如何改进这个 "update" 功能?
How to improve this "update" function?
假设我有 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
功能?
怎么样
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
如果您无法对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.
假设我有 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
功能?
怎么样
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
如果您无法对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.