Scala: 在列表中查找并更新一个元素

Question

我正在尝试找到一种优雅的方式来实现以下操作:

val l = List(1,2,3)

val (item, idx) = l.zipWithIndex.find(predicate)

val updatedItem = updating(item)

l.update(idx, updatedItem)

我可以在一次操作中完成所有任务吗？查找项目，如果存在则用更新后的值替换并保留原位置。

我可以这样做：

l.map{ i => 
  if (predicate(i)) {
     updating(i)
  } else {
     i
  }
}

但那看起来很丑陋。

另一个复杂性在于，我想仅更新与predicate匹配的第一个元素。

编辑：尝试：

implicit class UpdateList[A](l: List[A]) {
  def filterMap(p: A => Boolean)(update: A => A): List[A] = {
    l.map(a => if (p(a)) update(a) else a)
  }

  def updateFirst(p: A => Boolean)(update: A => A): List[A] = {
    val found = l.zipWithIndex.find { case (item, _) => p(item) }
    found match {
      case Some((item, idx)) => l.updated(idx, update(item))
      case None => l
    }
  }
}

- Wonay

---

我刚刚意识到问题哈哈。我只想在找到的第一项上执行它。 - Wonay

考虑到我只能想到使用可变变量来跟踪是否已经进行了更新，并使用 if (!alreadyUpdated && predicate(i)) 进行映射 - 您可以将所有内容封装在一个方法中，以避免暴露可变变量。对于完全不可变的解决方案，我会使用 foldLeft，其中您累积新的 List (向后) 和 alreadyUpdated 标志，在折叠之后，您可以提取 List 然后反转它 - 但是它的复杂度为 2O(N) _(两次迭代)_，可能过于复杂。不确定是否有更好的方法，这就是为什么我没有回答的原因。 - Luis Miguel Mejía Suárez

那我觉得我的 updateFirst 方法到目前为止是最好的了？ - Wonay

Wonay，在我看来不行。虽然意图非常明确——但它会进行大量迭代（如果第一个元素接近结尾，则为O(3N)），并创建一个额外的中间集合。如果您确定集合很小且第一个项目接近开头，则可能不会那么糟糕。 Aki，我认为这不是一个好主意，因为他/她也需要该元素，因此还需要使用该索引调用apply，这将导致另一次迭代——但会使意图更加清晰！这是一个重点！另一个想法是使用Vector而不是List。 - Luis Miguel Mejía Suárez

那在使用向量时该怎么做呢？ - Wonay

Answer 1

使用.indexWhere()可以避免使用.zipWithIndex()。

为了提高复杂度，使用Vector使得l(idx)变成有效的常数时间。

val l = Vector(1,2,3)
val idx = l.indexWhere(predicate)
val updatedItem = updating(l(idx))
l.updated(idx, updatedItem)

使用scala.collection.immutable.Vector而不是List的原因： Scala的List是一个链表，这意味着数据的访问时间为O(n)。Scala的Vector是索引的，这意味着数据可以在有效的常数时间内从任何点读取。

如果您只修改非常大的集合中的一个元素，则还可以考虑可变集合。

参考链接：https://docs.scala-lang.org/overviews/collections/performance-characteristics.html

- Leighton Ritchie

---

这并不比作者的代码更好，因为 l(idx) 的时间复杂度是 O(N)。 - SergGr

你介意用向量编辑你的解决方案吗？会有任何代码更改还是只是性能上的变化？ - Wonay

正如Leighton所说，代码不会改变，但性能会稍微提高。然而请注意，Vectors并不像人们期望的那样出色。详情请见：http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html#vectors-are-ok - Luis Miguel Mejía Suárez

Answer 2

我不知道任何一种方法可以在不使用可变变量的情况下完成集合的一次遍历。使用两次遍历，您可以使用foldLeft来完成，例如：

def updateFirst[A](list:List[A])(predicate:A => Boolean, newValue:A):List[A] = {
   list.foldLeft((List.empty[A], predicate))((acc, it) => {acc match {
     case (nl,pr) => if (pr(it)) (newValue::nl, _ => false) else (it::nl, pr)
   }})._1.reverse
}

思路是foldLeft允许通过迭代传递附加数据。在这个特定的实现中，我将谓词更改为始终返回false的固定值。不幸的是，你不能以有效的方式从头部构建一个List，因此需要进行另一次reverse。

我相信使用map和var的组合如何实现是显而易见的。 注意：List.map的性能与仅对列表进行单次遍历的性能相同，因为内部标准库是可变的。特别是cons类::声明为

final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] {

所以，tl 实际上是一个 var，这被 map 实现利用，以一种高效的方式从头部构建列表。该字段为 private[scala]，因此您无法从标准库之外使用相同的技巧。不幸的是，我没有看到任何其他 API 调用允许使用此功能将问题的复杂性减少到单个传递。

- SergGr