在无序元素上有效独特
Dan*_*zes 10 c++ algorithm performance unique
我想提高我在分形分析中使用的盒子计数方法的速度性能.
关于任务
我有一个整数流(大约n = 2 ^ 24长),我必须计算流中有多少不同的值.没有上限,允许负值(但负值的数量可能小于sqrt(n)).流中存在小的相关性,即实际元素可能与前一个元素相等或不太远.在许多情况下,我在整个范围内有很多相等的值.
方法我已经尝试过了
矢量,排序,uniqe
我的第一个实现是将所有元素放入向量中,然后我应用std :: sort然后应用std :: unique.
这种方法的复杂性是O(n*log(n)),我认为任何其他算法在扩展时都不会更快.但我确信一个代码必须存在比这更快但具有相同的缩放属性 - 只有一个常数因子才能更快.原因是:
- 我在向量中存储了很多相等的值,因此排序不是那么有效,向量过大
- 在这种方法中,我不使用实际元素和前一个元素彼此接近的信息
- 我不需要有关这些唯一值的信息,我只需要不同元素的数量
设置,插入,大小
为了消除第一个无效点,我将每个元素放入set :: insert的集合中.最后我用set :: size计算了元素的数量.
我的期望是这段代码必须更快,因为只有唯一值存储在集合中,并且它不必比较具有大量相等值的新元素.但不幸的是,这种方法比前一种方法慢1.5倍.
set,emplace_hint,size
为了消除第二个无效点,我不仅将每个元素放入一个集合中,而且使用函数set :: emplace_hint.每当一个提示将新元素放在前一个元素旁边时.最后,我用set :: size询问了set的大小
我的期望是这个代码必须比前一代码更快,因为我可以猜出新元素的价值,它总比没有好.但不幸的是,这种方法比前一种方法慢了5倍.
这个问题
您能否建议任何可以计算流中不同元素(int)数量的有效方法？如果知道的话,你能优化代码吗？
- 数字中存在可测量的相关性
- 有些数字是重复出现的
目标体系结构是现代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
小智 4
只是比较不同的方法（不考虑基数排序）：
#include <algorithm>
#include <deque>
#include <iostream>
#include <unordered_set>
#include <set>
#include <vector>
#include <chrono>
template <template <typename ...> class Container, typename T, typename ... A, typename Comp>
inline bool insert_sorted(Container<T, A...>& container, T const& e, Comp const& comp) {
auto const it = std::lower_bound(container.begin(), container.end(), e, comp);
if (it != container.end() and not comp(e, *it)) { return false; }
container.insert(it, e);
return true;
}
template <template <typename ...> class Container, typename T, typename ... A>
inline bool insert_sorted(Container<T, A...>& container, T const& e) {
return insert_sorted(container, e, std::less<T>{});
}
int main() {
using namespace std::chrono;
typedef std::vector<int> data_type;
const unsigned Size = unsigned(1) << 24;
const unsigned Limit = 1000;
data_type data;
data.reserve(Size);
for(unsigned i = 0; i < Size; ++i) {
int value = double(Limit) * std::rand() / RAND_MAX - 0.1;
data.push_back(value);
while(i < Size - 1 && rand() < RAND_MAX * 0.25) {
data.push_back(value);
++i;
}
}
std::cout
<< "Data\n"
<< "====\n"
<< " Size of data: " << Size << '\n';
std::cout
<< "Unorderd Set\n"
<< "============\n";
{
auto start = system_clock::now();
typedef std::unordered_set<int> set_type;
set_type set;
unsigned i = 0;
for( ; i < Size - 1; ++i) {
// Ignore a range of equal values
while(data[i] == data[i+1]) ++i;
set.insert(data[i]);
}
if(i < Size)
set.insert(data[i]);
auto stop = system_clock::now();
std::cout
<< "Number of different elements: "
<< set.size() << '\n';
std::cout
<< " Timing: "
<< duration_cast<duration<double>>(stop - start).count()
<< '\n';
}
std::cout
<< "Set\n"
<< "===\n";
{
auto start = system_clock::now();
typedef std::set<int> set_type;
set_type set;
unsigned i = 0;
for( ; i < Size - 1; ++i) {
// Ignore a range of equal values
while(data[i] == data[i+1]) ++i;
set.insert(data[i]);
}
if(i < Size)
set.insert(data[i]);
auto stop = system_clock::now();
std::cout
<< "Number of different elements: "
<< set.size() << '\n';
std::cout
<< " Timing: "
<< duration_cast<duration<double>>(stop - start).count()
<< '\n';
}
std::cout
<< "Sorted Vector\n"
<< "=============\n";
{
auto start = system_clock::now();
typedef std::vector<int> set_type;
set_type set;
unsigned i = 0;
for( ; i < Size - 1; ++i) {
// Ignore a range of equal values
while(data[i] == data[i+1]) ++i;
insert_sorted(set, data[i]);
}
if(i < Size)
insert_sorted(set, data[i]);
auto stop = system_clock::now();
std::cout
<< "Number of different elements: "
<< set.size() << '\n';
std::cout
<< " Timing: "
<< duration_cast<duration<double>>(stop - start).count()
<< '\n';
}
std::cout
<< "BitVector\n"
<< "=========\n";
{
auto start = system_clock::now();
typedef std::vector<bool> set_type;
set_type set(Limit);
unsigned i = 0;
unsigned elements = 0;
for( ; i < Size; ++i) {
if( ! set[data[i]]) {
set[data[i]] = true;
++elements;
}
}
auto stop = system_clock::now();
std::cout
<< "Number of different elements: "
<< elements << '\n';
std::cout
<< " Timing: "
<< duration_cast<duration<double>>(stop - start).count()
<< '\n';
}
std::cout
<< "Sorted Data\n"
<< "===========\n";
{
auto start = system_clock::now();
std::sort(data.begin(), data.end());
auto last = std::unique(data.begin(), data.end());
auto stop = system_clock::now();
std::cout
<< "Number of different elements: "
<< last - data.begin() << '\n';
std::cout
<< " Timing: "
<< duration_cast<duration<double>>(stop - start).count()
<< '\n';
}
return 0;
}
使用 g++ -std=c++11 -O3 编译给出：
Data
====
Size of data: 16777216
Unorderd Set
============
Number of different elements: 1000
Timing: 0.269752
Set
===
Number of different elements: 1000
Timing: 1.23478
Sorted Vector
=============
Number of different elements: 1000
Timing: 1.13783
BitVector
=========
Number of different elements: 1000
Timing: 0.038408
Sorted Data
===========
Number of different elements: 1000
Timing: 1.32827
因此，如果内存没有问题或者数字范围有限，设置一点是最好的选择。否则，unordered_set 是一个不错的选择。