1

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

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

1 回答 1

5

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
  }

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

实现说明：此实现是一种稳定的、自适应的、迭代的归并排序，当输入数组部分排序时，它需要远少于 n 次 lg(n) 的比较，同时在输入数组随机排序时提供传统归并排序的性能。如果输入数组接近排序，则实现需要大约 n 次比较。

2）如果您尝试通过将差异结果直接插入到像二叉树这样的排序结构中来进行优化，因为您逐个元素地生成它们，您仍然会付出相同的代价：插入的平均成本是元素的log(n)倍数- 与任何快速排序算法，如归并排序。n= n log(n)

3）因此，除非您针对特定用例进行优化，否则您无法普遍优化此案例。

3a)例如，ListBuffer可能被替换为 aSet并且diff应该更快。事实上，它被实现为：

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

which uses -which 反过来应该比diffwhich Seqhas first build a map 更快：

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作为数组中的索引来避免排序。如果您使用该索引插入，您的数组将被排序。这仅在您的数据足够密集或者您乐于事后处理稀疏数组时才有效。一个索引也可能有多个映射到它的值，您也必须处理它。实际上，您正在构建一个排序的地图。您也可以使用 a Map，但 aHashMap不会被排序，并且 aTreeMap将需要log(n)再次进行添加操作。

请参阅 Scala 集合性能特征，以了解根据您的案例可以获得什么。

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：

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

如果使用Setand 数组插入：

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

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

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

于 2016-11-21T06:47:54.287 回答