当您将链接到彼此的对象影响到此列表时,如何维护不可变列表

Question

我正在尝试使用Scala以不可变的方式编写NSGA2中使用的Deb的快速非支配排序算法(NDS).

但问题似乎比我想象的要困难,所以我在这里简化了制作MWE的问题.

想象一下,一个群体Seq[A],每个A元素decoratedA都有一个列表,其中包含指向其他群体元素的指针Seq[A].

一个函数evalA(a:decoratedA)取linkedA它包含的列表,并减少每个的值.

接下来,我将获取decoratedAPopulation人口A 的子集列表,并对evalA每个人进行调用.我有一个问题,因为在这个子集列表上的元素的每次迭代之间decoratedAPopulation,我需要A用decoratedA新的更新linkedA它包含的新的更新它包含...

更有问题的是,每个人口元素都需要更新'linkedA'来替换链接元素,如果它发生变化......

你可以看到Hum,以这种方式保持所有链表同步似乎很复杂.我提出了另一个解决方案底部,可能需要递归才能在每个EvalA替换元素的新种群后返回.

我怎样才能以不变的方式正确地做到这一点？

以可变的方式编码很容易,但我找不到以不可变的方式做到这一点的好方法,你有路径或想法吗？

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{
    // ?
    //}
  }
} 

更新1:

关于初始算法的输入/输出.

Deb算法的第一部分(步骤1到步骤3)分析个体的列表,并计算每个A:(a)统治计数,支配我的A的数量(A的value属性)(b)列表我支配着(listOfLinkedA).

所以它返回一个decoratedA完全初始化的人口,并且对于第4步的进入(我的问题),我采取第一个非支配的前线,参见 的元件的子集decoratedA与A值= 0.

我的问题从这里开始,以列表decoratedA与 A值= 0; 然后我通过计算每listOfLinkedA一个来搜索下一个前面的列表A

在步骤4到步骤6之间的每次迭代中,我需要计算具有值= 0 的新B子集列表.对于每个,我首先递减每个元素的控制计数属性,然后i过滤以使元素等于0.在步骤6结束时,B保存到列表中,然后我用B重新启动到步骤4,并计算新的等等. decoratedAAlistOfLinkedAList[Seq[DecoratedA]]C

类似的东西在我的代码,我调用explore()的每个元素B,以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

  }
}

算法的结束,我有一个seq的最终列表,decoratedA List[Seq[DecoratedA]]其中包含我计算的所有前端.

更新2

从此示例中提取的值的示例.我只采用帕累托前线(红色)和{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))

算法返回 List(List(a,b,c,d,e), List(f,h,l))

更新3

2小时后,和一些模式匹配问题(Ahum ......)我回来了完整的例子,自动计算主导的计数器,以及每个ARoot的孩子.

但我有同样的问题,我的孩子列表计算并不完全正确,因为每个元素A可能是另一个ARoot子列表的共享成员,所以我需要考虑你的答案来修改它:/此时我只计算儿童名单Seq[p],我需要清单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_stackoverflow 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)

}

Answer 1

谈论你的区分战线的问题（更新2后）：

\n\n

val (left,right) = population.partition(_.node.value == 0)\nList(left, right.map(_.copy(node = node.copy(value = node.value - 1))))\n

\n\n

不需要在这里改变任何东西。copy将复制除您用新值指定的字段之外的所有内容。谈到代码，新副本将链接到相同的子列表，但是 new value = value - 1。

\n\n

PS我有一种感觉，你可能真的想做这样的事情：

\n\n

case class A(id: String, level: Int)\nval a = A("a", 1)\nval b = A("b", 2)\nval c = A("c", 2)\nval d = A("d", 3)\n\nclusterize(List(a,b,c,d)) === List(List(a), List(b,c), List(d))\n

\n\n

实现起来很简单：

\n\n

def clusterize(list: List[A]) = \n   list.groupBy(_.level).toList.sortBy(_._1).map(_._2)\n

\n\n

测试：

\n\n

scala> clusterize(List(A("a", 1), A("b", 2), A("c", 2), A("d", 3)))\nres2: List[List[A]] = List(List(A(a,1)), List(A(b,2), A(c,2)), List(A(d,3)))\n

\n\n

PS2。请考虑更好的命名约定，例如此处。

\n\n\n\n

谈论一些复杂结构中的“变异”元素：

\n\n

“不可变变异”某些共享（结构的各个部分之间）值的想法是将“变异”与结构分开。或者简单地说，分而治之：

\n\n

\n
1. 提前计算变化
\n
2. 应用它们
\n

\n\n

代码：

\n\n

 case class A(v: Int)\n case class AA(a: A, seq: Seq[A]) //decoratedA\n\n def update(input: Seq[AA]) = {\n    //shows how to decrement each value wherever it is:\n    val stats = input.map(_.a).groupBy(identity).mapValues(_.size) //domination count for each A\n    def upd(a: A) = A(a.v - stats.getOrElse(a, 0)) //apply decrement\n    input.map(aa => aa.copy(aa = aa.seq.map(upd))) //traverse and "update" original structure\n }\n

\n\n

因此，我引入了新的Map[A, Int]结构，展示了如何修改原始结构。这种方法基于应用函子概念的高度简化版本。一般情况下，它应该是Map[A, A => A]or EvenMap[K, A => B]或 EvenMap[K, Zipper[A] => B]作为应用函子 ( input <*> map)。*Zipper（参见1、2）实际上可以为您提供有关当前元素上下文的信息。

\n\n

笔记：

\n\n

\n

• 我假设A具有相同值的 s 是相同的；这是案例类的默认行为，否则您需要提供一些额外的id（或重新定义hashCode/equals）。

\n

• 如果您需要更多级别 - 例如AA(AA(AA(...))))- 只需 makestats和upd递归，如果 d\xd0\xb5crement\ 的权重取决于嵌套级别 - 只需将嵌套级别作为参数添加到递归函数即可。

\n

• 如果递减取决于父节点（例如仅递减A(3)属于 的 \'s A(3)） - 将父节点添加为stats\'s 键的一部分并在 期间对其进行分析upd。

\n

• 如果统计数据计算（减少多少）之间存在某种依赖性，input(1)那么input(0)您应该使用foldLeft部分统计数据作为累加器：val stats = input.foldLeft(Map[A, Int]())((partialStats, elem) => partialStats ++ analize(partialStats, elem))

\n

\n\n

顺便说一句，它需要O(N)这里（线性内存和CPU使用率）

\n\n

例子：

\n\n

scala> val population = Seq(A(3), A(6), A(8), A(3))\npopulation: Seq[A] = List(A(3), A(6), A(8), A(3))\n\nscala> val input = Seq(AA(population(1),Seq(population(2),population(3))), AA(population(2),Seq(population(1),population(3))))\ninput: Seq[AA] = List(AA(A(6),List(A(8), A(3))), AA(A(8),List(A(6), A(3))))\n\nscala> update(input)\nres34: Seq[AA] = List(AA(A(5),List(A(7), A(3))), AA(A(7),List(A(5), A(3))))\n

\n