Raj*_*pta 2 java collections trove4j guava
我需要一个节省空间的集合来存储大量的基元列表int(大约800,000个整数),这允许快速操作contains()并允许以定义的顺序进行迭代.
contains()检查列表中是否存在int的更快操作是主要优先级,因为这是非常频繁的.
我愿意使用广泛使用和流行的第三方库,如Trove,Guava等.
我从Trove 看了TIntSet,但我相信不管怎样我都不会定义迭代的顺序.
收集的大小约为800,000英镑.集合中的值范围将从0到Integer.Max_VALUE.迭代的顺序实际上应该基于我将值添加到集合的顺序,或者可能是我只提供有序的int []并且它应该以相同的顺序迭代.
作为数据结构,我会选择一个longs数组(我逻辑上将其视为两个整数).high-int部分(位63-32)表示您添加到集合的int值.low-int部分(位31-0)表示迭代时后继的索引.如果您有800.000个唯一整数,则需要创建一个800.000的长数组.
现在,您将数组组织为按值排序的二进制平衡树.左边是较小的值,右边是较高的值.您还需要两个跟踪值:一个int指向要开始迭代的第一个索引,一个int指向最后插入的值的索引.
每当添加新值时,重新组织二进制平衡树并从指向当前添加值的最后一个值(作为索引)更新指针.
将此值(数组和两个int值)包装为您选择的集合.
使用此数据结构,您将获得O(log(n))的搜索性能和两倍于值大小的内存使用量.
| 归档时间： |
|
| 查看次数： |
340 次 |
| 最近记录： |