为什么需要rlist数据结构?它的优点是什么?
如果该示例显示为(4, (3, (2, (1, None))))
,我会认为它可以扩展到(5, (4 (3, (2, (1, None)))))
,就像其他任何链接列表一样,它具有完全的意义。
但是,由于示例是(1, (2, (3, (4, None))))
,所以(5, (1, (2, (3, (4, None)))))
可以将其向外扩展,尽管可能,但似乎与所示数据的方向相反。我感到这不是这种数据结构的意图。(4, None)
由于tuples
无法修改,因此无法进行扩展。
那么,这种数据结构的真正目的是什么?即使可以扩展它,我也不知道为什么它比(1, 2, 3, 4)
!
由于该课程改编自Scheme,因此他们是否尝试显示Scheme的列表?如果是这样,Scheme是lists
增长的还是静态的?甚至Lisp的例子也显示出cons
构建起来就像(cons 5 x)
显示出来的样子,(5 1 2 3)
这对于像我这样的初学者来说确实是违反直觉的。
我正在尝试点点滴滴,请帮忙!
评论中已经提到了这一点,但可以将其发布为答案:
递归列表(不是特定于Scheme的)在两种情况下很有用:
当您需要一个不变的数据结构时(例如,用于并行性或在函数式编程中)
当您需要高效地表示许多共享同一尾巴的列表(例如,一棵树)时
这是因为它们允许在不修改原始列表的情况下扩展列表。
在图形中查找路径时可能会出现这种情况。举例来说,假设您要寻找从房屋到工作场所的N条最佳路径(例如Google Maps),那么您就开始从工作场所(目的地)搜索,并考虑不同的街道,向后移动直到找到房子。1个
此处发生的是,许多路径将共享相同的“后缀”,因此,您只希望共享这些部分并将它们表示一次,以节省内存(因为您没有重复的路径)和时间(因为您不必花时间复制上一个路径就可以添加一个不同的前缀)。
现在,在这里您可能会想:“为什么我要到目的地的路径不只几个?” 好吧,如果“您”只是在给定的时间点将您称为一个人,您可能不希望这样做。但是,如果您要尝试在不同的流量条件下(例如,在不同的时间点)模拟许多驱动程序,那么突然节省内存和计算时间将很重要,并且可以共享部分数据结构并继续构建并行排列它们的顶部可以产生巨大的变化。
1您也可以使用某些算法向前搜索,但是向后搜索则更为通用。无论如何,这里的方向并不重要。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句