rda*_*mon 3 sorting algorithm data-structures
我有一个超过十亿的排序整数,你认为哪种数据结构可以利用排序行为？主要目标是更快地搜索项目...
我能想到的选项 -
1)常规二进制搜索树,在中间方法中递归拆分.
2)任何其他平衡的二进制搜索树应该运行良好,但不利用排序的启发式..
提前致谢..
[编辑]
插入和删除是非常罕见的...
另外,除了整数,我必须在节点中存储一些其他信息,我认为普通数组不能这样做,除非它是一个列表对吗？
这实际上取决于您要对数据执行的操作.
如果您只是搜索数据而从不插入或删除任何内容,只需将数据存储在一个巨大的排序数组中就可以了.然后,您可以使用二进制搜索在O(log n)时间内有效地查找元素.然而,插入和删除可能是昂贵的,因为有十亿个整数O(n)会受到伤害.如果您愿意,可以将辅助信息存储在数组本身内,只需将其放在每个整数旁边即可.
但是,如果使用十亿个整数,这可能会占用大量内存,您可能需要切换到使用位向量.然后,您可以在时间O(log U)中对位向量进行二进制搜索,其中U是位数.有十亿个整数,我假设U和n会很接近,所以这不是一个很大的惩罚.根据机器字大小的不同,这可以节省32x到128x内存,而不会造成太大的性能损失.此外,这将增加二进制搜索的位置,并且还可以提高性能.这确实使得实际迭代列表中的数字要慢得多,但它使插入和删除花费O(1)时间.为此,您需要存储一些包含与每个整数关联的数据的二级结构(可能是一个哈希表？).这不是太糟糕,因为一旦找到了您正在寻找的内容,就可以将这个排序的位向量用于排序查询和未排序的哈希表.
如果您还需要在列表中添加和删除值,则平衡的BST可能是一个不错的选择.但是,因为您特别知道存储整数,所以您可能需要查看更复杂的van Emde Boas树结构,它支持O中的插入,删除,前驱,后继,查找最大和查找全部( log log n)时间,它比二叉搜索树快得多.但是,这种方法的实施成本很高,因为数据结构非常难以实现.
您可能想要探索的另一个数据结构是按位trie,它与排序位向量具有相同的时间范围,但允许您将辅助数据与每个整数一起存储.此外,它非常容易实现!
希望这可以帮助!