Scala：从元组列表构建映射，但如果存在矛盾条目则失败
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5966535/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Scala: build a Map from a List of tuples, but fail if there are contradictory entries
提问by ziggystar
I think this might be a common operation. So maybe it's inside the API but I can't find it. Also I'm interested in an efficient functional/simple solution if not.
我想这可能是一个常见的操作。所以也许它在 API 内部，但我找不到它。如果没有，我也对高效的功能/简单解决方案感兴趣。
Given a sequence of tuples ("a" -> 1, "b" ->2, "c" -> 3)I want to turn it into a map. That's easy using TraversableOnce.toMap. But I want to fail this construction if the resulting map "would contain a contradiction", i.e. different values assigned to the same key. Like in the sequence ("a" -> 1, "a" -> 2). But duplicates shall be allowed.
给定一个元组序列，("a" -> 1, "b" ->2, "c" -> 3)我想把它变成一张地图。使用TraversableOnce.toMap. 但是如果生成的映射“包含矛盾”，即分配给同一个键的不同值，我想使这个构造失败。就像在序列中一样("a" -> 1, "a" -> 2)。但允许重复。
Currently I have this (very imperative) code:
目前我有这个（非常必要的）代码：
def buildMap[A,B](in: TraversableOnce[(A,B)]): Option[Map[A,B]] = {
val map = new HashMap[A,B]
val it = in.toIterator
var fail = false
while(it.hasNext){
val next = it.next()
val old = map.put(next._1, next._2)
fail = old.isDefined && old.get != next._2
}
if(fail) None else Some(map.toMap)
}
Side Question
副题
Is the final toMapreally necessary? I get a type error when omitting it, but I think it should work. The implementation of toMapconstructs a new map which I want to avoid.
最后toMap真的有必要吗？省略时出现类型错误，但我认为它应该可以工作。的实现toMap构造了一个我想避免的新地图。
采纳答案by Moritz
As always when working with Seq[A]the optimal solution performance-wise depends on the concrete collection type.
A general but not very efficient solution would be to fold over an Option[Map[A,B]]:
与往常一样，在使用Seq[A]最佳解决方案时，性能取决于具体的集合类型。一个通用但不是很有效的解决方案是折叠一个Option[Map[A,B]]：
def optMap[A,B](in: Iterable[(A,B)]): Option[Map[A,B]] =
in.iterator.foldLeft(Option(Map[A,B]())) {
case (Some(m),e @ (k,v)) if m.getOrElse(k, v) == v => Some(m + e)
case _ => None
}
If you restrict yourself to using List[A,B]s an optimized version would be:
如果您限制自己使用List[A,B]s，则优化版本将是：
@tailrec
def rmap[A,B](in: List[(A,B)], out: Map[A,B] = Map[A,B]()): Option[Map[A,B]] = in match {
case (e @ (k,v)) :: tail if out.getOrElse(k,v) == v =>
rmap(tail, out + e)
case Nil =>
Some(out)
case _ => None
}
Additionally a less idiomatic version using mutable maps could be implemented like this:
此外，可以像这样实现使用可变映射的不太惯用的版本：
def mmap[A,B](in: Iterable[(A,B)]): Option[Map[A,B]] = {
val dest = collection.mutable.Map[A,B]()
for (e @ (k,v) <- in) {
if (dest.getOrElse(k, v) != v) return None
dest += e
}
Some(dest.toMap)
}
回答by Rex Kerr
Here is a fail-slowly solution (if creating the entire map and then discarding it is okay):
这是一个缓慢失败的解决方案（如果创建整个地图然后丢弃它是可以的）：
def uniqueMap[A,B](s: Seq[(A,B)]) = {
val m = s.toMap
if (m.size == s.length) Some(s) else None
}
Here is a mutable fail-fast solution (bail out as soon as the error is detected):
这是一个可变的快速失败解决方案（一旦检测到错误就退出）：
def uniqueMap[A,B](s: Seq[(A,B)]) = {
val h = new collection.mutable.HashMap[A,B]
val i = s.iterator.takeWhile(x => !(h contains x._1)).foreach(h += _)
if (h.size == s.length) Some(h) else None
}
And here's an immutable fail-fast solution:
这是一个不可变的快速失败解决方案：
def uniqueMap[A,B](s: Seq[(A,B)]) = {
def mapUniquely(i: Iterator[(A,B)], m: Map[A,B]): Option[Map[A,B]] = {
if (i.hasNext) {
val j = i.next
if (m contains j._1) None
else mapUniquely(i, m + j)
}
else Some(m)
}
mapUniquely(s.iterator, Map[A,B]())
}
Edit: and here's a solution using putfor speed (hopefully):
编辑：这是一个put用于速度的解决方案（希望如此）：
def uniqueMap[A,B](s: Seq[(A,B)]) = {
val h = new collection.mutable.HashMap[A,B]
val okay = s.iterator.forall(x => {
val y = (h put (x._1,x._2))
y.isEmpty || y.get == x._2
})
if (okay) Some(h) else None
}
Edit: now tested, and it's ~2x as fast on input that works (returns true) than Moritz' or my straightforward solution.
编辑：现在已经过测试，它的输入速度比 Moritz 或我的简单解决方案快 2 倍（返回 true）。
回答by Antonin Brettsnajdr
Scala 2.9 is near, so why not to take advantage of the combinations method (inspired by Moritz's answer):
Scala 2.9 快到了，所以为什么不利用组合方法（受莫里茨的回答启发）：
def optMap[A,B](in: List[(A,B)]) = {
if (in.combinations(2).exists {
case List((a,b),(c,d)) => a == c && b != d
case _ => false
}) None else Some(in.toMap)
}
scala> val in = List(1->1,2->3,3->4,4->5,2->3)
in: List[(Int, Int)] = List((1,1), (2,3), (3,4), (4,5), (2,3))
scala> optMap(in)
res29: Option[scala.collection.immutable.Map[Int,Int]] = Some(Map(1 -> 1, 2 -> 3, 3 -> 4, 4 -> 5))
scala> val in = List(1->1,2->3,3->4,4->5,2->3,1->2)
in: List[(Int, Int)] = List((1,1), (2,3), (3,4), (4,5), (2,3), (1,2))
scala> optMap(in)
res30: Option[scala.collection.immutable.Map[Int,Int]] = None
回答by Mishael Rosenthal
You can also use gourpBy as follows:
您还可以按如下方式使用 gourpBy：
val pList = List(1 -> "a", 1 -> "b", 2 -> "c", 3 -> "d")
def optMap[A,B](in: Iterable[(A,B)]): Option[Map[A,B]] = {
Option(in.groupBy(_._1).map{case(_, list) => if(list.size > 1) return None else list.head})
}
println(optMap(pList))
It's efficiency is competitive to the above solutions. In fact if you examine the gourpBy implementation you will see that it is very similar to some of the solutions suggested.
它的效率与上述解决方案相比具有竞争力。事实上，如果您检查 gourpBy 实现，您会发现它与建议的一些解决方案非常相似。
