相关疑难解决方法(0)

我已经阅读过像bloom过滤器和跳过列表这样的数据结构.

概率数据结构的共同特征是什么？它们用于什么？

我想提高我在分形分析中使用的盒子计数方法的速度性能.

关于任务

我有一个整数流(大约n = 2 ^ 24长),我必须计算流中有多少不同的值.没有上限,允许负值(但负值的数量可能小于sqrt(n)).流中存在小的相关性,即实际元素可能与前一个元素相等或不太远.在许多情况下,我在整个范围内有很多相等的值.

方法我已经尝试过了

矢量,排序,uniqe

我的第一个实现是将所有元素放入向量中,然后我应用std :: sort然后应用std :: unique.

这种方法的复杂性是O(n*log(n)),我认为任何其他算法在扩展时都不会更快.但我确信一个代码必须存在比这更快但具有相同的缩放属性 - 只有一个常数因子才能更快.原因是:

1. 我在向量中存储了很多相等的值,因此排序不是那么有效,向量过大
2. 在这种方法中,我不使用实际元素和前一个元素彼此接近的信息
3. 我不需要有关这些唯一值的信息,我只需要不同元素的数量

设置,插入,大小

为了消除第一个无效点,我将每个元素放入set :: insert的集合中.最后我用set :: size计算了元素的数量.

我的期望是这段代码必须更快,因为只有唯一值存储在集合中,并且它不必比较具有大量相等值的新元素.但不幸的是,这种方法比前一种方法慢1.5倍.

set,emplace_hint,size

为了消除第二个无效点,我不仅将每个元素放入一个集合中,而且使用函数set :: emplace_hint.每当一个提示将新元素放在前一个元素旁边时.最后,我用set :: size询问了set的大小

我的期望是这个代码必须比前一代码更快,因为我可以猜出新元素的价值,它总比没有好.但不幸的是,这种方法比前一种方法慢了5倍.

这个问题

您能否建议任何可以计算流中不同元素(int)数量的有效方法？如果知道的话,你能优化代码吗？

1. 数字中存在可测量的相关性
2. 有些数字是重复出现的

目标体系结构是现代x86或x86-64 PC处理器(使用sse,sse2),只有单线程代码是合适的.我不喜欢使用boost而是使用c ++ 11.

解决方案

首先,感谢许多建议,耐心和理解,我很抱歉,我无法测试所有方法,我也确信有效性取决于我没有提供的整数流的细节.但是我分享了VS2013编译器的结果.(代码在gcc4.7下测试但未测量.)这个主题值得花很多时间去研究,但我有一个符合我需求的解决方案.

关于方法:

• bool的矢量:DieterLücking的BitVector解决方案
• 二进制查找:Tony D建议的方法
• unordered set:将所有元素简单地放入std :: unordered_set,然后询问其元素的数量,如Ixanezis所示
• 矢量插入排序:使用DieterLücking的Sorted Vector方法
• set insert:我在问题表单中描述的方法
• 基数排序:Ixanezis的建议,在向量上使用流行的排序算法
• set emplace提示:使用问题表单中描述的std :: emplace_hint