Distinct Last By

Question

我正在寻找具有以下distinctLastBy方法良好性能的解决方案：

import scala.language.higherKinds
implicit final class SeqPimp[A, S[A] <: Seq[A]](val s: S[A]) extends AnyVal {
  import scala.collection.generic.CanBuildFrom
  import scala.collection.mutable.Builder
  private final def build[B](build: Builder[B, S[B]] => Unit)(implicit cbf: CanBuildFrom[S[A], B, S[B]]): S[B] = {
    val b = cbf()
    build(b)
    b.result
  }
  final def distinctBy[B](f: A => B)(implicit cbf: CanBuildFrom[S[A], A, S[A]]): S[A] = {
    build[A] { builder =>
      val seen = scala.collection.mutable.Set[B]()
      for (a <- s; b = f(a); if !(seen contains b)) {
        seen += b
        builder += a
      }
    }
  }
  final def distinctLastBy[B](f: A => B)(implicit cbf: CanBuildFrom[S[A], A, S[A]]): S[A] = {
    // instead of keeping the first occurence of an element the last one will be kept
    build[A] { builder => builder ++= s.view.reverse.distinctBy(f).reverse }
  }
}

举个例子：

case class Num(integralDigits: Int, fractionalDigits: Int)
val nums = Num(2, 11) :: Num(1, 23) :: Num(1, 45) :: Num(3, 11) :: Num(2, 22) :: Nil
nums distinctLastBy (_.integralDigits) // List(Num(1,45), Num(3,11), Num(2,22))

如果结果元素在原始列表中按第一次出现( by-argument)进行排序，那会很好。

List(Num(2,22), Num(1,45), Num(3,11))

有什么想法吗？

Answer 1

如果您的目标是JVM，那么基于java.util.LinkedHashMap的东西呢？

import java.util.LinkedHashMap
import scala.collection.JavaConversions._

final def distinctLastBy[B](f: A => B)(implicit cbf: CanBuildFrom[S[A], A, S[A]]): S[A] = {
  build[A] { builder =>
    val map = new LinkedHashMap[B, A]
    for (a <- s; b = f(a)) {
      map(b) = a
    }
    builder ++= map.values
  }
}

LinkedHashMap跟踪LinkedList中的插入顺序。当然，我们也可以在纯Scala中做同样的事情：

import scala.collection.mutable.ListBuffer

final class Ref[A](var x: A)

final def pureDistinctLastBy[B](f: A => B)(implicit cbf: CanBuildFrom[S[A], A, S[A]]): S[A] = {
  build[A] { builder =>
    var seen = Map.empty[B, Ref[A]]
    val listBuf = ListBuffer.empty[Ref[A]]
    for (a <- s; b = f(a)) {
      seen.get(b) match {
        case Some(ref) => ref.x = a
        case None =>
          val ref = new Ref(a)
          seen += b -> ref
          listBuf += ref
      }
    }
    builder ++= listBuf.view.map(_.x)
  }
}

Ref使我们不必在使用新信息更新列表时搜索列表。这些Ref会让任何函数式编程爱好者感到不安，因此我们可以使用Map seen来跟踪列表中项目的位置，而不是存储对它们的引用：

final def functionalDistinctLastBy[B](f: A => B)(implicit cbf: CanBuildFrom[S[A], A, S[A]]): S[A] = {
  build[A] { builder =>
    val (seen, list) = ((Map.empty[B, Int], IndexedSeq.empty[A]) /: s){(acc, a) =>
      val (innerSeen, innerList) = acc
      val b = f(a)
      innerSeen.get(b) match {
        case Some(i) => (innerSeen, innerList.updated(i, a))
        case None => (innerSeen + (b -> innerList.size), innerList :+ a)
      }
    }
    builder ++= list
  }
}

尽管我怀疑它不会像命令式版本那样快。

Answer 2

如果你想保持一个使用构建器的实现，我只能确认@James_pic的答案。如果您希望最后对密钥进行排序，请考虑使用SortedMap。

另一种更轻量级的代码是：

nums.groupBy(_.integralDigits).map(_._2.last)