14

我必须创建一个包含 n 个元素的大列表（最多 100,000 个）。列表中的每个元素都是一个与列表索引等效的整数。在此之后，我必须在此列表上调用 Collections.shuffle。我的问题是，应该使用哪个列表实现（java 集合或 apache 集合）。我的直觉是 ArrayList 可以在这里很好地使用。所有的想法都值得赞赏。谢谢！

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

4

10 回答 10

12

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

于 2009-11-18T14:25:21.640 回答
6

引用自 Collections.shuffle javadoc：

此方法以线性时间运行。如果指定列表没有实现 RandomAccess 接口并且很大，则此实现在打乱之前将指定列表转储到数组中，并将打乱后的数组转储回列表中。这避免了因将“顺序访问”列表改组而导致的二次行为。

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

于 2009-11-18T14:29:32.790 回答
5

制作一个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空间（......在这种情况下绝对没有什么），但它执行的范围检查确实比 "real" 少ArrayList，因此访问会稍微快一些。不过，您可能不会注意到任何事情:)

于 2009-11-18T15:13:51.140 回答
2

ArrayList<T>可能会很好，是的 - 但是你用什么标准来衡量“最好”呢？无论如何它必须有多好？无论这些标准是什么，您在复杂性和“好”之间的权衡是什么？

于 2009-11-18T14:25:36.507 回答
2

Javolution声称拥有 Java 中最快的 List 实现。但是我在这个库中找不到任何 shuffle 实现，所以你必须手动完成。

于 2009-11-18T23:48:46.097 回答
1

Google 的Guava库有一些非常好的原始处理，包括一个Ints.asList()方法返回一个可能被打乱的列表。

Guava 项目仍处于初步部署阶段，尽管代码已经过仔细审查并在 Google 中大量使用。您需要从SVN检索代码并构建 com.google.common.primitive 类。

于 2009-11-19T14:18:42.240 回答
1

这是关于您对有关FastArrayList.

FastArrayList确实实现RandomAccess了，但是 apache 有一个关于这个类的注释说“这个类不是跨平台的。使用它可能会导致某些架构上的意外失败”。

该类FastArrayList( javadoc ) 是一个并发列表类。这就是javadoc所说的：

java.util.ArrayList 的定制实现，旨在在大多数方法调用是只读的而不是结构更改的多线程环境中运行。在“快速”模式下运行时，读取调用是非同步的，写入调用执行以下步骤：

  1. 克隆现有集合
  2. 对克隆进行修改
  3. 用（修改的）克隆替换现有集合

[...]

注意：如果您仅在单个线程中创建和访问 ArrayList，则应直接使用 java.util.ArrayList（不进行同步）以获得最佳性能。

注意：这个类不是跨平台的[由于快速模式和多线程的问题]

现在您的用例（如所述）是单线程的。所以：

  • “跨平台”问题无关紧要，因为它只影响多线程用例。
  • 第一个“注意”（清楚地）说，对于单线程应用程序，最好使用ArrayList.

简而言之，“快速”FastArrayList是相对于（比如说）这样做的：

  List<String> myConcurrentlList = Collections.synchronizedList(new ArrayList<>());

回到你原来的问题。 ArrayList是最简单的快速方法，我怀疑任何其他List课程都会击败它。但是，以下方法 可能更快。

  String[] array = new String[...];
  // populate array
  // shuffle array ... using same algorithm as Collections.shuffle
  for (int i = array.length; i > 1; i--)
      swap(array, i - 1, rnd.nextInt(i));
  }
  List<String> list = Arrays.asList(array);

为什么会更快？因为数组上的交换操作会比ArrayList.

整体会更快吗？很难说。这取决于：

  • 您是否像这样创建/填充数组是/不是额外的工作
  • asList与...相比，包装器上的列表操作的性能是否ArrayList以及您执行的操作等。

我的建议是提防“过早的优化”。

于 2019-07-21T01:53:09.537 回答
1

有一个名为GlueList的新 List 实现，它比 ArrayList 和 LinkedList 快。

免责声明：我已经创建了实现。

于 2015-11-07T10:18:07.480 回答
-1

您还可以使用基于内存映射文件的列表实现。在这样的实现中，列表并不完全存在于内存中，但只有一部分巨大的列表将在内存中处于活动状态。如果您达到堆空间限制（主要在 32 位 jvm 中），您可能需要使用比普通文件 I/O 更快的内存映射文件使列表无缝推送数据。此google 代码中描述了一种此类实现，并在此链接中进行了解释。

于 2013-04-28T12:15:31.247 回答
-1

ArrayList 将是最好的列表。因为数组支持对于交换 shuffle 中使用的元素非常有效。

但是，如果您真的在追求性能，您可能希望考虑使用 int[] 或基于 int[] 的自定义列表，就像所有 List 和 List 标准实现一样，您将装箱和拆箱整数到整数。

这不会是 suffle 的问题，因为这只是重新排序指针，但您可能不需要创建 100,000 个对象。假设您在创建之前知道列表的大小，您可以很容易地创建一个包装原始数组的新 List 类。如果用作 java.util.List ，您仍然需要将任何 get 方法的返回值装箱。

于 2009-11-18T15:06:59.797 回答