19

我目前正在从事一个嵌入式设备项目，我遇到了性能问题。分析找到了一个我想消除的 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()一个子集。这是我需要修复的 O(N) 操作；由于 的新旧值基本上是随机的，我平均移动大约N/2 N/3 个元素。B[]kA[k]

我研究了std::make_heap用作[](int i, int j) { return A[i] < A[j]; }谓词。在那种情况下，我可以很容易地B[0]指出 的最小元素A，并且更新B现在是一个廉价的 O(log N) 重新平衡操作。但是，我通常不需要 A 的最小值，我需要查找是否存在任何给定值。现在这是一个 O(N log N) 搜索B。（我的 N 个元素中有一半位于堆深度 log N，四分之一位于 (log N)-1 等），这与直接在A.

考虑到std::set有 O(log N) 的插入和查找，我想说应该有可能在这里获得相同的性能来进行更新和查找。但是我该怎么做呢？我需要另一个订单B吗？不同的类型？

B目前是short [N]因为A和B一起大约是我的 CPU 缓存的大小，而我的主内存要慢很多。从 6*N 到 8*N 字节不是很好，但如果我的查找和更新都达到 O(log N) 仍然可以接受。

4

3 回答 3

7

如果唯一的操作是 (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%。 "

来自维基百科：

Zukowski 等人的一项研究。已经表明，对于现代处理器上的小型缓存驻留哈希表，布谷鸟哈希比链式哈希要快得多。Kenneth Ross 已经展示了布谷鸟哈希的分桶版本（使用包含多个键的桶的变体）在空间利用率很高的情况下也比传统方法更快地用于大型哈希表。Askitis 进一步研究了桶化杜鹃哈希表的性能，并将其性能与其他哈希方案进行了比较。

于 2012-05-11T13:17:24.380 回答
1

std::set通常使用二叉搜索树提供O(log(n))插入和删除。不幸的是，对于大多数基于指针的实现来说，这使用了 3*N 空间。假设字大小的数据，1 表示数据，2 表示每个节点上左右子节点的指针。

如果你有一些常数 N 并且可以保证它ceil(log2(N))小于字长的一半，你可以使用一个固定长度的树节点数组，每个 2*N 大小。使用1表示数据，1表示两个子节点的索引，存储为单词的上半部分和下半部分。这是否会让您以某种方式使用自平衡二叉搜索树取决于您的 N 和字长。对于 16 位系统，您只能得到 N = 256，但对于 32，它是 65k。

于 2012-05-11T14:14:11.657 回答
0

既然你的 N 有限，你不能std::set<short, cmp, pool_allocator> B和Boostpool_allocator一起使用吗？

于 2012-05-11T14:10:35.897 回答