问题描述
我正在编写一个函数来将两个 Map 合并在一起.这是我目前所拥有的:
I'm writing a function to merge two Map's together. This is what I have so far:
def merge[K, V1, V2, V3](left: Map[K, V1], right: Map[K, V2])
(fn: (Option[V1], Option[V2]) => V3): Map[K, V3] = {
val r = (left.keySet ++ right.keySet) map {
key =>
(key -> fn(left.get(key), right.get(key)))
}
r.toMap
}
函数本身有效.您可以这样使用该函数:
The function itself works. You use the function as so:
val m1 = Map(1 -> "one", 3 -> "three", 5 -> "five")
val m2 = Map(1 -> "I", 5 -> "V", 10 -> "X")
merge(m1, m2) { (_, _) }
// returns:
// Map(1 -> (Some(one),Some(I)),
// 3 -> (Some(three),None),
// 5 -> (Some(five),Some(V)),
// 10 -> (None,Some(X)))
我有两个问题:
- 我担心
.get
和.toMap
调用的计算复杂性.有人可以改进实施吗? - 我想要默认函数来生成一对值 (
{ (_, _) }
).我不太明白正确执行此操作的语法.
- I'm worried about the computational complexity of the
.get
and.toMap
calls. Can anyone improve the implementation? - I'd like the default function to make a pair of the values (
{ (_, _) }
). I can't quite get the syntax to do so properly.
虽然我最初说的是性能,但我的意思是计算复杂度. 看起来我的函数的执行时间大致为 O(n).可以在 O(ln(n)) 中完成吗?
While I originally said performance, I meant computational complexity. Looks like my function performs roughly in O(n). Can it be done in O(ln(n))?
推荐答案
对于默认函数字面量使用:
For the default function literal use:
(fn: (Option[V1], Option[V2]) => V3 =
(x: Option[V1], y: Option[V2]) => Tuple2(x,y))
你必须像这样使用合并:merge(m1,m2)()
You'll have to use merge like this: merge(m1,m2)()
我想说在对实际数据进行一些测量之前不要担心性能.
I would say don't be worried about performance until you perform some measurements on actual data.
关于性能,通过提供视图而不是构建地图,您可以以查找为代价快速构建" - 假设我们正在处理不可变的地图.因此,根据实际数据和用例,您可以为某些操作获得更好的性能,但这需要权衡.
about performance, by providing a view instead of constructing a map you can get quick "construction" at the expense of lookup - assuming we are dealing with immutable maps. So depending on actual data and use case, you can get better performance for certain operations, but it has a trade-off.
class MergedView[K, V1, V2, V3](
left: Map[K, V1], right: Map[K, V2]
)(fn: (Option[V1], Option[V2]) => V3 = (x: Option[V1], y: Option[V2]) => Tuple2(x,y)
) extends collection.DefaultMap[K, V3] {
def get(key: K): Option[V3] = (left.get(key), right.get(key)) match {
case (None, None) => None
case t => Some(fn(t._1, t._2))
}
lazy val tuples = (left.keys ++ right.keys).map(key => key -> get(key).get)
def iterator: Iterator[(K, V3)] = tuples.iterator
}
val r1 = new MergedView(m1, m2)() // use parens here for second param list.
这篇关于地图合并功能的改进的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!