如何改进这个 "update" 功能？

Question

假设我有 case class A(x: Int, s: String) 并且需要像这样使用 Map[Int, String] 更新 List[A]：

def update(as: List[A], map: Map[Int, String]): List[A] = ???

val as = List(A(1, "a"), A(2, "b"), A(3, "c"), A(4, "d"))
val map = Map(2 -> "b1", 4 -> "d1", 5 -> "e", 6 -> "f")
update(as, map) // List(A(1, "a"), A(2, "b1"), A(3, "c"), A(4, "d1"))

我这样写update:

def update(as: List[A], map: Map[Int, String]): List[A] = {

  @annotation.tailrec
  def loop(acc: List[A], rest: List[A], map: Map[Int, String]): List[A] = rest match {
    case Nil => acc
    case as => as.span(a => !map.contains(a.x)) match {
      case (xs, Nil) => xs ++ acc
      case (xs, y :: ys) => loop((y.copy(s = map(y.x)) +: xs) ++ acc, ys, map - y.x)
    }
  }

  loop(Nil, as, map).reverse
}

这个函数工作正常，但不是最理想的，因为它在 map 为空时继续遍历输入列表。此外，它看起来过于复杂。您建议如何改进此 update 功能？

Answer 1

怎么样

def update(as: List[A], map: Map[Int, String]): List[A] =
  as.foldLeft(List.empty[A]) { (agg, elem) =>
    val newA = map
      .get(elem.x)
      .map(a => elem.copy(s = a))
      .getOrElse(elem)
    newA :: agg
  }.reverse

Answer 2

如果您无法对List和Map做出任何假设。那么最好的办法就是迭代前者，以最简单的方式突出一次；也就是说，使用 map 函数。

list.map { a =>
  map
    .get(key = a.x)
    .fold(ifEmpty = a) { s =>
      a.copy(s = s)
   }
}

但是，当且仅当，您可以确定大部分时间：

列表会很大。
地图会很小。
Map 中的键是 List.
并且所有操作将更接近 List 的头部而不是尾部。

那么，您可以使用下面的方法，在这种情况下应该更有效。

def optimizedUpdate(data: List[A], updates: Map[Int, String]): List[A] = {
  @annotation.tailrec
  def loop(remaining: List[A], map: Map[Int, String], acc: List[A]): List[A] =
    if (map.isEmpty) acc reverse_::: remaining
    else remaining match {
      case a :: as =>
        map.get(key = a.x) match {
          case None =>
            loop(
              remaining = as,
              map,
              a :: acc
            )
          
          case Some(s) =>
            loop(
              remaining = as,
              map = map - a.x,
              a.copy(s = s) :: acc
            )
        }
      
      case Nil =>
        acc.reverse
    }
  
  loop(remaining = data, map = updates, acc = List.empty)
}

但是请注意，代码不仅更长而且更难理解。
它实际上比map解决方案（如果不满足条件）效率低；这是因为 stdlib 实现 "cheats" 并构造 List 我改变它的 tail 而不是向后构建它然后 reversing 和我们一样。

无论如何，与任何性能一样，唯一真正的答案是基准测试。
但是，为了清晰起见，我会选择 map 解决方案，如果您真的需要速度，我会选择可变方法。

可以看到代码运行 here.

如何改进这个 "update" 功能？

How to improve this "update" function?

scala

collections

tail-recursion