4

关于手指树，如本文所见并在Eric Lippert的这篇文章中提到。

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

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

在论文中，它甚至提到：

练习 1. 在上面的演示中，为简单起见，我们将数字表示为列表。更准确和更有效的实现将使用该类型 

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

修改上述定义以使用此数字定义。

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

编辑
在此处输入图像描述

像这样实现手指怎么样？

4

1 回答 1

2

要了解为什么这在 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.

我们可以观察分配 aDigit和 a所需的堆结构List。

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

对比

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

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

于 2012-07-02T15:05:55.727 回答