代码之家 › 专栏 › 技术社区 › SirPeople

用线性供应流中的值填充嵌套结构

nested stream functional-programming data-structures algorithm

SirPeople · 技术社区 · 6 年前

我陷入了解决下一个问题的困境:

假设我们有一个数组结构,任何结构,但是在这个例子中,让我们使用:

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

为了方便起见,我将此结构转换为类似以下的平面数组:

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

假设在执行某些操作后,我们的数组如下所示:

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

注意:这些值是一些操作的结果,我只是想指出,它独立于结构或它们的位置。

我想知道的是…给定第一个数组结构,如何将最后一个平面数组转换为与第一个相同的结构?所以看起来像是:

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

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

3 回复 | 直到 6 年前

Andrey Tyukin 6 年前

这是斯卡拉的素描。无论您的语言是什么,您首先必须以某种方式表示类似树的数据结构:

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 方法和额外的构造函数并不那么重要,主要是为了下面的小演示。

现在您基本上想要构建一个编码器解码器,其中 encode 部分只会压扁所有的东西, decode part将另一个嵌套数组作为参数,并将平面数组整形为嵌套数组的形状。压平非常简单:

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

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

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树:

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

现在从另一个数组中重建形状相同的树:

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子代进行功能编程的人来说或多或少是可以理解的。

Bergi 6 年前

只需在结构中递归,并使用迭代器按顺序生成值:

function fillWithStream(structure, iterator) {
    for (var i=0; i<structure.length; i++)
        if (Array.isArray(structure[i]))
            fillWithStream(structure[i], iterator);
        else
            structure[i] = getNext(iterator);
}
function getNext(iterator) {
    const res = iterator.next();
    if (res.done) throw new Error("not enough elements in the iterator");
    return res.value;
}

var structure = [
    [ [1, 2], [3, 4], [5, 6] ],
    [ 7, 8, 9, 10 ]
];
var seq = [1, 2, 3, 4, 12515, 25125, 12512, 8, 9, 10];
fillWithStream(structure, seq[Symbol.iterator]())
console.log(JSON.stringify(structure));

Will Ness Derri Leahy 5 年前

结果是 I've already answered 几个月前你的问题,无论如何都很相似。

那里的代码需要稍微调整一下,使其适合这里。方案中:

(define (merge-tree-fringe vals tree k)
  (cond
    [(null? tree)
     (k vals '())]
    [(not (pair? tree))                  ; for each leaf:
     (k (cdr vals) (car vals))]          ;   USE the first of vals
    [else
     (merge-tree-fringe vals (car tree) (lambda (Avals r)      ; collect 'r' from car,
      (merge-tree-fringe Avals (cdr tree) (lambda (Dvals q)    ;  collect 'q' from cdr,
       (k Dvals (cons r q))))))]))       ; return the last vals and the combined results

第一个参数是值的线性列表,第二个参数是要重新创建其结构的嵌套列表。确保线性值列表中有足够的元素是 在你身上 .

我们称之为

> (merge-tree-fringe '(1 2 3 4 5 6 7 8) '(a ((b) c) d) (lambda (vs r) (list r vs)))
'((1 ((2) 3) 4) (5 6 7 8))

> (merge-tree-fringe '(1 2 3 4 5 6 7 8) '(a ((b) c) d) (lambda (vs r) r))
'(1 ((2) 3) 4)

在链接的答案中有一些措辞,解释了正在发生的事情。短篇小说,写在 CPS - continuation-passing 风格:

我们处理嵌套结构的一部分,同时用线性供应的值替换叶;然后用剩余供应处理结构的其余部分;然后我们将处理这两个子部分得到的两个结果结合起来。对于类似lisp的嵌套列表,它通常是 car “和” cdr “的” cons “单元格,即树的顶部节点。

这就是Bergi的代码所做的,本质上,但是以一种功能性的风格。

在与伪代码匹配的假想模式中,它可能更容易阅读/跟踪

merge-tree-fringe vals tree = g vals tree (vs r => r)
    where
    g vals [a, ...d] k = g vals a (avals r =>    -- avals: vals remaining after 'a'
                             g avals d (dvals q =>    -- dvals: remaining after 'd'
                                 k dvals [r, ...q] ))     -- combine the results
    g vals        [] k = k vals []                           -- empty 
    g [v, ...vs]  _  k = k vs   v                            -- leaf: replace it

这种通过计算来处理一个变化状态的计算模式正是monad状态的意义所在;使用haskell do 上面的符号将写为

merge_tree_fringe vals tree = evalState (g tree) vals
    where
    g [a, ...d] = do { r <- g a ; q <- g d ; return [r, ...q] }  
    g        [] = do { return [] }           
    g        _  = do { [v, ...vs] <- get ; put vs ; return v }  -- leaf: replace

put 和 get 处理被操纵、更新和传递的状态; vals 初始状态;最终状态被 evalState 就像我们的 (vs r => r) 上面也有,但很明确。