用线性供应流中的值填充嵌套结构 [英] Fill a nested structure with values from a linear supply stream

问题描述

我陷入了下一个问题的解决之路:

I got stuck in the resolution of the next problem:

想象一下，我们有一个数组结构，任何结构，但在此示例中，我们使用:

Imagine we have an array structure, any structure, but for this example let's use:

[
    [ [1, 2], [3, 4], [5, 6] ],
    [ 7, 8, 9, 10 ]
]

为方便起见，我将此结构转换为一个平面数组，如下所示:

For convenience, I transform this structure into a flat array like:

[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

想象一下，在执行某些操作之后，我们的数组如下所示:

Imagine that after certain operations our array looks like this:

[ 1, 2, 3, 4, 12515, 25125, 12512, 8, 9, 10]

注意:这些值是某些操作的结果，我只想指出一点，它们独立于结构或其位置.

NOTE: those values are a result of some operation, I just want to point out that is independent from the structure or their positions.

我想知道的是...给定第一个数组结构，如何将最后一个平面数组转换为与第一个数组相同的结构?因此，它看起来像:

What I would like to know is... given the first array structure, how can I transform the last flat array into the same structure as the first? So it will look like:

[ 
   [ [1, 2], [3, 4] , [12515, 25125] ],
   [ 12512, 8, 9, 10] 
]

有什么建议吗?我只是将职位硬编码到给定的结构中.但这不是动态的.

Any suggestions? I was just hardcoding the positions in to the given structure. But that's not dynamic.

推荐答案

这是Scala中的草图.无论您使用哪种语言，都必须首先以某种方式表示树状数据结构:

Here is a sketch in Scala. Whatever your language is, you first have to represent the tree-like data structure somehow:

sealed trait NestedArray
case class Leaf(arr: Array[Int]) extends NestedArray {
  override def toString = arr.mkString("[", ",", "]")
}
case class Node(children: Array[NestedArray]) extends NestedArray {
  override def toString = 
    children
      .flatMap(_.toString.split("\n"))
      .map("  " + _)
      .mkString("[\n", "\n", "\n]")
}

object NestedArray {
  def apply(ints: Int*) = Leaf(ints.toArray)
  def apply(cs: NestedArray*) = Node(cs.toArray)
}

唯一重要的部分是区分包含整数数组的叶节点和将其子节点保存在数组中的内部节点之间的区别. toString方法和额外的构造函数并不是那么重要，主要是用于下面的小演示.

The only important part is the differentiation between the leaf nodes that hold arrays of integers, and the inner nodes that hold their child-nodes in arrays. The toString methods and extra constructors are not that important, it's mostly just for the little demo below.

现在，您实际上想要构建一个编码器-解码器，其中encode部分仅将所有内容弄平，而decode部分将另一个嵌套数组作为参数，并将一个平面数组重塑为嵌套数组的形状.展平非常简单:

Now you essentially want to build an encoder-decoder, where the encode part simply flattens everything, and decode part takes another nested array as argument, and reshapes a flat array into the shape of the nested array. The flattening is very simple:

def encode(a: NestedArray): Array[Int] = a match {
  case Leaf(arr) => arr
  case Node(cs) => cs flatMap encode
}

恢复结构也不是那么困难.我决定通过传递一个显式的int -index:

The restoring of the structure isn't all that difficult either. I've decided to keep the track of the position in the array by passing around an explicit int-index:

def decode(
  shape: NestedArray, 
  flatArr: Array[Int]
): NestedArray = {
  def recHelper(
    startIdx: Int, 
    subshape: NestedArray
  ): (Int, NestedArray) = subshape match {
    case Leaf(a) => {
      val n = a.size
      val subArray = Array.ofDim[Int](n)
      System.arraycopy(flatArr, startIdx, subArray, 0, n)
      (startIdx + n, Leaf(subArray))
    }
    case Node(cs) => {
      var idx = startIdx
      val childNodes = for (c <- cs) yield {
        val (i, a) = recHelper(idx, c)
        idx = i
        a
      }
      (idx, Node(childNodes))
    }
  }
  recHelper(0, shape)._2
}

您的示例:

val original = NestedArray(
  NestedArray(NestedArray(1, 2), NestedArray(3, 4), NestedArray(5, 6)),
  NestedArray(NestedArray(7, 8, 9, 10))
)

println(original)

这是ASCII树的样子:

Here is what it looks like as ASCII-tree:

[
  [
    [1,2]
    [3,4]
    [5,6]
  ]
  [
    [7,8,9,10]
  ]
]

现在从不同的阵列重建一棵形状相同的树:

Now reconstruct a tree of same shape from a different array:

val flatArr = Array(1, 2, 3, 4, 12515, 25125, 12512, 8, 9, 10)
val reconstructed = decode(original, flatArr)

println(reconstructed)

这给您:

[
  [
    [1,2]
    [3,4]
    [12515,25125]
  ]
  [
    [12512,8,9,10]
  ]
]

我希望对于使用不太远距离的ML子代进行某些功能编程的人，应该或多或少容易理解.

I hope that should be more or less comprehensible for anyone who does some functional programming in a not-too-remote descendant of ML.

这篇关于用线性供应流中的值填充嵌套结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！