java中大型列表的最佳List实现是什么

Question

我必须创建一个包含n个元素的大型列表(最多可达100,000个).列表中的每个元素都是一个等于列表索引的整数.在此之后,我必须在此列表上调用Collections.shuffle.我的问题是,应该使用哪个列表实现(java集合或apache集合).我的直觉是ArrayList可以在这里使用.所有的想法都很感激.谢谢!

感谢您的投入.我想我坚持使用ArrayList.我目前正在使用带有initialCapacity参数的ArrayList构造函数,并传递列表的大小.因此,如果原始列表是100000,我使用新的ArrayList(100000)创建这个新列表; 因此我认为我没有创建数组并执行asList,因为不会有任何大小调整.此外,像GrowthList和LazyList这样的大多数apache集合列表都不实现RandomAccess.这肯定会减慢shuffle(根据javadocs).FastArrayList确实实现了RandomAccess,但是apache有一个关于这个类的说明,"这个类不是跨平台的.使用它可能会导致某些体系结构出现意外故障".

Answer 1

ArrayList最有可能每个列表元素的开销最小,因此应该是最佳选择.如果您经常需要删除列表中间的项目,则可能是更糟糕的选择.

Answer 2

引自Collections.shuffle的javadoc:

此方法以线性时间运行.如果指定的列表未实现RandomAccess接口并且很大,则此实现会在将其重新排列之前将指定的列表转储到数组中,并将混洗的数组转储回列表中.这避免了在适当的位置改组"顺序访问"列表所导致的二次行为.

因此,如果您没有其他需求,我会选择实现RandomAccess的ArrayList.

Answer 3

制作一个Integer数组然后用 包装它Arrays.asList可以比常规ArrayList.

List<Integer> makeList(int size){
    if (size < 0) throw new IllegalArgumentException();
    Integer[] arr = new Integer[size];
    for (int i = 0; i < arr.length; ++i) arr[i] = i;
    List<Integer> list = Arrays.asList(arr);
    Collection.shuffle(list);
    return list;
}

您节省了一整套int空间（……诚然，在这种情况下这绝对算不了什么），但它执行的范围检查确实比“真实”少ArrayList，因此访问速度会稍快一些。不过，你可能不会注意到什么:)