O(log N)的数据结构查找和更新,考虑小L1缓存

Question

我目前正在开发一个嵌入式设备项目,我遇到了性能问题.分析已经找到了我想要消除的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处等),这与直接在O(N)搜索中没有任何改进A.

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

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

Answer 1

如果唯一的操作是(1)检查值'a'是否属于A和(2)更新A中的值,为什么不使用哈希表代替排序的数组B？特别是如果A不会增大或缩小尺寸而且值只会改变,这将是一个更好的解决方案.哈希表不需要比数组多得多的内存.(或者,B应该更改为堆而不是二进制搜索树,可以自我平衡,例如展开树或红黑树.但是,由于左侧和右侧,树需要额外的内存 -指针.)

增加内存使用从6N到8N字节的实用解决方案是针对准确的50%填充哈希表,即使用由2N短路数组组成的哈希表.我建议实现Cuckoo Hashing机制(参见http://en.wikipedia.org/wiki/Cuckoo_hashing).进一步阅读文章,你会发现你可以通过使用更多的哈希函数来获得超过50%的负载因子(即将内存消耗从8N推向7N)." 仅使用三个散列函数可将负载增加到91%. "

来自维基百科:

Zukowski等人的一项研究.已经表明,对于现代处理器上的小型缓存驻留哈希表,布谷鸟哈希比链式哈希要快得多.Kenneth Ross已经展示了buckoo散列的bucketized版本(使用包含多个密钥的存储桶的变体)比空间利用率高的大型散列表的传统方法更快.Askitis进一步研究了bucketized cuckoo哈希表的性能,并将其性能与其他哈希方案进行了比较.