并行排序List而不在Java 8中创建临时数组

Question

Java 8提供了java.util.Arrays.parallelSort使用fork-join框架并行排序数组的方法.但是没有相应Collections.parallelSort的排序列表.

我可以使用toArray,对该数组进行排序,并将结果存储在我的列表中,但这会暂时增加内存使用量,如果我使用并行排序已经很高,因为并行排序只能为巨额列表付出代价.而不是内存的两倍(列表加上parallelSort的工作内存),我正在使用三次(列表,临时数组和parallelSort的工作内存).(Arrays.parallelSort文档说"算法需要的工作空间不大于原始数组的大小".)

除了内存使用,Collections.parallelSort对于看起来像是一个相当常见的操作也会更方便.(我倾向于不直接使用数组,所以我肯定比Arrays.parallelSort更经常使用它.)

该库可以测试RandomAccess以避免尝试例如快速排序链表,因此这不能成为故意遗漏的原因.

如何在不创建临时数组的情况下并行对List进行排序？

Answer 1

似乎没有任何直接的方法List在Java 8中并行排序.我认为这根本不困难; 它看起来更像是对我的疏忽.

假设的困难Collections.parallelSort(list, cmp)在于Collections实现对列表的实现或其内部组织一无所知.通过检查Java 7的实现可以看出这一点Collections.sort(list, cmp).正如您所观察到的,它必须将列表元素复制到数组中,对它们进行排序,然后将它们复制回列表中.

这是List.sort(cmp)扩展方法的一大优势Collections.sort(list, cmp).看起来这似乎只是一个小的语法优势,能够写myList.sort(cmp)而不是Collections.sort(myList, cmp).不同之处在于myList.sort(cmp),作为接口扩展方法,可以被特定List实现覆盖.例如,使用ArrayList.sort(cmp)原样对列表进行排序,Arrays.sort()而默认实现实现旧的copyout-sort-copyback技术.

应该可以向具有类似语义parallelSort的List接口添加扩展方法,List.sort但并行进行排序.这将允许ArrayList使用直接进行就地排序Arrays.parallelSort.(我并不完全清楚默认实现应该做什么.执行copyout-parallelSort-copyback可能仍然值得.)因为这将是一个API更改,所以直到Java SE的下一个主要版本才会发生.

至于Java 8解决方案,有几个解决方法,没有一个非常漂亮(通常的解决方法).您可以创建自己的基于数组的List实现并覆盖sort()以并行排序.或者您可以通过反射子类化ArrayList,覆盖sort(),获取elementData数组并调用parallelSort()它.当然,你可以编写自己的List实现并提供一个parallelSort()方法,但是覆盖的优点List.sort()是它可以在普通List接口上工作,你不必修改代码库中的所有代码来使用不同的List子类.

Answer 2

我认为你注定要使用List自己扩充的自定义实现,parallelSort或者更改所有其他代码以将大数据存储在Array类型中.

这是抽象数据类型层的固有问题.它们旨在将程序员与实现细节隔离开来.但是当实现的细节很重要时 - 就像底层存储模型的排序 - 否则精彩的隔离让程序员无能为力.

标准List排序文档提供了一个示例.他们说,在使用mergesort的解释之后

默认实现获取包含此列表中所有元素的数组,对数组进行排序,并迭代此列表,从数组中的相应位置重置每个元素.(这样可以避免因尝试对链接列表进行排序而导致的n2 log(n)性能.)

换句话说,"因为我们不知道a的底层存储模型,List如果我们这样做就无法触及它,我们以一种已知的方式组织一个副本." 带括号的表达式基于以下事实:List链接列表上的"第i个元素访问器"是Omega(n),因此使用它实现的正常数组mergesort将是一个灾难.实际上,在链表上有效地实现mergesort很容易.该List实施者是刚刚从做预防.

并行排序List有同样的问题.标准顺序排序sort在具体List实现中使用自定义s 进行修复.Java人们还没有选择去那里.也许在Java 9中.

Answer 3

只是在这里推测，但我看到通用排序算法更喜欢在数组而不是实例上工作的几个充分理由List：

• 元素访问是通过方法调用执行的。尽管 JIT 可以应用所有优化，即使对于实现 的列表RandomAccess，与可以很好优化的普通数组访问相比，这可能意味着大量开销。
• 许多算法需要将数组的一些片段复制到临时结构中。有一些有效的方法可以复制数组或其片段。List另一方面，任意实例不能轻易复制。必须分配新的列表，这会带来两个问题。首先，这意味着分配一些新对象，这可能比分配数组成本更高。其次，算法必须选择List为这个临时结构分配什么实现。有两个明显的解决方案，两者都不好：要么只选择一些硬编码的实现，例如ArrayList，但它也可以只分配简单的数组（如果我们生成数组，那么如果源也是一个数组，那就容易得多） 。或者，让用户提供一些列表工厂对象，这使得代码变得更加复杂。
• 与上一期相关：由于 API 的设计方式，没有明显的方法可以将一个列表复制到另一个列表中。接口提供的最好的方法List是addAll()方法，但这在大多数情况下可能效率不高（考虑将新列表预先分配到其目标大小，而不是像许多实现那样一一添加元素）。
• 大多数需要排序的列表都足够小，因此另一个副本不会成为问题。

因此，设计者可能首先考虑的是 CPU 效率和代码简单性，而当 API 接受数组时，这很容易实现。某些语言（例如 Scala）具有直接在列表上工作的排序方法，但这是有代价的，并且在许多情况下可能比数组排序效率低（或者有时可能只是在幕后执行数组之间的转换） ）。