Mad*_*ist 0 arrays big-o list sbcl common-lisp
我想知道Common Lisp中的数组,列表和哈希表有什么区别.也就是说,我知道如何在语法上实现和使用它们.我也知道围绕这三种数据类型的计算机科学理论.
我想知道的是什么是Common-Lisp特定的实现？应该如何使用它们来优化性能代码(空间和时间)？Common Lisp中的这些数据结构是否存在任何特性？他们在运行时有多贵？
不同之处在于实际实施和实施后的性能(以术语定义O(size)).
列表实现为链接列表,因此它们可以具有复杂的嵌套和数据共享.
由于Lisp使用cons基于树的树
来表示其代码,因此可以预期链表相对较快(即,O(n)上面的常量应该很小).
数组被实现为向量(存储器的连续部分),在向量之上具有多维数组(索引算法自动完成).数组也可以共享存储空间.
O(n)(需要一个循环来移动数据)O(1)(vector-push-extend) - 平均来说,如果你使用fill-pointer&c.O(1)(aref)如果您使用专门的数组来避免装箱,您应该知道可以在访问时装箱数据.例如,如果v有类型(simple-array double-float (5)),则(aref v 2)可能必须分配内存来装箱返回值(编译器
可能会消除一些此类分配,但您需要了解危险).
散列表完全不同 - 它们不是 序列,因此它们允许从任意数据映射(而不是序列的整数索引),以及访问(读取和写入)O(1).
可以将哈希表与关联列表和属性列表进行比较(这对于小型表来说可能是一个很好的选择).
哈希表的主要考虑因素是
例如,许多实现会将所有standard-class实例散列
到同一个存储桶,使您的散列表作为列表执行.
如果使用eq哈希表,则实现可以使用内存中的对象地址作为(源)哈希,如果它具有复制垃圾收集器,则必须重新哈希每个GC上的所有哈希表.
您可能会发现最好将字符串用作哈希表键,因为它们通常是最佳哈希值.这是因为软件包本质上是钩住了读者的美化字符串哈希表 ,因此实现通常会确保它们非常好.