哪种搜索数据结构最适合排序的整数数据？

Question

哪种搜索数据结构最适合排序的整数数据？

3

我有一个十亿个整数的已排序列表，你认为哪种数据结构可以利用排序后的行为？主要目标是更快地搜索项目...
我能想到的选项 --
1）常规二叉搜索树，使用递归分割中间方法。
2）任何其他平衡的二叉搜索树都应该很好，但不能充分利用排序启发式算法..
提前感谢..
[编辑]
插入和删除非常罕见...
此外，除了整数外，我还需要在节点中存储一些其他信息，我认为普通数组无法做到这一点，除非它是一个列表对吗？

- rda3mon

2

仅搜索？数组同样适用，且浪费更少的空间。当然，它不支持高效的插入/删除操作。 - harold

插入和删除很少发生... - rda3mon

4个回答

2

搜索已排序整数的最佳数据结构是数组。

您可以使用log(N)操作进行搜索，它比树更紧凑（内存开销更小）。

而且您甚至不需要编写任何代码（因此出错的可能性更小） - 只需使用标准库中的bsearch即可。

- Employed Russian

你能解释一下吗？你的意思是说我可以在O(1)时间内完成吗？但是怎么做到的呢？ - rda3mon

1

你无法拥有常数时间，使用二分查找在数组上的时间复杂度为O(logn)。而且数组不需要像树一样指向节点的指针。 - Jesus Ramos

我同意log(N)的观点，难道我不能做得更好吗？ - rda3mon

一般来说，你不能比O(log(N))更好。数组可以有任意数据（bsearch可以搜索结构体数组；或者你可以有第二个“并行”数组来存储额外的数据）。 - Employed Russian

你可以通过插值搜索在平均情况下做得更好！请查看我的答案。 - Simone

2

有了一个已排序的数组，最好的方法是使用插值搜索，平均时间为log(log(n))。它本质上是二分搜索，但不将数组分成相同大小的两个子数组。它非常快速且易于实现。

http://en.wikipedia.org/wiki/Interpolation_search

“不要让最坏情况下O(n)的限制吓到你，因为对于10亿个整数来说，实际上几乎不可能达到这个限制。”

- Simone

好像这取决于数据的某些特征——数据应该是均匀分布的。否则搜索会变成线性的。所以对于这个问题不适用，因为我不能确定它是否均匀... - rda3mon

如果整数的范围是32位整数的范围，那么在0-40亿的范围内有10亿个数字，最坏情况是不可能的。 - Simone

尝试一下吧，只需要5分钟就可以实现。 - Simone

好的，我会尝试。是的，实际上达到O(n)几乎是不可能的，但即使对我来说100也很糟糕，因为BST只需要30次比较。 - rda3mon

要实现线性时间，你必须拥有呈指数分布的数字；例如：2、4、8、16……一直到 2 ^ 1000000000。而这是不可能的。 - Simone

我希望如此。此外，您可以通过简单地切换到二分搜索来避免线性情况的维护平均对数(log(log(n)))和最坏对数(log(n))，如果在经过2 * log(log(n))次细分后，仍然没有找到您正在搜索的数字。 - Simone

1

O(1)解决方案：

假设使用32位整数和大量内存：

一个大约有2³²（40亿个元素）大小的查找表，其中每个索引对应于具有该值的整数数量。

假设使用更大的整数：

一个非常大的哈希表。如果您拥有良好的值分布，则通常的模数哈希函数是合适的，否则，您可能需要将32位策略与哈希查找相结合。

- Captain Giraffe

我认为这对我来说不是一个好的解决方案，因为： 1）哈希需要大量的资源。 2）我不能容忍任何一次碰撞。 3）对于十亿个哈希，我将不得不使用长整型大小的哈希。 - rda3mon

@Ringo 对于第三个问题，完全不需要。普通的32位整数可以很好地工作。对于第一个问题，二分查找更为复杂。而哈希表查询只需要进行一次模运算即可。至于第二个问题，则是为什么？ - Captain Giraffe

对于32位数字，如何才能避免32位哈希冲突？我感觉会有冲突。
我同意BST占用资源（空间），但比较是更便宜的。我可以使用BST的其他一些功能，这些我没有提到。

- rda3mon

@Ringo 如果要求不发生冲突，那么哈希肯定是行不通的。但是，为什么需要这样的要求呢？ - Captain Giraffe

每个项目对我来说都非常重要，如果我失去了任何一个项目，应用程序就没有价值了... 这与事件响应有关... - rda3mon

@Ringo 哈希表不会丢失数据。例如，查看 http://en.wikipedia.org/wiki/Hash_table#Collision_resolution。 - Captain Giraffe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

这真的取决于您想对数据执行什么操作。

如果您只是搜索数据而从不插入或删除任何内容，那么仅将数据存储在一个巨大的排序数组中可能完全没有问题。然后，您可以使用二分查找以O（log n）的时间高效地查找元素。但是，由于十亿个整数的存在，插入和删除可能很昂贵，因为O（n）会受到影响。如果您愿意，您可以在数组本身内部存储辅助信息，只需将其放置在每个整数旁边即可。

但是，对于十亿个整数，这可能过于占用内存，您可能需要切换到使用位向量。然后，您可以在O（log U）的时间内对位向量进行二进制搜索，其中U是位数。对于十亿个整数，我认为U和n将接近，因此这并不会造成太大的损失。根据机器字长的大小，这可以节省32倍到128倍的内存，而不会造成太大的性能损失。此外，这将增加二进制搜索的局部性，并且还可以改善性能。这确实使得实际遍历列表中的数字变得更慢，但是使插入和删除需要O（1）时间。为了做到这一点，您需要存储一些辅助结构（也许是哈希表？），其中包含与每个整数相关联的数据。这并不太糟糕，因为一旦找到要查找的内容，您可以使用此排序的位向量进行排序查询，使用未排序的哈希表。

如果您还需要添加和删除列表中的值，则平衡BST可能是一个不错的选择。但是，由于您特别知道您正在存储整数，因此您可能需要查看更复杂的van Emde Boas树结构，该结构支持插入、删除、前任、后继、查找最大值和查找最小值，所有这些操作都在O（log log n）的时间内完成，这比二叉搜索树快指数倍。然而，这种方法的实现成本很高，因为数据结构非常难以正确实现。

您可能还想探索的另一个数据结构是位字典树，它具有与排序的位向量相同的时间边界，但允许您将辅助数据与每个整数一起存储。此外，它非常容易实现！

希望这可以帮助您！