时间戳

首页 > 解决方案 > 如何在 Scala 中从 List[T] 创建 Ordering[T]

scala - 如何在 Scala 中从 List[T] 创建 Ordering[T]

问题描述

假设我有以下列表

val preferences: List[T] = List(t1, t2, t3)

对于我的应用程序，插入元素preferences的顺序意味着首选元素的顺序（即，最喜欢的元素Preferences[T]是t1，最不喜欢的元素是t3，并且t2是首选t3但不是t1。T不包括在的元素preferences，比如说t4和t5, 将不如t3但会被视为彼此相等。

有没有办法Ordering[T]根据插入顺序派生一个实例List[T]？

标签： scala

解决方案

您可以使用伴随对象Ordering上的方法实现自定义 s 。Ordering例如 order by List，您必须比较此列表中元素的索引：

def listBasedOrdering[T](list: List[T]): Ordering[T] = {
  Ordering.by[T, Int] { t =>
    val index = list.indexOf(t)
    if (index == -1) list.size else index
  }
}

List如果它很小，这应该可以很好地工作。但是该indexOf操作使用线性时间，因此对于较大的列表，您可能需要Map预先将其转换为：

def listBasedOrdering[T](list: List[T]): Ordering[T] = {
  val map = list.zipWithIndex.toMap.withDefaultValue(list.size)
  Ordering.by[T, Int](map)
}

这是一个小测试：

scala> implicit val ord = listBasedOrdering(List("t1", "t2", "t3"))
ord: Ordering[String] = scala.math.Ordering$$anon$9@95cecc5

scala> List("t5", "t3", "t2", "t1", "t0").sorted
res0: List[String] = List(t1, t2, t3, t5, t0)

推荐阅读