最快的C++地图？

Question

纠正我我错了,但是std :: map是一个有序的映射,因此每次插入一个值时,map都会使用算法在内部对其项进行排序,这需要一些时间.

我的应用程序以恒定间隔获取有关某些项目的信息.

这个应用程序保留一个定义如下的地图:

::std::map<DWORD, myItem*>

首先,所有项目都被视为应用程序的"新"项.正在分配"Item"对象并将其添加到此映射,将其id和指向它的指针相关联.

如果它不是"新"项(只是对象的更新),我的应用程序应该使用给定的id在地图上找到对象并更新.

大多数时候我都会得到更新.

我的问题是:
是否有更快的地图实施或我应该继续使用这个？
我最好使用unordered_map吗？

Answer 1

我最好使用unordered_map吗？

有可能.

std:map在O(log n)处提供一致的性能,因为它需要实现为平衡树.但是std:unordered_map将作为哈希表实现,它可能会给你O(1)性能(良好的哈希函数和跨哈希桶的密钥分配),但它可能是O(n)(一个哈希桶中的所有内容并转换为列表) .人们通常会期待这些极端之间的某些东西.

因此,您可以始终拥有合理的性能(O(log n)),或者您需要确保所有内容都能通过哈希获得良好的性能.

与任何此类问题一样:您需要在采取一种方法之前进行衡量.除非您的数据集很大,否则您可能会发现没有显着差异.

Answer 2

重要警告:除非您已经测量过(并且您的问题表明您没有),否则地图性能会严重影响您的应用程序性能(大部分时间花在搜索和更新地图上),不要费心去加快速度.坚持std::map(或std::unordered_map任何可用的hash_map实施).将您的应用程序加速1%可能不值得付出努力.让它免于bug.

回应理查德的回答:使用您的真实类和真实数据,通过不同的地图实现来衡量绩效.

一些额外的说明:

• 了解预期成本(哈希映射通常使其更低)之间的差异,最差情况成本(平衡二叉树的O(logn),但如果插入触发哈希数组的重新分配,则哈希映射要高得多)和摊销成本(总成本除以数字)操作或元素;取决于新元素和现有元素的比例).你需要找出哪个更适合你的情况.例如,如果您需要遵守非常低的延迟限制,则重新分配哈希映射可能会太多.

• 找出真正的瓶颈在哪里.与例如IO成本相比,在地图中搜索的成本可能是微不足道的.

• 尝试更专业的地图实施.例如,如果您对地图的密钥有更多了解,可以获得很多.通用地图实现的作者没有这样的知识.

在您的示例中(强烈聚类的32位无符号整数键,例如按顺序分配),您可以使用基于基数的方法.非常简单的例子(威胁它作为插图,不准备使用食谱):

Item *sentinel[65536];  // sentinel page, initialized to NULLs.
Item (*pages[65536])[65536];  // list of pages,
                              // initialized so every element points to sentinel

然后搜索就像:

Item *value = pages[index >> 16][index & 0xFFFF];

需要设置新值时:

if (pages[index >> 16] == sentinel) {
  pages[index >> 16] = allocate_new_null_filled_page();
}
pages[index >> 16][index & 0xFFFF] = value;

• 调整你的地图实现.

  • 例如,每个hash_map人都喜欢提前知道元素的大致数量.它有助于避免不必要的重新分配哈希表和(可能)重新散列所有键.

  • 通过上面的专业示例,您肯定会尝试不同的页面大小或三级版本.

  • 常见的优化是提供专门的内存分配器,以避免小对象的多次分配.