Scala中如何基于List[T]的插入顺序生成Ordering[T]实例

当然可以！我们完全可以基于你给出的优先级列表，实现一个符合需求的Ordering[T]实例，核心思路是给每个元素分配一个优先级分数，然后基于分数的大小来定义排序规则。

实现步骤与代码示例 #

首先，我们可以把列表里的元素和它们的索引绑定（索引越小，优先级越高），然后通过一个映射快速查找元素对应的分数；对于不在列表中的元素，统一分配一个比列表所有元素分数都高的值（这样它们的优先级就最低，且彼此相等）。

// 假设你的优先级列表是这样的
val preferences: List[T] = List(t1, t2, t3)

// 第一步：创建元素到优先级分数的映射，索引越小分数越低（代表优先级越高）
val priorityLookup: Map[T, Int] = preferences.zipWithIndex.toMap

// 第二步：基于分数映射定义Ordering实例
implicit val priorityOrdering: Ordering[T] = Ordering.by { element =>
  // 存在于列表中的元素用索引作为分数，不存在的用列表长度作为分数（比所有列表内元素的分数都大）
  priorityLookup.getOrElse(element, preferences.length)
}

代码解释 #

• zipWithIndex会把列表中的每个元素和它的位置索引配对，比如t1对应0，t2对应1，t3对应2，索引越小代表优先级越高。
• Ordering.by是Scala标准库提供的便捷方法，它接受一个函数（把T转换成可比较的类型，这里是Int），然后基于该类型的自然排序生成Ordering[T]。
• 对于不在preferences里的元素（比如t4、t5），getOrElse会返回preferences.length（也就是3），这个分数比列表内所有元素的分数都大，所以它们的优先级低于t3，而且因为分数相同，互相比较时会被视为相等。

测试验证 #

假设T是String类型，我们来测试一下排序效果：

val preferences: List[String] = List("t1", "t2", "t3")
val priorityLookup: Map[String, Int] = preferences.zipWithIndex.toMap
implicit val priorityOrdering: Ordering[String] = Ordering.by(priorityLookup.getOrElse(_, preferences.length))

// 测试用列表
val testElements = List("t3", "t5", "t1", "t4", "t2")
println(testElements.sorted) 
// 输出结果：List(t1, t2, t3, t5, t4)（t5和t4的顺序可能互换，因为它们优先级相等）

注意事项 #

• 如果T是自定义类型，请确保它正确实现了equals和hashCode方法，否则Map无法正确查找元素的分数。如果无法修改T的实现，对于小列表可以改用遍历查找索引的方式（效率稍低，但可行）：

  implicit val priorityOrdering: Ordering[T] = Ordering.by { element =>
    preferences.indexOf(element) match {
      case -1 => preferences.length
      case idx => idx
    }
  }
  

• 这种实现的效率很高：构建映射是O(n)时间，每次分数查找是O(1)，排序操作的时间复杂度为O(m log m)（m是待排序元素的数量）。

内容的提问来源于stack exchange，提问作者davidrpugh