use*_*804 6 c++ heap performance boost stl
我目前正在寻找满足我要求的C++中最快的数据结构:
我不需要删除/插入(除了最初的删除/插入)或其他任何内容.我认为堆是最好的选择.在查看STL之后,我发现大多数数据结构都不支持更新(这是关键部分).解决方案是删除并重新插入看起来很慢的元素(我的程序的瓶颈).然后我查看了boost提供的堆,发现pairing_heap给了我最好的结果.但是,所有堆仍然比MultiMap上的删除/插入过程慢.有没有人有建议,我可以尝试哪种方法/实施？
非常感谢你.
再次为了完整起见,这是我目前的时间:
编辑我的帖子以澄清一些事情:
小智 4
我尝试了一下，因为它很有趣，而且我想我自己也可以使用这样的结构。通常很难击败专业编写的标准库，除非您可以做出缩小的假设，从而比他们的解决方案限制更多的通用性（以及可能的稳健性）。
例如，malloc如果free您的目标只是编写一个像malloc. 但是，如果您对特定用例做出很多假设，则很容易编写一个分配器来仅针对该特定用例击败这些假设。
这就是为什么，如果您对数据结构有这样的疑问，我建议尽可能多地提供有关您的特定用例的特殊细节的信息（您需要从结构中得到什么，例如迭代、排序、搜索、从中间删除、插入到前面，键的范围，类型等）。您想要做的一些测试代码（甚至是伪代码）会很有帮助。我们希望尽可能多地采用这些缩小范围的假设。
在您的例子中，我们对如此大的堆类型结构进行了特殊的动态使用。我最初有老派的游戏背景，在这种非常动态的情况下，通常低于标准的搜索算法实际上比具有优越算法复杂性的算法效果更好，因为搜索优势通常伴随着更昂贵的价格标签。构建/更新过程（较慢的插入/删除）。
例如，如果在 2D 游戏中的每一帧都有大量精灵在移动，那么在实践中，用于最近邻搜索的、编写粗糙、算法较差的固定网格加速器在实践中通常比算法优越、专业的加速器效果更好。编写四叉树，因为不断移动物体和重新平衡树的成本可能会增加开销，超过所有事物的卓越加速和理论对数复杂性。当所有精灵聚集在一个区域时，固定网格会出现病态情况，但这种情况很少发生。
所以我采取了这样的策略。我正在做出一些假设，其中最大的假设是您的密钥在一定范围内合理分布。另一个是您可以粗略地估计容器应处理的最大元素数量（尽管您可以超过或低于这个数字，但它在一些粗略的知识和预期的情况下效果最好）。而且我没有费心提供迭代器来迭代容器（如果您愿意，这是可能的，但键不会像 那样完美排序std::multimap，它们会“有点”排序），但它确实提供了从middle 除了用最小键弹出元素之外。我的解决方案中存在一个病态的情况，例如，std::multimap如果您有大量元素，其中所有百万个元素的键值大致相同（例如：0.000001、0.00000012、0.000000011 等），那么它会降级对所有元素进行线性搜索，并且性能比 差很多multimap。
std::multmap但我得到了一个解决方案，它比我的假设适合您的用例快约 8 倍。
注意：它是仓促的代码，并使用大量快速而肮脏的分析器辅助微优化编写，甚至提供池分配器并在对齐假设的情况下在位和字节级别操作事物（使用最大对齐假设“足够可移植”） 。它也不关心异常安全之类的事情。然而，它对于 C++ 对象来说应该是安全的。
作为测试用例，我创建了一百万个随机密钥，并开始弹出最小密钥，更改它们，然后重新插入它们。我对多重贴图和我的结构都这样做了，以比较性能。
#include <iostream>
#include <cassert>
#include <utility>
#include <stdexcept>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <map>
#include <vector>
#include <malloc.h>
// Max Alignment
#if defined(_MSC_VER)
#define MAX_ALIGN __declspec(align(16))
#else
#define MAX_ALIGN __attribute__((aligned(16)))
#endif
using namespace std;
static void* max_malloc(size_t amount)
{
#ifdef _MSC_VER
return _aligned_malloc(amount, 16);
#else
void* mem = 0;
posix_memalign(&mem, 16, amount);
return mem;
#endif
}
static void max_free(void* mem)
{
#ifdef _MSC_VER
return _aligned_free(mem);
#else
free(mem);
#endif
}
// Balanced priority queue for very quick insertions and
// removals when the keys are balanced across a distributed range.
template <class Key, class Value, class KeyToIndex>
class BalancedQueue
{
public:
enum {zone_len = 256};
/// Creates a queue with 'n' buckets.
explicit BalancedQueue(int n):
num_nodes(0), num_buckets(n+1), min_bucket(n+1), buckets(static_cast<Bucket*>(max_malloc((n+1) * sizeof(Bucket)))), free_nodes(0), pools(0)
{
const int num_zones = num_buckets / zone_len + 1;
zone_counts = new int[num_zones];
for (int j=0; j < num_zones; ++j)
zone_counts[j] = 0;
for (int j=0; j < num_buckets; ++j)
{
buckets[j].num = 0;
buckets[j].head = 0;
}
}
/// Destroys the queue.
~BalancedQueue()
{
clear();
max_free(buckets);
while (pools)
{
Pool* to_free = pools;
pools = pools->next;
max_free(to_free);
}
delete[] zone_counts;
}
/// Makes the queue empty.
void clear()
{
const int num_zones = num_buckets / zone_len + 1;
for (int j=0; j < num_zones; ++j)
zone_counts[j] = 0;
for (int j=0; j < num_buckets; ++j)
{
while (buckets[j].head)
{
Node* to_free = buckets[j].head;
buckets[j].head = buckets[j].head->next;
node_free(to_free);
}
buckets[j].num = 0;
}
num_nodes = 0;
min_bucket = num_buckets+1;
}
/// Pushes an element to the queue.
void push(const Key& key, const Value& value)
{
const int index = KeyToIndex()(key);
assert(index >= 0 && index < num_buckets && "Key is out of range!");
Node* new_node = node_alloc();
new (&new_node->key) Key(key);
new (&new_node->value) Value(value);
new_node->next = buckets[index].head;
buckets[index].head = new_node;
assert(new_node->key == key && new_node->value == value);
++num_nodes;
++buckets[index].num;
++zone_counts[index/zone_len];
min_bucket = std::min(min_bucket, index);
}
/// @return size() == 0.
bool empty() const
{
return num_nodes == 0;
}
/// @return The number of elements in the queue.
int size() const
{
return num_nodes;
}
/// Pops the element with the minimum key from the queue.
std::pair<Key, Value> pop()
{
assert(!empty() && "Queue is empty!");
for (int j=min_bucket; j < num_buckets; ++j)
{
if (buckets[j].head)
{
Node* node = buckets[j].head;
Node* prev_node = node;
Node* min_node = node;
Node* prev_min_node = 0;
const Key* min_key = &min_node->key;
const Value* min_val = &min_node->value;
for (node = node->next; node; prev_node = node, node = node->next)
{
if (node->key < *min_key)
{
prev_min_node = prev_node;
min_node = node;
min_key = &min_node->key;
min_val = &min_node->value;
}
}
std::pair<Key, Value> kv(*min_key, *min_val);
if (min_node == buckets[j].head)
buckets[j].head = buckets[j].head->next;
else
{
assert(prev_min_node);
prev_min_node->next = min_node->next;
}
removed_node(j);
node_free(min_node);
return kv;
}
}
throw std::runtime_error("Trying to pop from an empty queue.");
}
/// Erases an element from the middle of the queue.
/// @return True if the element was found and removed.
bool erase(const Key& key, const Value& value)
{
assert(!empty() && "Queue is empty!");
const int index = KeyToIndex()(key);
if (buckets[index].head)
{
Node* node = buckets[index].head;
if (node_key(node) == key && node_val(node) == value)
{
buckets[index].head = buckets[index].head->next;
removed_node(index);
node_free(node);
return true;
}
Node* prev_node = node;
for (node = node->next; node; prev_node = node, node = node->next)
{
if (node_key(node) == key && node_val(node) == value)
{
prev_node->next = node->next;
removed_node(index);
node_free(node);
return true;
}
}
}
return false;
}
private:
// Didn't bother to make it copyable -- left as an exercise.
BalancedQueue(const BalancedQueue&);
BalancedQueue& operator=(const BalancedQueue&);
struct Node
{
Key key;
Value value;
Node* next;
};
struct Bucket
{
int num;
Node* head;
};
struct Pool
{
Pool* next;
MAX_ALIGN char buf[1];
};
Node* node_alloc()
{
if (free_nodes)
{
Node* node = free_nodes;
free_nodes = free_nodes->next;
return node;
}
const int pool_size = std::max(4096, static_cast<int>(sizeof(Node)));
Pool* new_pool = static_cast<Pool*>(max_malloc(sizeof(Pool) + pool_size - 1));
new_pool->next = pools;
pools = new_pool;
// Push the new pool's nodes to the free stack.
for (int j=0; j < pool_size; j += sizeof(Node))
{
Node* node = reinterpret_cast<Node*>(new_pool->buf + j);
node->next = free_nodes;
free_nodes = node;
}
return node_alloc();
}
void node_free(Node* node)
{
// Destroy the key and value and push the node back to the free stack.
node->key.~Key();
node->value.~Value();
node->next = free_nodes;
free_nodes = node;
}
void removed_node(int bucket_index)
{
--num_nodes;
--zone_counts[bucket_index/zone_len];
if (--buckets[bucket_index].num == 0 && bucket_index == min_bucket)
{
// If the bucket became empty, search for next occupied minimum zone.
const int num_zones = num_buckets / zone_len + 1;
for (int j=bucket_index/zone_len; j < num_zones; ++j)
{
if (zone_counts[j] > 0)
{
for (min_bucket=j*zone_len; min_bucket < num_buckets && buckets[min_bucket].num == 0; ++min_bucket) {}
assert(min_bucket/zone_len == j);
return;
}
}
min_bucket = num_buckets+1;
assert(empty());
}
}
int* zone_counts;
int num_nodes;
int num_buckets;
int min_bucket;
Bucket* buckets;
Node* free_nodes;
Pool* pools;
};
/// Test Parameters
enum {num_keys = 1000000};
enum {buckets = 100000};
static double sys_time()
{
return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}
struct KeyToIndex
{
int operator()(double val) const
{
return static_cast<int>(val * buckets);
}
};
int main()
{
vector<double> keys(num_keys);
for (int j=0; j < num_keys; ++j)
keys[j] = static_cast<double>(rand()) / RAND_MAX;
for (int k=0; k < 5; ++k)
{
// Multimap
{
const double start_time = sys_time();
multimap<double, int> q;
for (int j=0; j < num_keys; ++j)
q.insert(make_pair(keys[j], j));
// Pop each key, modify it, and reinsert.
for (int j=0; j < num_keys; ++j)
{
pair<double, int> top = *q.begin();
q.erase(q.begin());
top.first = static_cast<double>(rand()) / RAND_MAX;
q.insert(top);
}
cout << (sys_time() - start_time) << " secs for multimap" << endl;
}
// Balanced Queue
{
const double start_time = sys_time();
BalancedQueue<double, int, KeyToIndex> q(buckets);
for (int j=0; j < num_keys; ++j)
q.push(keys[j], j);
// Pop each key, modify it, and reinsert.
for (int j=0; j < num_keys; ++j)
{
pair<double, int> top = q.pop();
top.first = static_cast<double>(rand()) / RAND_MAX;
q.push(top.first, top.second);
}
cout << (sys_time() - start_time) << " secs for BalancedQueue" << endl;
}
cout << endl;
}
}
我的机器上的结果：
3.023 secs for multimap
0.34 secs for BalancedQueue
2.807 secs for multimap
0.351 secs for BalancedQueue
2.771 secs for multimap
0.337 secs for BalancedQueue
2.752 secs for multimap
0.338 secs for BalancedQueue
2.742 secs for multimap
0.334 secs for BalancedQueue