algorithm - 在 Scala 中，根据复合键对列表进行排序的正确方法是什么

Question

我正在尝试从列表中获取前 N-1 个元素。我在 SO 中浏览过类似的帖子，比如 here和 here .我了解这些帖子中提出的解决方案背后的动机。但是，我认为我的问题有点不同。

我有一些元素的排序(降序)列表。让我们假设它已经以一种有效的方式进行了排序，因为这不是这里的重点。

head 是我得到的最上面的。但是，列表的其余部分有 0 个或多个重复项。这些副本中每一个的 attr1 都与 head 的相同。我想提取这些重复项(如果有的话)。然后我想根据第二个属性 attr2 对这个(顶部 + 重复项)列表进行排序。换句话说，我想对复合​​键进行排序:首先按 Key_1，然后 - 对于同一个 Key_1 - 按 Key_2。

假设列表中的一个元素是一对。

case class PairOfAttrs(val int attr1,val int attr2)

/* .. more code here ... */

// Now, we obtain a sorted (descending) list of PairOfAttrs below
// Ordering is based on the value of attr1 (key_1)
val sortedPairsFirstAttr = .. // Seq(Pair1,Pair2,Pair3,Pair4....Pairn)

val top = sortedPairsFirstAttr.head

很明显，top的attr1是列表中最高的。要提取重复项，我会:

val otherToppers = sortedPairsFirstAttr.tail.filter 
                   (e => e.attr1 == topper.attr1) // Expression(1)

恕我直言，这是关键点。在隔离顶部并在比较期间使用其属性 (attr1) 之前，我无法找到重复项。

// Then, I create a new list of the toppers only

val semiToppers = if (!otherToppers.empty) {
                        List(topper) ++ otherToppers // Expression(2)
                  }

然后，我对结果列表进行排序。排序是根据attr2(Key_2)的值

val finalToppers = semiToppers.sortWith(_._2 < _.2) // Expression(3)

因此，实际上，我使用复合键对原始列表进行了排序:在 Key_1 上降序排序，然后，在 Key_2 上升序排序。

我知道 Experssion(1) 可以针对长列表进行优化；我不需要遍历整个列表。我可以早点摆脱它。我也明白 Expression(2) 和 Expression(3) 可以合并。所以，我们可以把这两点放在一边。

我的问题是我的方法在功能上是否合适且可以接受。如果不是，那么您认为什么是更好、更惯用的方法？

这是一个学习者的问题。因此，我竭诚征求您的意见/意见。

Answer 1

您的解决方案有效且有效，因此我不会对此发表评论。您已经使用了 val 和不可变数据结构，这是实现它的纯粹方式。相反，我会建议一种替代方法，该方法稍微更短并且您可能也会感兴趣:

既然你预处理了你的列表，我建议你对它进行排序lexicographically首先:首先下降 attr1，如果出现平局，则上升 attr2:

scala> val originalList = Seq((1,0), (2,7), (3,1), (1,3), (2,5), (3,4), (3,2))
scala> val lst = originalList.sortBy(x => (-x._1, x._2))
lst: Seq[(Int, Int)] = List((3,1), (3,2), (3,4), (2,5), (2,7), (1,0), (1,3))

现在你只需要从前面取出重复项，结果已经按 attr2 排序:

scala> lst.takeWhile(_._1 == lst.head._1)
res8: Seq[(Int, Int)] = List((3,1), (3,2), (3,4))