c# - 为什么在手指树和链表等中使用元组

Question

关于手指树，如 this paper 中所示并在 this post 中提到埃里克·利珀特着。

我不明白为什么要使用明确的元组排列，而不是为每个手指使用某种链表结构。也就是说，为什么我们定义 One(x), Two(x, y), Three(x, y, z), Four(x, y, z, a) 而不是只有一个不太理想的双端队列对象并执行LessOptimalDeque.AddLeft(x)？

它是不是有点慢？我的意思是，即使您可以使用一些数据结构来重复使用某些节点/节点组的内存？

在论文中，甚至提到了:

Exercise 1. In the above presentation, we represented digits as lists for simplicity. A more accurate and efficient implementation would use the type

data Digit a = One a  
| Two a a
| Three a a a
| Four a a a a

Rework the above denitions to use this denition of Digit.

虽然我不知道为什么它更有效率。它是否只与作者使用的功能语言相关，否则也可以使用我上面提出的数据结构来完成？

编辑

像这样实现手指怎么样？

Answer 1

看看为什么这在 H​​askell 中更有效:

data Digit a
           = One a  
           | Two a a
           | Three a a a
           | Four a a a a

比这个(向量的明显编码):

data List a = One a
            | Many a (List a) -- a linked list of at least one element.

我们可以观察分配 Digit 与 List 所需的堆结构。

Four 'x' 'y' 'z' 'd'

对比

Many 'x' (Many 'y' (Many 'z' (One 'd')))

在前一种情况下，我们保存了 3 个构造函数。在后者中，我们被迫为结构的(可能是无限的)尾部分配额外的堆对象。一般来说，Digit 表示将分配 O(n-1) 个更少的堆单元，因为结构的大小在最外层的构造函数中编码。我们还可以确定 O(1) 的大小作为结果。