我目前正在处理一个遇到性能问题的嵌入式设备项目。分析找到了一个我想消除的 O(N) 操作。
我基本上有两个数组int A[N]和 short B[N] . A 中的条目是唯一的，并由外部约束排序。最常见的操作是检查一个特定的值 a出现在 A[] .不常见但仍然常见的是对 A[] 元素的更改.新值与之前的值无关。
由于最常见的操作是查找，因此 B[]进来。它是 A[] 中的索引排序数组，这样 A[B[i]] < A[B[j]]当且仅当 i<j .这意味着我可以在 A 中找到值使用二分查找。
当然，当我更新 A[k] ，我必须找到k在 B并将其移动到新位置，以保持搜索顺序。因为我知道 A[k] 的新旧值, 那只是一个 memmove() B[] 的子集k的新旧位置之间.这是我需要修复的 O(N) 操作；由于 A[k] 的旧值和新值基本上是随机的 我平均移动大约 N/2 N/3 个元素。
我查看了 std::make_heap使用 [](int i, int j) { return A[i] < A[j]; }作为谓词。在那种情况下，我可以轻松地制作 B[0]指向 A 的最小元素，并更新 B现在是一个廉价的 O(log N) 再平衡操作。但是，我通常不需要 A 的最小值，我需要查找是否存在任何给定值。这现在是 B 中的 O(N log N) 搜索。 . (我的 N 个元素中有一半位于堆深度 log N，四分之一位于 (log N)-1 等)，这与直接在 A 中的愚蠢 O(N) 搜索相比没有任何改进。 .
考虑到 std::set有 O(log N) 插入和查找，我想说在这里更新和查找应该可以获得相同的性能。但是我该怎么做呢？我需要另外订购 B 吗？ ?不同的类型？
B目前是 short [N]因为A和 B加起来大约是我的 CPU 缓存的大小，而我的主内存要慢得多。从 6*N 到 8*N 字节不是很好，但如果我的查找和更新都达到 O(log N)，仍然可以接受。
最佳答案
如果唯一的操作是 (1) 检查值 'a' 是否属于 A 和 (2) 更新 A 中的值，为什么不使用 哈希表 代替排序数组 B?特别是如果 A 的大小没有增长或缩小并且值只会改变，这将是一个更好的解决方案。哈希表不需要比数组更多的内存。 (或者，不应该将 B 更改为堆，而是将其更改为二叉搜索树，这可以是自平衡的，例如 splay 树或红黑树。但是，树需要 额外的内存，因为左右指针。)
将内存使用量从 6N 增加到 8N 字节的实用解决方案是针对 50% 填充的哈希表，即使用由 2N 个短裤数组组成的哈希表。我建议实现 Cuckoo Hashing 机制(参见 http://en.wikipedia.org/wiki/Cuckoo_hashing )。进一步阅读这篇文章，你会发现通过使用更多的散列函数可以获得超过 50% 的负载因子(即将内存消耗从 8N 降低到 7N)。 "仅使用三个哈希函数将负载增加到 91%。"
来自维基百科:
A study by Zukowski et al. has shown that cuckoo hashing is much faster than chained hashing for small, cache-resident hash tables on modern processors. Kenneth Ross has shown bucketized versions of cuckoo hashing (variants that use buckets that contain more than one key) to be faster than conventional methods also for large hash tables, when space utilization is high. The performance of the bucketized cuckoo hash table was investigated further by Askitis, with its performance compared against alternative hashing schemes.
关于c++ - O(log N) 查找和更新的数据结构，考虑到小型 L1 缓存，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10551808/