3

此 API 调用返回一个可能很大的未排序的 List<String>。我需要对其进行排序、搜索并访问随机元素。目前 List 是由 ArrayList 实现的（我检查了源代码），但在未来的某个未知点，API 开发人员可能会选择切换到 LinkedList 实现（不更改接口）。

对我的程序来说，排序、搜索、访问一个可能很大的 LinkedList 会非常慢且不可接受。因此我需要将 List 转换为 ArrayList 以确保我的程序的实际效率。但是，由于 List 很可能已经是 ArrayList，因此不必要地创建 List 的新 ArrayList 副本将是低效的。

鉴于这些限制，我想出了以下方法将 List 转换为 ArrayList：

private static <T> ArrayList<T> asArrayList(List<T> list) {
  if (list instanceof ArrayList) {
    return (ArrayList<T>) (list);
  } else {
    return new ArrayList<T>(list);
  }
}

我的问题是：这是使用未知实现的列表的最有效方法吗？有没有更好的方法将 List 转换为 ArrayList？有比将 List 转换为 ArrayList 更好的选择吗？

4

4 回答 4

4

你真的不能比你所拥有的更简单了——在我看来，它可能是最有效的。

也就是说，这听起来很像过早的优化——只有当你使用的 API 的作者对LinkedList. 如果您现在担心它，您可能会花费大量时间和精力来规划甚至可能无法实现的未来场景 - 这是最好的时间花在寻找其他需要解决的问题上。大概您将更改 API 版本的唯一时间是在您自己的应用程序的版本之间 - 如果有的话，请在那时处理问题。

于 2012-06-01T15:02:21.370 回答
2

正如您自己看到的那样，代码很简单而且很高效，因为它只在必要时创建一个副本。

所以答案是没有明显更好的选择，除了完全不同类型的解决方案，例如，也可以对您的列表进行排序。

（请记住，很少需要这种级别的优化，所以这不是一个非常常见的问题。）

更新：作为一般规则，只是事后诸葛亮，编写良好的 API 不会返回不适合它们可能包含的数据量的数据类型。这并不是说你应该盲目相信他们，但这并不是一个完全不合理的假设。

于 2012-06-01T15:00:18.183 回答
1

对我的程序来说，排序、搜索、访问一个可能很大的 LinkedList 会非常慢且不可接受。

实际上，情况并没有那么糟糕。IIRC，Collections.sort 方法将列表复制到临时数组，对数组进行排序，clear()原始列表并将数组复制回它。对于足够大的列表，O(NlogN)排序阶段将主导O(N)复制阶段。

于 2012-06-01T15:17:43.090 回答
0

支持有效随机访问的 Java 集合实现了 RandomAccess 标记接口。对于这样的列表，您可以Collections.sort直接在列表上运行。对于没有随机访问的列表，您可能应该使用其中一种方法将列表转储到数组中，对该数组进行toArray排序，然后将其包装到 random-accessList中。

T[] array = (T[])list.toArray(); // just suppress the warning if the compiler worries about unsafe cast
Arrays.sort(array);
List<T> sortedList = Arrays.asList(array);

我认为Arrays.asList实际上创建了一个ArrayList，所以如果你愿意，你可以尝试转换它的结果。

Collections.sort对所有List实现都是有效的，只要它们提供有效的ListIterator. 该方法将列表转储到一个数组中，对其进行排序，然后使用ListIteratorO(n) 将值复制回列表中。

于 2012-06-01T15:17:42.640 回答