C++性能优化实践（基于C++17）

需求

这个例子来自于《C++高级编程》，作者把进一步的优化留给了读者，我们这里来还原一下优化过程，并实现一个优于书中的解决办法。

需求是这样的：文件boys_long.txt中保存了500500个人名，大部分的名字是重复的，给定任意人名，找出该名称出现次数的排名。

第一次尝试

首先考虑使用vector数组来保存人名数据，为了将人名和出现次数对应起来，在数组中保存pair。头文件NameDB.h定义如下：

#pragma once

#include <string_view>
#include <string>
#include <vector>
#include <utility>

class NameDB
{
public:
  NameDB(std::string_view nameFile);

  // 返回名字排名，如果没有找到则返回-1
  int getNameRank(std::string_view name) const;

  // 返回名字出现的次数，如果没有找到名字则返回-1
  int getAbsoluteNumber(std::string_view name) const;

private:
  // 保存名字的数组
  std::vector<std::pair<std::string, int>> mNames;

  bool nameExists(std::string_view name) const;
  void incrementNameCount(std::string_view name);
  void addNewName(std::string_view name);
};

这里主要关注一下vector数组及pair名字对的使用，因为数据结构是性能优化的关键。

这些函数的实现在NameDB.cpp里：

#include "NameDB.h"
#include <stdexcept>
#include <fstream>

using namespace std;

NameDB::NameDB(string_view nameFile)
{
  ifstream inputFile(nameFile.data());
  if (!inputFile) {
    throw invalid_argument("Unable to open file");
  }

  // 从文件中读取名字，一次读一个
  string name;
  while (inputFile >> name) {
    // 查找名字是否存在
    if (nameExists(name)) {
      // 名字存在则将出现次数加1
      incrementNameCount(name);
    } else {
      // 名字不存在，则加入新名字
      addNewName(name);
    }
  }
}

// 暴力搜索，判断名字是否存在
bool NameDB::nameExists(string_view name) const
{
  for (auto& entry : mNames) {
    if (entry.first == name) {
      return true;
    }
  }
  return false;
}
// 暴力搜索，如果名字存在则加1
void NameDB::incrementNameCount(string_view name)
{
  for (auto& entry : mNames) {
    if (entry.first == name) {
      entry.second++;
      return;
    }
  }
}

void NameDB::addNewName(string_view name)
{
  mNames.push_back(make_pair(name.data(), 1));
}

int NameDB::getNameRank(string_view name) const
{
  int num = getAbsoluteNumber(name);

  if (num == -1) {
    return -1;
  }

  // 统计出现次数更高的个数
  int rank = 1;
  for (auto& entry : mNames) {
    if (entry.second > num) {
      rank++;
    }
  }

  return rank;
}

// 获取名字出现次数
int NameDB::getAbsoluteNumber(string_view name) const
{
  for (auto& entry : mNames) {
    if (entry.first == name) {
      return entry.second;
    }
  }
  return -1;
}

基本的逻辑都实现了，但是多次使用到了暴力搜索，基本判断性能不可能会高。

在文件NameDBTest.cpp中使用上述实现的NameDB类，代码如下：

#include "NameDB.h"
#include <iostream>

using namespace std;

int main()
{
  NameDB boys("boys_long.txt");

  cout << boys.getNameRank("Daniel") << endl;
  cout << boys.getNameRank("Jacob") << endl;
  cout << boys.getNameRank("William") << endl;

  return 0;
}

使用以下命令编译：

g++ -std=c++17  -o namedb *.cpp

运行：

time ./namedb
8
1
11
./namedb  18.06s user 0.01s system 96% cpu 18.767 total

不出所料，整个运行时间用了18s。可以断定数组的反复暴力搜索消耗了大部分时间，如果使用gprof工具可以很清楚看到这一点。由于性能瓶颈很明显，我们就不用gprof了。很显然，在读文件时，时间复杂度是O(n^2)，而在查询排名时又用去了O(n)的时间。

第二次尝试

使用元素定位时间为常数的unordered_map应该可以解决上述vector带来的问题。

重新定义头文件NameDB.h定义如下：

#pragma once

#include <string_view>
#include <string>
#include <unordered_map>

class NameDB
{
public:
	NameDB(std::string_view nameFile);
	int getNameRank(std::string_view name) const;
	int getAbsoluteNumber(std::string_view name) const;

private:
	std::unordered_map<std::string, int> mNames;
};

我们在新的定义里去掉了一些方法，由于unordered_map实现类型逻辑非常方便，这些方法已经不需要了。

文件NameDB.cpp的实现如下：

#include "NameDB.h"
#include <stdexcept>
#include <fstream>
#include <iostream>

using namespace std;

NameDB::NameDB(string_view nameFile)
{
	ifstream inputFile(nameFile.data());
	if (!inputFile) {
		throw invalid_argument("Unable to open file");
	}

	string name;
	while (inputFile >> name) {
		++mNames[name];
	}
}

int NameDB::getNameRank(string_view name) const
{
	int num = getAbsoluteNumber(name);
	if (num == -1) {
		return -1;
	}

	int rank = 1;
	for (auto& entry : mNames) {
		if (entry.second > num) {
			rank++;
		}
	}

	return rank;
}

int NameDB::getAbsoluteNumber(string_view name) const
{
	auto res = mNames.find(name.data());
	if (res != end(mNames)) {
		return res->second;
	}

	return -1;
}

与使用vector的版本相比，代码量少了，实现逻辑也更为清晰。猜测性能应该不错，测试一下看看：

g++ -std=c++17  -o namedb *.cpp
time ./namedb
8
1
11
./namedb  0.33s user 0.01s system 34% cpu 0.984 total

Oops！18s vs 0.33s，性能差异如此之大！之所以有这么大的性能差异，主要归功于unordered_map O(1)的元素定位时间。在getNameRank方法里，我们仍然采用了循环进行线性查找，这个时间复杂度是O(n)，是否可以进一步优化呢？我们来继续分析尝试。

第三次尝试

我们这一次尝试主要来优化getNameRank 方法，借助数据结构的优化提升该方法的查找效率。由于unordered_map保存的数据类型是std::pair<人名，次数>，如果我们在读取完文件后，对这些pair进行排序，那么在查找的时候就可以使用标准库的find_if，找到的哪一项排序的顺序就是排名了。

具体的做法是：

将std::pair<人名，次数>的指针保存到vector数组中。
读完文件后依据次数对该数组进行排序。
以后每次getNameRank调用都从该数组进行查找，元素在该数据中的排名即最终排名。

NameDB.h定义如下：

#pragma once

#include <string_view>
#include <string>
#include <unordered_map>
#include <vector>

class NameDB
{
public:
	NameDB(std::string_view nameFile);
	int getNameRank(std::string_view name) const;
	int getAbsoluteNumber(std::string_view name) const;
private:
  using PairPoint=std::pair<const std::string, int>;
	std::unordered_map<std::string, int> mNames;
  std::vector<PairPoint *> mVector;
};

我们定义了数据类型PairPoint，增加了一个数组mVector来保存PairPoint的指针。

文件NameDB.cpp的实现如下：

#include "NameDB.h"
#include <stdexcept>
#include <fstream>
#include <iostream>

using namespace std;
NameDB::NameDB(string_view nameFile)
{
	ifstream inputFile(nameFile.data());
	if (!inputFile) {
		throw invalid_argument("Unable to open file");
	}

	string name;
	while (inputFile >> name) {
    auto item = mNames.find(name);
    if (item != mNames.end()) {
      item->second++;
    } else {
      mNames[name] = 1;
      item = mNames.find(name);
      mVector.push_back(&(*item));
    }
	}

  sort(mVector.begin(), mVector.end(), [](auto x, auto y) {
    return x->second < y->second;
  });
}

int NameDB::getNameRank(string_view name) const
{
	int num = getAbsoluteNumber(name);

	if (num == -1) {
		return -1;
	}

  auto fi = find_if(mVector.begin(), mVector.end(), [&name](auto x) {
    return x->first == name;
  });

    return mVector.end() - fi;
}

int NameDB::getAbsoluteNumber(string_view name) const
{
	auto res = mNames.find(name.data());
	if (res != end(mNames)) {
		return res->second;
	}

	return -1;
}

文件NameDBTest.cpp不做改动，编译、运行如下：

g++ -std=c++17  -o namedb *.cpp

time ./namedb
8
1
11
./namedb  0.30s user 0.00s system 32% cpu 0.947 total

与第二次尝试相比，性能又进一步提升了！由于我们主要优化了getNameRank方法，如果该方法有大量调用，优化效果应该是更加明显的。需要注意的是，我们的vector数组是排过序的，这是一个可以利用的优化点，但是std::find_if函数没有利用到。所以还可以进一步优化。

继续优化

我们尝试自己实现一个二分法查找，替代find_if来提升查找的效率。

修改文件NameDB.cpp中的getNameRank方法如下：

int NameDB::getNameRank(string_view name) const
{
	int num = getAbsoluteNumber(name);

	if (num == -1) {
		return -1;
	}

  int lo = 0, hi = mVector.size();
  int mi = 0;
  while (lo < hi) {
    mi = (lo + hi) >> 1;
    if (mVector[mi]->second > num) {
      hi = mi;
    } else if (mVector[mi]->second < num) {
      lo = mi + 1;
    } else {
      break;
    }
  }

  return mVector.size() - mi;
}

重新编译、运行：

g++ -std=c++17  -o namedb *.cpp
time ./namedb
8
1
11
./namedb  0.29s user 0.00s system 26% cpu 1.125 total

0.29s，比第三次尝试又提升了0.01s。由于getNameRank调用次数较少，效果并不明显，将getNameRank的调用次数提升到10万次，修改NameDBTest.cpp 文件如下：

#include "NameDB.h"
#include <iostream>

using namespace std;

int main()
{
	NameDB boys("boys_long.txt");

  /*
  cout << boys.getNameRank("Daniel") << endl;
	cout << boys.getNameRank("Jacob") << endl;
	cout << boys.getNameRank("William") << endl;
  */

  for(int i = 0; i < 100000 ; ++i) {
    boys.getNameRank("Jacob");
  }

	return 0;
}

再次编译运行，第三次尝试的运行如下：

time ./namedb
./namedb  6.44s user 0.02s system 99% cpu 6.513 total

使用了二分查找优化后的运行如下：

time ./namedb
./namedb  0.34s user 0.00s system 98% cpu 0.351 total

可以看到，二分查找的时间复杂度是O(logn)，采用了二分查找后，性能提升了一个数量级。如果不自己实现，也可以采用标准库的二分查找算法lower_bound，最终结果是一样的，代码如下：

int NameDB::getNameRank(string_view name) const
{
	int num = getAbsoluteNumber(name);

	if (num == -1) {
		return -1;
	}

  auto low_bound = lower_bound(mVector.begin(), mVector.end(), num, [](auto x, int val){
    return x->second < val; 
  });

  return mVector.end() - low_bound;
}

总结

合适的数据结构和算法在C++性能优化中起到了关键性作用。
为了更加明显对比性能，我们都没有使用编译器优化，如果在编译时加上O2或者O3参数，优化效果非常明显，运行效率的差异没有变化。
所有代码都在gitee上： https://gitee.com/wisting/cpluscplus-optimize

wisting/C++性能优化实践（基于C++17）

C++性能优化实践（基于C++17）

需求

第一次尝试

第二次尝试

第三次尝试

继续优化

总结

简介

发行版

贡献者

近期动态

wisting/C++性能优化实践（基于C++17） .gitee-modal { width: 500px !important; }

C++性能优化实践（基于C++17）

需求

第一次尝试

第二次尝试

第三次尝试

继续优化

总结

简介

发行版

贡献者

近期动态

搜索帮助

wisting/C++性能优化实践（基于C++17）