scala - Scala:不可变的 Map 正在改变它的值
问题描述
我正在编写一个代码来确定一个 k 可着色图。我正在使用不可变地图来确定回溯时的顶点颜色。
在 flatMap 循环的第二次交互中,我的 Map 丢失了一个元素。我无法编写一个更简洁的示例来呈现相同的错误,那么这是我的整个代码:
import scala.collection.immutable
import scala.collection.mutable
class GraphUndirected[Vertex](vertices: Set[Vertex], edges: Set[(Vertex, Vertex)]) {
private val adjacencyList: Map[Vertex, Set[Vertex]] =
(
edges.flatMap{ case (a, b) => {Seq( (a, Set(b)), (b, Set(a)))}}
++ vertices.map((_, Set()))
)
.groupBy(_._1)
.mapValues(
_.map(_._2)
.reduce(_ ++ _)
.toSet
)
override def toString(): String = adjacencyList.toString
def kColorable[C](colors: Set[C]): Option[Map[Vertex, C]] = {
vertices.toSeq.view.flatMap( v => {
val colorsMap = immutable.Map[Vertex,C]()
kColorable[C](colors, v, colorsMap)
}).headOption
}
def kColorable[C](colors: Set[C], v: Vertex, colorMap: Map[Vertex, C]): Option[Map[Vertex, C]] = {
println(v, colorMap)
colors.toSeq.view.flatMap( c => {
if (kColorableIsSafe[C](c, v, colorMap)) {
val newColorMap = colorMap + (v -> c)
println("\tnewColorMap", newColorMap)
if (newColorMap.size == vertices.size) {
Some(newColorMap)
} else {
adjacencyList(v).toSeq.view.flatMap( u => {
println("\t\tnewColorMap", newColorMap)
if (newColorMap.contains(u)) {
None
} else {
kColorable[C](colors, u, newColorMap)
}
}).headOption
}
} else {
None
}
}).headOption
}
def kColorableIsSafe[C](c: C, v: Vertex, colorMap: Map[Vertex, C]): Boolean = {
adjacencyList(v).forall( u => {
(!colorMap.contains(u)) ||
(colorMap(u) != c)
})
}
}
val myGraph1 = new GraphUndirected[Int](
Set(1,2,3,4,5,6,7,8,9),
Set(
(1,2),
(3,2), (3,4),
(5,7), (5,9),
(6,4),
(8,2), (8,9)
)
)
println(myGraph1.kColorable[String](Set("BLACK", "WHITE")))
运行此代码将产生:
(5,Map())
( newColorMap,Map(5 -> BLACK))
( newColorMap,Map(5 -> BLACK))
(7,Map(5 -> BLACK))
( newColorMap,Map(5 -> BLACK, 7 -> WHITE))
( newColorMap,Map(5 -> BLACK, 7 -> WHITE))
( newColorMap,Map(5 -> BLACK))
(9,Map(5 -> BLACK))
这对我来说没有意义。在第一次交互中它会打印newColorMap,Map(5 -> BLACK, 7 -> WHITE)
,但在第二次交互中“7->WHITE”消失了newColorMap,Map(5 -> BLACK)
。
newColorMap
不应该是不可变的,不改变它的价值?
我的斯卡拉版本:
$ scala -version
Scala code runner version 2.12.2 -- Copyright 2002-2017, LAMP/EPFL and Lightbend, Inc.
解决方案
你的代码对我来说似乎没有错误。它返回预期的输出。具有欺骗性的是您选择在逐步执行程序时输出程序内部状态的方式。
要了解发生了什么,请尝试运行同一程序的此版本。只需将代码复制并粘贴到 Kcolor.scala 中,将其放入其文件夹并输入
scalac Kcolor.scala
scala Kcolor
这是 Kcolor.scala 的内容
import scala.collection.immutable
object Kcolor extends App {
val myGraph1 = new GraphUndirected[Int](
Set(5,7,9),
Set((5,7), (5,9))
)
println(myGraph1.kColorable[String](Set("BLACK", "WHITE")))
}
class GraphUndirected[Vertex](vertices: Set[Vertex], edges: Set[(Vertex, Vertex)]) {
val adjacencyList: Map[Vertex, Set[Vertex]] =
(
edges.flatMap{ case (a, b) => {Seq( (a, Set(b)), (b, Set(a)))}}
++ vertices.map((_, Set()))
)
.groupBy(_._1)
.mapValues(
_.map(_._2)
.reduce(_ ++ _)
.toSet
)
override def toString(): String = adjacencyList.toString
def kColorable[C](colors: Set[C]): Option[Map[Vertex, C]] = {
vertices.flatMap( v => {
val colorsMap = immutable.Map[Vertex,C]()
kColorable[C](colors, v, colorsMap)
}).headOption
}
def kColorable[C](colors: Set[C], v: Vertex, colorMap: Map[Vertex, C]): Option[Map[Vertex, C]] = {
println(v, colorMap)
val res = colors.flatMap( c => {
if (kColorableIsSafe[C](c, v, colorMap)) {
val newColorMap = colorMap + (v -> c)
println("\tnewColorMap", v, c, newColorMap)
if (newColorMap.size == vertices.size) {
Some(newColorMap)
} else {
val res1 = adjacencyList(v).flatMap( u => {
println("\t\tnewColorMap", u, newColorMap)
if (newColorMap.contains(u)) {
None
} else {
kColorable[C](colors, u, newColorMap)
}
})
println(res1)
res1.headOption
}
} else {
None
}
}).headOption
println("end")
res
}
def kColorableIsSafe[C](c: C, v: Vertex, colorMap: Map[Vertex, C]): Boolean = {
adjacencyList(v).forall( u => {
(!colorMap.contains(u)) ||
(colorMap(u) != c)
})
}
}
我已经包含了输出的前几行:
(5,Map())
( newColorMap,5,BLACK,Map(5 -> BLACK))
( newColorMap,7,Map(5 -> BLACK))
(7,Map(5 -> BLACK))
( newColorMap,7,WHITE,Map(5 -> BLACK, 7 -> WHITE))
( newColorMap,5,Map(5 -> BLACK, 7 -> WHITE))
Set()
end
( newColorMap,9,Map(5 -> BLACK))
(9,Map(5 -> BLACK))
( newColorMap,9,WHITE,Map(5 -> BLACK, 9 -> WHITE))
( newColorMap,5,Map(5 -> BLACK, 9 -> WHITE))
Set()
end
该程序正在做的是它到达 flatMap 的末尾而无法创建彩色地图,并且它正在输出 None。所以线之间
( newColorMap,5,Map(5 -> BLACK, 7 -> WHITE))
和
( newColorMap,9,Map(5 -> BLACK))
它正在到达当前 flatMap 的末尾并跳回到外循环的下一次迭代。
你的程序很有趣。我想起来很开心。感谢分享。
推荐阅读
- node.js - 无法执行 git commit
- python-3.x - OpenNMT 玩具示例(Python3.9)的问题
- javascript - 如何使用ajax在html中显示mySQL数据
- json - 带有 json 数据的 Swagger PHP multipart/form-data
- authentication - API需要HMAC认证JMeter
- r - LightGBM 的 multi_error 和 multi_logloss 度量参数之间的区别的介绍性解释是什么?
- visual-studio - 如何分发 Visual Studio 模板包?
- python - 如何在对象的内存中保持全局状态?
- python - 如何用 numpy 找到 Wronskian 行列式
- mysql - 如何在几天内加入两个 MySQL 表?