在数字数组中，每个数字出现偶数次，并且只有一个数字出现奇数次 . 我们需要找到这个数字（之前讨论的问题是on Stack Overflow） .
这是一个用3种不同方法解决问题的解决方案 - 两种方法是O（N）（hash_set和hash_map），而一种是O（NlogN）（排序） . 但是，对任意大的输入进行分析表明排序更快，并且随着输入的增加变得越来越快（相比之下） .
实施或复杂性分析有什么问题，为什么O（NlogN）方法更快？
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using std::cout;
using std::chrono::high_resolution_clock;
using std::chrono::milliseconds;
using std::endl;
using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;
class ScopedTimer {
public:
ScopedTimer(const string& name)
: name_(name), start_time_(high_resolution_clock::now()) {}
~ScopedTimer() {
cout << name_ << " took "
<< std::chrono::duration_cast<milliseconds>(
high_resolution_clock::now() - start_time_).count()
<< " milliseconds" << endl;
}
private:
const string name_;
const high_resolution_clock::time_point start_time_;
};
int find_using_hash(const vector<int>& input_data) {
unordered_set<int> numbers(input_data.size());
for(const auto& value : input_data) {
auto res = numbers.insert(value);
if(!res.second) {
numbers.erase(res.first);
}
}
return numbers.size() == 1 ? *numbers.begin() : -1;
}
int find_using_hashmap(const vector<int>& input_data) {
unordered_map<int,int> counter_map;
for(const auto& value : input_data) {
++counter_map[value];
}
for(const auto& map_entry : counter_map) {
if(map_entry.second % 2 == 1) {
return map_entry.first;
}
}
return -1;
}
int find_using_sort_and_count(const vector<int>& input_data) {
vector<int> local_copy(input_data);
std::sort(local_copy.begin(), local_copy.end());
int prev_value = local_copy.front();
int counter = 0;
for(const auto& value : local_copy) {
if(prev_value == value) {
++counter;
continue;
}
if(counter % 2 == 1) {
return prev_value;
}
prev_value = value;
counter = 1;
}
return counter == 1 ? prev_value : -1;
}
void execute_and_time(const string& method_name, std::function<int()> method) {
ScopedTimer timer(method_name);
cout << method_name << " returns " << method() << endl;
}
int main()
{
vector<int> input_size_vec({1<<18,1<<20,1<<22,1<<24,1<<28});
for(const auto& input_size : input_size_vec) {
// Prepare input data
std::vector<int> input_data;
const int magic_number = 123454321;
for(int i=0;i<input_size;++i) {
input_data.push_back(i);
input_data.push_back(i);
}
input_data.push_back(magic_number);
std::random_shuffle(input_data.begin(), input_data.end());
cout << "For input_size " << input_size << ":" << endl;
execute_and_time("hash-set:",std::bind(find_using_hash, input_data));
execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, input_data));
execute_and_time("hash-map:",std::bind(find_using_hashmap, input_data));
cout << "--------------------------" << endl;
}
return 0;
}
分析结果：
sh$ g++ -O3 -std=c++11 -o main *.cc
sh$ ./main
For input_size 262144:
hash-set: returns 123454321
hash-set: took 107 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 37 milliseconds
hash-map: returns 123454321
hash-map: took 109 milliseconds
--------------------------
For input_size 1048576:
hash-set: returns 123454321
hash-set: took 641 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 173 milliseconds
hash-map: returns 123454321
hash-map: took 731 milliseconds
--------------------------
For input_size 4194304:
hash-set: returns 123454321
hash-set: took 3250 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 745 milliseconds
hash-map: returns 123454321
hash-map: took 3631 milliseconds
--------------------------
For input_size 16777216:
hash-set: returns 123454321
hash-set: took 14528 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 3238 milliseconds
hash-map: returns 123454321
hash-map: took 16483 milliseconds
--------------------------
For input_size 268435456:
hash-set: returns 123454321
hash-set: took 350305 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 60396 milliseconds
hash-map: returns 123454321
hash-map: took 427841 milliseconds
--------------------------
Addition
@Matt建议使用xor的快速解决方案当然不在竞争中 - 例如，在最差情况下，在1秒内：
int find_using_xor(const vector<int>& input_data) {
int output = 0;
for(const int& value : input_data) {
output = output^value;
}
return output;
}
For input_size 268435456:
xor: returns 123454321
xor: took 264 milliseconds
但问题仍然存在 - 尽管理论算法的复杂性优势，为什么散列与实际排序相比效率低？
6 回答
它实际上取决于hash_map / hash_set实现 . 通过用Google的
dense_hash_{map,set}替换libstdc的unordered_{map,set}，它明显快于sort.dense_hash_xxx的缺点是它们需要两个永远不会使用的键值 . 请参阅其文档了解详细信息另一件需要记住的事情是：
hash_{map,set}通常会进行大量的动态内存分配/解除分配，因此最好使用更好的替代libc的默认值malloc/free，例如谷歌的tcmalloc或Facebook的jemalloc.码：
这个分析与他的answer中的user3386199基本相同 . 无论他的回答是什么，我都会进行分析 - 但他确实首先到达那里 .
我在我的机器上运行程序（运行Ubuntu 14.04 LTE衍 生产环境 品的HP Z420），并为
1<<26添加了输出，所以我有一组不同的数字，但这些比率看起来与原始帖子中的数据比率非常相似 . 我得到的原始时间是（文件on-vs-logn.raw.data）：我创建了一个脚本
awk.analysis.sh来分析数据：该程序的输出相当广泛，但给出：
很明显，在这个平台上，哈希集和哈希映射算法不是O（N），它们也不如O（N.logN），但它们优于O（N3 / 2），更不用说O （N2） . 另一方面，排序算法确实非常接近O（N.logN） .
您只能将其归结为散列集和散列映射代码中的理论缺陷，或者散列表的大小不合适，以便它们使用次优的散列表大小 . 值得研究一下有哪些机制可以预先调整哈希集和哈希映射的大小，以确定使用它是否会影响性能 . （另见下面的额外信息 . ）
并且，仅为记录，这是原始数据的分析脚本的输出：
进一步测试显示修改散列函数如下所示：
和：
产生这样的分析：
显然，为哈希映射保留空间是有益的 .
哈希集代码是相当不同的;它添加了大约一半时间（整体）的项目，并且“添加”然后在另一半时间删除项目 . 这比哈希映射代码必须做的工作更多，所以它更慢 . 这也意味着保留空间大于实际需要的空间，并且可能考虑到保留空间的性能下降 .
让我们从查看排序解决方案的数字开始 . 在下表中，第一列是尺寸比率 . 它是通过计算给定测试的NlogN并除以第一次测试的NlogN来计算的 . 第二列是给定测试和第一次测试之间的时间比率 .
您可以看到两个比率之间存在非常好的一致性，表明排序例程确实是O（NlogN） .
那么为什么哈希例程没有按预期执行 . 简单来说，从哈希表中提取项目的概念是O（1）是纯粹的幻想 . 实际提取时间取决于散列函数的质量以及散列表中的bin数 . 实际提取时间的范围从O（1）到O（N），其中最坏的情况发生在哈希表中的所有条目最终都在同一个bin中 . 因此，使用哈希表，您应该期望您的性能介于O（N）和O（N ^ 2）之间，这似乎适合您的数据，如下所示
请注意，时间比率处于低位范围的结尾，表明哈希函数运行得相当好 .
我通过valgrind以不同的输入大小运行程序，我得到了循环计数的这些结果：
这表明排序时间正在慢慢超过哈希时间，至少在理论上如此 . 使用我的特定编译器/库（gcc 4.8.2 / libsddc）和优化（-O2），sort和hash方法的速度大约相同，大约为2 ^ 28，这正是你所尝试的极限 . 我怀疑在使用那么多内存时其他系统因素正在发挥作用，这使得难以在实际的墙壁时间内进行评估 .
O(N)似乎比O(N logN)慢的事实让我发疯，所以我决定深入研究这个问题 .我在Windows中使用Visual Studio进行了此分析，但我敢打赌，在Linux上使用g的结果会非常相似 .
首先，我使用Very Sleepy来查找
find_using_hash()中for循环中执行次数最多的代码片段 . 这就是我所看到的：如您所见，顶部条目都与列表相关（
RtlAllocateHeap从列表代码中调用） . 显然，问题在于，对于unordered_set中的每次插入，并且由于存储桶是作为列表实现的，因此会对节点进行分配，并且这会使算法的持续时间发生火花，而不是不进行分配的排序 .为了确定这是问题，我写了一个非常简单的哈希表实现，没有分配，结果更合理：
因此，在最大的例子（即
1<<28）中，因子log N乘以N仍然小于分配所需的"constant"工作量 .这里有许多很好的答案，但这是一种特殊的问题，自然会产生许多有效的答案 .
我正在编写以提供数学视角的答案（没有LaTeX很难做到），因为纠正未解决的误解是很重要的，即用哈希解决给定问题代表了一个问题，但不知何故"practically"比
O(n)更糟糕 . 这样的事情在数学上是不可能的！要理解为什么问题不是"theoretically"
O(n)，有必要注意基础假设也是错误的：哈希是"theoretically"O(1)数据结构不是真的 .事实恰恰相反 . 哈希以其纯粹的形式只是"practically"数据结构，但理论上仍然是
O(n)数据结构 . （注意：在混合形式中，它们可以实现理论上的性能 . ）因此，在最好的情况下，解决方案仍然是
O(n log n)问题，因为n接近无穷大 .所以现在让我解释一下这种说法是否属实，但是在实践中，而不是理论上 .
对于任何应用程序（无论
n，只要n提前知道 - 他们在数学证明中称为"fixed"而不是"arbitrary"），您可以设计哈希表以匹配应用程序，并在约束条件下获得O(1)性能环境 . 每个纯散列结构旨在在先验的数据集大小范围内良好地执行，并且假定密钥相对于散列函数具有独立性 .但是当你按照Big-
O符号的定义要求接近无穷大时，那么桶开始填充（这必须通过鸽子原理发生），并且任何纯哈希结构都会分解成一个O(n)算法（大 -O符号在这里忽略了取决于有多少桶的常数因子 .所以在这一点上，而不是方程，一个适当的类比会更有帮助：
通过想象一个包含26个抽屉的文件柜，可以获得对哈希表的非常准确的数学理解每个字母的字母 . 每个文件都存储在抽屉中，该抽屉对应于文件名中的第一个字母 .
"hash function"是一个
O(1)操作，查看第一个字母 .存储是
O(1)操作：将文件放在该字母的抽屉内 .只要每个抽屉内没有多个文件，检索就是
O(1)操作：打开该字母的抽屉 .在这些设计约束中，此哈希结构为
O(1).现在假设您超出了这个“文件柜”散列结构的设计约束，并且存储了数百个文件 . 存储现在需要尽可能多的操作来在每个抽屉中找到空的空间，并且检索采取与每个抽屉内的项目数一样多的操作 .
与将所有文件放入一个巨大的堆中相比，整体的平均性能大约好于时间的1/26 . 但请记住，在数学上，人们不能说
O(n/26)，因为O(n)符号的定义并未考虑影响性能的常数因素，而只考虑算法复杂度作为n的函数 . 因此，当超出设计约束时，数据结构为O(n).