当您将相互链接的 object 影响到此列表时，如何维护一个不可变列表
How to maintain an immutable list when you impact object linked to each other into this list
我正在尝试使用 Scala 以不可变的方式编写 NSGA2 中使用的 Deb 的快速非支配排序算法 (NDS)。
但是这个问题似乎比我想象的要难，所以我在这里简化问题来做一个MWE。
想象一下人口 Seq[A]，每个 A 元素是 decoratedA 和一个列表，该列表包含指向人口 Seq[A].[=57 的其他元素的指针=]
函数evalA(a:decoratedA)获取它包含的linkedA列表，并递减每个的值。
接下来我获取人口 A 的子集列表 decoratedAPopulation，并对每个子集调用 evalA。我有一个问题，因为在这个子集列表 decoratedAPopulation 上的元素的每次迭代之间，我需要用新的 decoratedA 和新更新的 linkedA 更新我的 A 人口它包含...
更有问题，人口的每个元素都需要更新 'linkedA' 以替换链接元素，如果它发生变化 ...
哼哼，如你所见，用这种方式保持所有链表同步似乎很复杂。我提出了另一个解决方案 bottom，它可能需要在每个 EvalA 替换元素的新 Population 之后递归到 return。
我怎样才能以不变的方式正确地做到这一点？
以可变方式编写代码很容易，但我没有找到以不可变方式执行此操作的好方法，您有方法或想法吗？
object test extends App{
case class A(value:Int) {def decrement()= new A(value - 1)}
case class decoratedA(oneAdecorated:A, listOfLinkedA:Seq[A])
// We start algorithm loop with A element with value = 0
val population = Seq(new A(0), new A(0), new A(8), new A(1))
val decoratedApopulation = Seq(new decoratedA(population(1),Seq(population(2),population(3))),
new decoratedA(population(2),Seq(population(1),population(3))))
def evalA(a:decoratedA) = {
val newListOfLinked = a.listOfLinkedA.map{e => e.decrement()
new decoratedA(a.oneAdecorated,newListOfLinked)}
}
def run()= {
//decoratedApopulation.map{
// ?
//}
}
}
更新一：
关于初始算法的输入/输出。
Deb 算法的第一部分（步骤 1 到 步骤 3）分析一个 Individual 列表，并为每个 A 计算： (a) 支配计数，支配我的 A 的数量（A 的 value 属性） (b) 支配我的 A 的列表（listOfLinkedA）。
所以它 return 一个 decoratedA 的种群完全初始化，并且对于第 4 步（我的问题）的入口，我采用第一个非支配前沿，cf。 decoratedA 的元素子集 A 值 = 0。
我的问题从这里开始，decoratedA 的列表 A 值 = 0；我通过计算每个 A
的每个 listOfLinkedA 来搜索此列表的下一个前沿
在第 4 步到第 6 步之间的每次迭代中，我需要计算 decoratedA 的新 B 子集列表，其中 A 值 = 0。对于每个，我首先递减将每个元素的支配计数属性转化为listOfLinkedA，然后我过滤得到等于0的元素。A步骤6结束，B被保存到列表List[Seq[DecoratedA]]，然后我重新开始步骤4与 B，并计算一个新的 C，等等
在我的代码中类似的东西，我为 B 的每个元素调用 explore()，Q 在末尾等于 decoratedA 的新子集 value（此处健身）= 0 :
case class PopulationElement(popElement:Seq[Double]){
implicit def poptodouble():Seq[Double] = {
popElement
}
}
class SolutionElement(values: PopulationElement, fitness:Double, dominates: Seq[SolutionElement]) {
def decrement()= if (fitness == 0) this else new SolutionElement(values,fitness - 1, dominates)
def explore(Q:Seq[SolutionElement]):(SolutionElement, Seq[SolutionElement])={
// return all dominates elements with fitness - 1
val newSolutionSet = dominates.map{_.decrement()}
val filteredSolution:Seq[SolutionElement] = newSolutionSet.filter{s => s.fitness == 0.0}.diff{Q}
filteredSolution
}
}
算法结束，我有一个 decoratedA List[Seq[DecoratedA]] 的最终序列列表，其中包含我计算的所有前沿。
更新 2
从此示例中提取的值示例。
我只采用 pareto 前沿（红色）和 {f,h,l} 下一个前沿，支配计数 = 1。
case class p(x: Int, y: Int)
val a = A(p(3.5, 1.0),0)
val b = A(p(3.0, 1.5),0)
val c = A(p(2.0, 2.0),0)
val d = A(p(1.0, 3.0),0)
val e = A(p(0.5, 4.0),0)
val f = A(p(0.5, 4.5),1)
val h = A(p(1.5, 3.5),1)
val l = A(p(4.5, 1.0),1)
case class A(XY:p, value:Int) {def decrement()= new A(XY, value - 1)}
case class ARoot(node:A, children:Seq[A])
val population = Seq(
ARoot(a,Seq(f,h,l),
ARoot(b,Seq(f,h,l)),
ARoot(c,Seq(f,h,l)),
ARoot(d,Seq(f,h,l)),
ARoot(e,Seq(f,h,l)),
ARoot(f,Nil),
ARoot(h,Nil),
ARoot(l,Nil))
算法returnList(List(a,b,c,d,e), List(f,h,l))
更新 3
2 小时后，以及一些模式匹配问题（嗯...），我将返回完整的示例，该示例自动计算支配计数器，以及每个 ARoot 的 children。
但是我有同样的问题，我的children列表计算并不完全正确，因为每个元素A可能是另一个ARoot children列表的共享成员，所以我需要考虑你修改它的答案：/此时我只计算 Seq[p] 的 children 列表，我需要 seq[A]
的列表
case class p(x: Double, y: Double){
def toSeq():Seq[Double] = Seq(x,y)
}
case class A(XY:p, dominatedCounter:Int) {def decrement()= new A(XY, dominatedCounter - 1)}
case class ARoot(node:A, children:Seq[A])
case class ARootRaw(node:A, children:Seq[p])
object test_Whosebug extends App {
val a = new p(3.5, 1.0)
val b = new p(3.0, 1.5)
val c = new p(2.0, 2.0)
val d = new p(1.0, 3.0)
val e = new p(0.5, 4.0)
val f = new p(0.5, 4.5)
val g = new p(1.5, 4.5)
val h = new p(1.5, 3.5)
val i = new p(2.0, 3.5)
val j = new p(2.5, 3.0)
val k = new p(3.5, 2.0)
val l = new p(4.5, 1.0)
val m = new p(4.5, 2.5)
val n = new p(4.0, 4.0)
val o = new p(3.0, 4.0)
val p = new p(5.0, 4.5)
def isStriclyDominated(p1: p, p2: p): Boolean = {
(p1.toSeq zip p2.toSeq).exists { case (g1, g2) => g1 < g2 }
}
def sortedByRank(population: Seq[p]) = {
def paretoRanking(values: Set[p]) = {
//comment from @dk14: I suppose order of values isn't matter here, otherwise use SortedSet
values.map { v1 =>
val t = (values - v1).filter(isStriclyDominated(v1, _)).toSeq
val a = new A(v1, values.size - t.size - 1)
val root = new ARootRaw(a, t)
println("Root value ", root)
root
}
}
val listOfARootRaw = paretoRanking(population.toSet)
//From @dk14: Here is convertion from Seq[p] to Seq[A]
val dominations: Map[p, Int] = listOfARootRaw.map(a => a.node.XY -> a.node.dominatedCounter) //From @dk14: It's a map with dominatedCounter for each point
val listOfARoot = listOfARootRaw.map(raw => ARoot(raw.node, raw.children.map(p => A(p, dominations.getOrElse(p, 0)))))
listOfARoot.groupBy(_.node.dominatedCounter)
}
//Get the first front, a subset of ARoot, and start the step 4
println(sortedByRank(Seq(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)).head)
}
关于区分前沿的问题（更新 2 后）：
val (left,right) = population.partition(_.node.value == 0)
List(left, right.map(_.copy(node = node.copy(value = node.value - 1))))
这里不需要改变任何东西。 copy 将复制除您用新值指定的字段以外的所有内容。谈到代码，新副本将链接到相同的子列表，但是新 value = value - 1.
P.S。我有一种感觉，你可能真的想做这样的事情：
case class A(id: String, level: Int)
val a = A("a", 1)
val b = A("b", 2)
val c = A("c", 2)
val d = A("d", 3)
clusterize(List(a,b,c,d)) === List(List(a), List(b,c), List(d))
实现起来很简单：
def clusterize(list: List[A]) =
list.groupBy(_.level).toList.sortBy(_._1).map(_._2)
测试：
scala> clusterize(List(A("a", 1), A("b", 2), A("c", 2), A("d", 3)))
res2: List[List[A]] = List(List(A(a,1)), List(A(b,2), A(c,2)), List(A(d,3)))
P.S.2。请考虑更好的命名约定，例如 here.
谈论一些复杂结构中的 "mutating" 个元素：
"immutable mutating" 某些共享（结构的各个部分之间）值的想法是将您的 "mutation" 与结构分开。或者简单地说，分而治之：
- 提前计算变化
- 应用它们
代码：
case class A(v: Int)
case class AA(a: A, seq: Seq[A]) //decoratedA
def update(input: Seq[AA]) = {
//shows how to decrement each value wherever it is:
val stats = input.map(_.a).groupBy(identity).mapValues(_.size) //domination count for each A
def upd(a: A) = A(a.v - stats.getOrElse(a, 0)) //apply decrement
input.map(aa => aa.copy(aa = aa.seq.map(upd))) //traverse and "update" original structure
}
因此，我介绍了新的 Map[A, Int] 结构，它展示了如何修改原始结构。这种方法基于 Applicative Functor concept. In general case, it should be Map[A, A => A] or even Map[K, A => B] or even Map[K, Zipper[A] => B] as applicative functor (input <*> map). *Zipper (see 1, 2) 的高度简化版本，实际上可以为您提供有关当前元素上下文的信息。
备注：
我假设A具有相同值的是相同的；这是案例类的默认行为，否则您需要提供一些额外的 id（或重新定义 hashCode/equals）。
如果你需要更多的层次 - 比如 AA(AA(AA(...)))) - 只需使 stats 和 upd 递归，如果递减的权重取决于嵌套级别 - 只需添加嵌套级别作为递归函数的参数。
如果减量取决于父节点（比如只减量 A(3) 的，它属于 A(3)） - 添加父节点作为 [=27 的一部分=] 的密钥并在 upd.
如果统计数据计算（减少多少）之间存在某种依赖关系，比如 input(1) 与 input(0) - 您应该使用 foldLeft 和部分统计数据作为累加器：val stats = input.foldLeft(Map[A, Int]())((partialStats, elem) => partialStats ++ analize(partialStats, elem))
顺便说一句，这里需要 O(N)（线性内存和 cpu 用法）
示例：
scala> val population = Seq(A(3), A(6), A(8), A(3))
population: Seq[A] = List(A(3), A(6), A(8), A(3))
scala> val input = Seq(AA(population(1),Seq(population(2),population(3))), AA(population(2),Seq(population(1),population(3))))
input: Seq[AA] = List(AA(A(6),List(A(8), A(3))), AA(A(8),List(A(6), A(3))))
scala> update(input)
res34: Seq[AA] = List(AA(A(5),List(A(7), A(3))), AA(A(7),List(A(5), A(3))))
我正在尝试使用 Scala 以不可变的方式编写 NSGA2 中使用的 Deb 的快速非支配排序算法 (NDS)。
但是这个问题似乎比我想象的要难，所以我在这里简化问题来做一个MWE。
想象一下人口 Seq[A]，每个 A 元素是 decoratedA 和一个列表，该列表包含指向人口 Seq[A].[=57 的其他元素的指针=]
函数evalA(a:decoratedA)获取它包含的linkedA列表，并递减每个的值。
接下来我获取人口 A 的子集列表 decoratedAPopulation，并对每个子集调用 evalA。我有一个问题，因为在这个子集列表 decoratedAPopulation 上的元素的每次迭代之间，我需要用新的 decoratedA 和新更新的 linkedA 更新我的 A 人口它包含...
更有问题，人口的每个元素都需要更新 'linkedA' 以替换链接元素，如果它发生变化 ...
哼哼，如你所见，用这种方式保持所有链表同步似乎很复杂。我提出了另一个解决方案 bottom，它可能需要在每个 EvalA 替换元素的新 Population 之后递归到 return。
我怎样才能以不变的方式正确地做到这一点？
以可变方式编写代码很容易，但我没有找到以不可变方式执行此操作的好方法，您有方法或想法吗？
object test extends App{
case class A(value:Int) {def decrement()= new A(value - 1)}
case class decoratedA(oneAdecorated:A, listOfLinkedA:Seq[A])
// We start algorithm loop with A element with value = 0
val population = Seq(new A(0), new A(0), new A(8), new A(1))
val decoratedApopulation = Seq(new decoratedA(population(1),Seq(population(2),population(3))),
new decoratedA(population(2),Seq(population(1),population(3))))
def evalA(a:decoratedA) = {
val newListOfLinked = a.listOfLinkedA.map{e => e.decrement()
new decoratedA(a.oneAdecorated,newListOfLinked)}
}
def run()= {
//decoratedApopulation.map{
// ?
//}
}
}
更新一：
关于初始算法的输入/输出。
Deb 算法的第一部分（步骤 1 到 步骤 3）分析一个 Individual 列表，并为每个 A 计算： (a) 支配计数，支配我的 A 的数量（A 的 value 属性） (b) 支配我的 A 的列表（listOfLinkedA）。
所以它 return 一个 decoratedA 的种群完全初始化，并且对于第 4 步（我的问题）的入口，我采用第一个非支配前沿，cf。 decoratedA 的元素子集 A 值 = 0。
我的问题从这里开始，decoratedA 的列表 A 值 = 0；我通过计算每个 A
listOfLinkedA 来搜索此列表的下一个前沿
在第 4 步到第 6 步之间的每次迭代中，我需要计算 decoratedA 的新 B 子集列表，其中 A 值 = 0。对于每个，我首先递减将每个元素的支配计数属性转化为listOfLinkedA，然后我过滤得到等于0的元素。A步骤6结束，B被保存到列表List[Seq[DecoratedA]]，然后我重新开始步骤4与 B，并计算一个新的 C，等等
在我的代码中类似的东西，我为 B 的每个元素调用 explore()，Q 在末尾等于 decoratedA 的新子集 value（此处健身）= 0 :
case class PopulationElement(popElement:Seq[Double]){
implicit def poptodouble():Seq[Double] = {
popElement
}
}
class SolutionElement(values: PopulationElement, fitness:Double, dominates: Seq[SolutionElement]) {
def decrement()= if (fitness == 0) this else new SolutionElement(values,fitness - 1, dominates)
def explore(Q:Seq[SolutionElement]):(SolutionElement, Seq[SolutionElement])={
// return all dominates elements with fitness - 1
val newSolutionSet = dominates.map{_.decrement()}
val filteredSolution:Seq[SolutionElement] = newSolutionSet.filter{s => s.fitness == 0.0}.diff{Q}
filteredSolution
}
}
算法结束，我有一个 decoratedA List[Seq[DecoratedA]] 的最终序列列表，其中包含我计算的所有前沿。
更新 2
从此示例中提取的值示例。 我只采用 pareto 前沿（红色）和 {f,h,l} 下一个前沿，支配计数 = 1。
case class p(x: Int, y: Int)
val a = A(p(3.5, 1.0),0)
val b = A(p(3.0, 1.5),0)
val c = A(p(2.0, 2.0),0)
val d = A(p(1.0, 3.0),0)
val e = A(p(0.5, 4.0),0)
val f = A(p(0.5, 4.5),1)
val h = A(p(1.5, 3.5),1)
val l = A(p(4.5, 1.0),1)
case class A(XY:p, value:Int) {def decrement()= new A(XY, value - 1)}
case class ARoot(node:A, children:Seq[A])
val population = Seq(
ARoot(a,Seq(f,h,l),
ARoot(b,Seq(f,h,l)),
ARoot(c,Seq(f,h,l)),
ARoot(d,Seq(f,h,l)),
ARoot(e,Seq(f,h,l)),
ARoot(f,Nil),
ARoot(h,Nil),
ARoot(l,Nil))
算法returnList(List(a,b,c,d,e), List(f,h,l))
更新 3
2 小时后，以及一些模式匹配问题（嗯...），我将返回完整的示例，该示例自动计算支配计数器，以及每个 ARoot 的 children。
但是我有同样的问题，我的children列表计算并不完全正确，因为每个元素A可能是另一个ARoot children列表的共享成员，所以我需要考虑你修改它的答案：/此时我只计算 Seq[p] 的 children 列表，我需要 seq[A]
case class p(x: Double, y: Double){
def toSeq():Seq[Double] = Seq(x,y)
}
case class A(XY:p, dominatedCounter:Int) {def decrement()= new A(XY, dominatedCounter - 1)}
case class ARoot(node:A, children:Seq[A])
case class ARootRaw(node:A, children:Seq[p])
object test_Whosebug extends App {
val a = new p(3.5, 1.0)
val b = new p(3.0, 1.5)
val c = new p(2.0, 2.0)
val d = new p(1.0, 3.0)
val e = new p(0.5, 4.0)
val f = new p(0.5, 4.5)
val g = new p(1.5, 4.5)
val h = new p(1.5, 3.5)
val i = new p(2.0, 3.5)
val j = new p(2.5, 3.0)
val k = new p(3.5, 2.0)
val l = new p(4.5, 1.0)
val m = new p(4.5, 2.5)
val n = new p(4.0, 4.0)
val o = new p(3.0, 4.0)
val p = new p(5.0, 4.5)
def isStriclyDominated(p1: p, p2: p): Boolean = {
(p1.toSeq zip p2.toSeq).exists { case (g1, g2) => g1 < g2 }
}
def sortedByRank(population: Seq[p]) = {
def paretoRanking(values: Set[p]) = {
//comment from @dk14: I suppose order of values isn't matter here, otherwise use SortedSet
values.map { v1 =>
val t = (values - v1).filter(isStriclyDominated(v1, _)).toSeq
val a = new A(v1, values.size - t.size - 1)
val root = new ARootRaw(a, t)
println("Root value ", root)
root
}
}
val listOfARootRaw = paretoRanking(population.toSet)
//From @dk14: Here is convertion from Seq[p] to Seq[A]
val dominations: Map[p, Int] = listOfARootRaw.map(a => a.node.XY -> a.node.dominatedCounter) //From @dk14: It's a map with dominatedCounter for each point
val listOfARoot = listOfARootRaw.map(raw => ARoot(raw.node, raw.children.map(p => A(p, dominations.getOrElse(p, 0)))))
listOfARoot.groupBy(_.node.dominatedCounter)
}
//Get the first front, a subset of ARoot, and start the step 4
println(sortedByRank(Seq(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)).head)
}
关于区分前沿的问题（更新 2 后）：
val (left,right) = population.partition(_.node.value == 0)
List(left, right.map(_.copy(node = node.copy(value = node.value - 1))))
这里不需要改变任何东西。 copy 将复制除您用新值指定的字段以外的所有内容。谈到代码，新副本将链接到相同的子列表，但是新 value = value - 1.
P.S。我有一种感觉，你可能真的想做这样的事情：
case class A(id: String, level: Int)
val a = A("a", 1)
val b = A("b", 2)
val c = A("c", 2)
val d = A("d", 3)
clusterize(List(a,b,c,d)) === List(List(a), List(b,c), List(d))
实现起来很简单：
def clusterize(list: List[A]) =
list.groupBy(_.level).toList.sortBy(_._1).map(_._2)
测试：
scala> clusterize(List(A("a", 1), A("b", 2), A("c", 2), A("d", 3)))
res2: List[List[A]] = List(List(A(a,1)), List(A(b,2), A(c,2)), List(A(d,3)))
P.S.2。请考虑更好的命名约定，例如 here.
谈论一些复杂结构中的 "mutating" 个元素：
"immutable mutating" 某些共享（结构的各个部分之间）值的想法是将您的 "mutation" 与结构分开。或者简单地说，分而治之：
- 提前计算变化
- 应用它们
代码：
case class A(v: Int)
case class AA(a: A, seq: Seq[A]) //decoratedA
def update(input: Seq[AA]) = {
//shows how to decrement each value wherever it is:
val stats = input.map(_.a).groupBy(identity).mapValues(_.size) //domination count for each A
def upd(a: A) = A(a.v - stats.getOrElse(a, 0)) //apply decrement
input.map(aa => aa.copy(aa = aa.seq.map(upd))) //traverse and "update" original structure
}
因此，我介绍了新的 Map[A, Int] 结构，它展示了如何修改原始结构。这种方法基于 Applicative Functor concept. In general case, it should be Map[A, A => A] or even Map[K, A => B] or even Map[K, Zipper[A] => B] as applicative functor (input <*> map). *Zipper (see 1, 2) 的高度简化版本，实际上可以为您提供有关当前元素上下文的信息。
备注：
我假设
A具有相同值的是相同的；这是案例类的默认行为，否则您需要提供一些额外的id（或重新定义hashCode/equals）。如果你需要更多的层次 - 比如
AA(AA(AA(...))))- 只需使stats和upd递归，如果递减的权重取决于嵌套级别 - 只需添加嵌套级别作为递归函数的参数。如果减量取决于父节点（比如只减量
A(3)的，它属于A(3)） - 添加父节点作为 [=27 的一部分=] 的密钥并在upd. 期间对其进行分析
如果统计数据计算（减少多少）之间存在某种依赖关系，比如
input(1)与input(0)- 您应该使用foldLeft和部分统计数据作为累加器：val stats = input.foldLeft(Map[A, Int]())((partialStats, elem) => partialStats ++ analize(partialStats, elem))
顺便说一句，这里需要 O(N)（线性内存和 cpu 用法）
示例：
scala> val population = Seq(A(3), A(6), A(8), A(3))
population: Seq[A] = List(A(3), A(6), A(8), A(3))
scala> val input = Seq(AA(population(1),Seq(population(2),population(3))), AA(population(2),Seq(population(1),population(3))))
input: Seq[AA] = List(AA(A(6),List(A(8), A(3))), AA(A(8),List(A(6), A(3))))
scala> update(input)
res34: Seq[AA] = List(AA(A(5),List(A(7), A(3))), AA(A(7),List(A(5), A(3))))