lisp中的数据结构
我有一个简单的问题:将对象收集到列表中并向后遍历此列表.看起来很简单,但这段代码是高负载计算的一部分.使用conses是很自然的,因为它在添加新元素和顺序访问时需要O(1).但是,如果我需要一个有效的双链表来轻松地在两个方向上遍历它,我该怎么办？使用(反向)？它需要O(n)内存和时间,所以实际上它需要O(n ^ 2)在我的情况下(这是非常糟糕的).使用(最后)还是(追加)？同样的故事:O(n).我真的不知道在哪里可以找到关于标准库函数计算复杂性的任何信息(源代码除外).它是依赖于实现的吗？我需要做些什么才能实现各种标准数据结构？有没有有效使用conses的指南？
Rai*_*wig 15
如果使用Common Lisp,则可以使用向量.矢量可以具有填充指针和/或可以是可调节的.因此,您可以使用向量推送向向量添加元素.填充指针将增长.如果矢量是可调节的,那么如果需要它也会变大.由于向量是一维数组,因此您可以根据需要使用索引访问元素.
请参阅MAKE-ARRAY选项以创建此类矢量.
VECTOR-PUSH和VECTOR-PUSH-EXTEND是添加元素的功能.
Ano*_*mie 12
如果您执行(reverse)一次然后按顺序遍历反转列表,则总计应该是O(2n)时间(设置为O(n),然后是另一个O(n)遍历)和O(n)内存.
双重链表不是非常复杂.如您所知,列表由cons单元格组成,其中汽车指向对象而不是cdr指向列表中的下一个cons单元格.
进行双向链表的一种方法是将cdr指向另一个cons单元,其cdr指向列表中的下一个cons单元,其car指向列表中的前一个cons单元.然后你使用cddr前进和cdar后退.
我不知道标准库函数有任何保证的复杂性.除非规范指定,否则它将是实现定义的.