Scala：最有效地按第三个值对（Int，Int，Int）的ListBuffer进行排序

Question

我希望最有效地按第三个值对 ListBuffer(Int, Int, Int) 进行排序。这就是我目前拥有的。我正在使用 sortBy。注意 y 和 z 都是 ListBuffer[(Int, Int, Int)]，我先把它们区别开来。我的目标是优化它并最有效地执行此操作（取两个列表之间的差异并按第三个元素排序）。我假设 diff 部分无法优化，但 sortBy 可以，所以我正在寻找一种有效的方法来处理排序部分。我找到了关于排序数组的帖子，但我正在使用 ListBuffer 并转换为数组会增加开销，所以我宁愿不转换我的 ListBuffer。

val x = (y diff z).sortBy(i => i._3)

Answer 1

1) 如果您想使用 Scala 库，没有比这更好的了。 Scala 已经尝试以最有效的方式对您的集合进行排序。 SeqLike 定义 def sortBy[B](f: A => B)(implicit ord: Ordering[B]): Repr = sorted(ord on f) 调用此实现：

  def sorted[B >: A](implicit ord: Ordering[B]): Repr = {
    val len = this.length
    val arr = new ArraySeq[A](len)
    var i = 0
    for (x <- this.seq) {
      arr(i) = x
      i += 1
    }
    java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]])
    val b = newBuilder
    b.sizeHint(len)
    for (x <- arr) b += x
    b.result
  }

这就是您的代码将要调用的内容。如您所见，它已经使用数组对数据进行就地排序。根据public static void sort(Object[] a)的javadoc：

Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons.

2) 如果您尝试通过将 diff 结果直接插入到排序结构（如二叉树）中逐个元素地生成它们来进行优化，您仍然会支付相同的价格：插入的平均成本是 log(n) 乘以 n 个元素 = n log(n) - 与合并排序等任何快速排序算法相同。

3) 因此，除非针对您的特定用例进行优化，否则您无法对这种情况进行一般优化。

3a) 例如，ListBuffer 可能会被替换为 Set 而 diff 应该更快。实际上它的实现方式是：

 def diff(that: GenSet[A]): This = this -- that

使用 - 反过来应该比 Seq 上的 diff 更快，后者必须先构建地图：

def diff[B >: A](that: GenSeq[B]): Repr = {
    val occ = occCounts(that.seq)
    val b = newBuilder
    for (x <- this)
      if (occ(x) == 0) b += x
      else occ(x) -= 1
    b.result
  }

3b) 您还可以通过使用 _3 作为数组中的索引来避免排序。如果您使用该索引插入，您的数组将被排序。这仅在您的数据足够密集或您乐于随后处理稀疏数组时才有效。一个索引也可能有多个值映射到它，您也必须处理它。实际上，您正在构建一个排序的地图。您也可以为此使用 Map，但不会对 HashMap 进行排序，并且 TreeMap 将需要 log(n) 再次进行添加操作。

咨询 Scala Collections Performance Characteristics 以了解您可以根据自己的情况获得什么。

4) 总之，排序在现代计算机上确实很快。做一些基准测试以确保您没有过早地优化它。

总结不同场景的复杂性...

您当前的案例：

diff for SeqLike: n 从 that + n 创建地图以迭代 this （地图查找实际上是常数时间（ C)) = 2n 或 O(n)
排序 - O(n log(n))
总计 = O(n) + O(n log(n)) = O(n log(n))，更准确地说：2n + nlog(n)

如果您使用 Set 而不是 SeqLike：

Set 的差异：n 迭代（查找是 C）= O(n)
排序 - 相同
总计 - 相同：O(n) + O(n log(n)) = O(n log(n))，更准确地说：n + nlog(n)

如果使用Set和数组插入：

diff - 与 Set
sort - 0 - 数组按结构排序
总计：O(n) + O(0) = O(n)，更准确地说：n。对于稀疏数据可能不太实用。

看起来在宏伟的计划中它并不重要，除非你有一个独特的案例可以从最后一个选项（数组）中获益。

如果你有一个 ListBuffer[Int] 而不是 ListBuffer[(Int, Int, Int)] 我建议先对两个集合进行排序，然后通过同时对它们进行单次传递来进行比较。这将是 O(nlog(n))。在您的情况下，按 _3 排序不足以保证两个集合中的准确顺序。您可以按元组的所有三个字段进行排序，但这会更改原始顺序。如果您对此感到满意并编写自己的差异，那么它可能是最快的选择。

Scala：最有效地按第三个值对（Int，Int，Int）的ListBuffer进行排序

Scala: Sort a ListBuffer of (Int, Int, Int) by the third value most efficiently

sorting

scala

listbuffer