“我需要一种新的药物,一种不会让我生病的药物,一种不会让我撞车或让我感觉像被压扁三英尺的药物。”
——Huey Lewis and the News
虽然本教程开头引用的歌词看似和编程无关,但事实上,Lisp 的哈希表和数组系统的设计,确实能让我们像嗑药一样上瘾(纯属比喻,绝无鼓励滥用物质的意思)。在本篇文章中,我们将探索 Common Lisp 中的三位数据结构好伙伴:关联列表(a-list)、属性列表(p-list)和哈希表(hash table),以及数组和向量的奇妙世界。准备好了吗?让我们开始吧!
🔗 关联列表 - 一切从 cons 开始
关联列表(a-list)是 Lisp 中最简单的键值对存储方式之一。它由一串 cons
对象组成,而 cons
是 Lisp 中的基本构建块。每个 cons
对象都包含两个部分,分别是 car
(存储键)和 cdr
(存储值)。你可以将其想象为一对好朋友,一个负责记住事情,另一个负责行动。
(defparameter *alist* (list (cons 1 2) (cons 3 4)))
在上面的例子中,我们创建了一个简单的关联列表,包含两个键值对 (1 . 2)
和 (3 . 4)
。我们可以通过 assoc
函数快速查找键所对应的值:
(assoc 3 *alist*) ; => (3 . 4)
(car (assoc 3 *alist*)) ; => 3
(cdr (assoc 3 *alist*)) ; => 4
通过 acons
,我们可以向关联列表中非破坏性地添加一对新朋友:
(acons 5 6 *alist*) ; => '((1 . 2)(3 . 4)(5 . 6))
不过,关联列表的一个限制是它的查找速度较慢,因为所有键值对都存储在一个线性列表中。要查找某个键值对,必须遍历整个列表,直到找到匹配的键。
🌀 用 LOOP
显示所有的键值对
LOOP
是 Lisp 中的强大工具,可以非常优雅地遍历列表。我们可以用它来显示关联列表中的所有键和值:
(loop for (k . v) in *alist* do (format t "k=~A v=~A~
输出结果将会是:
k=1 v=2 k=3 v=4
🧳 属性列表 - 有序的键值对
属性列表(p-list)则是一种更加节省空间的键值对存储方式。它的奇数位置存储键,偶数位置存储值。这就像一对对情侣并排而坐,每个键旁边都是它的值。
(defparameter *plist* (list 'k1 'v1 'k2 'v2 'k3 'v3))
在这个例子中,
k1
、k2
和k3
是键,而v1
、v2
和v3
是对应的值。我们可以通过getf
来查找键对应的值:(getf *plist* 'k2) ; => v2
你还可以通过
remf
删除元素,或者通过setf
替换某个键对应的值:(setf (getf *plist* 'k3) 3)
🌀 用
LOOP
遍历属性列表同样,我们可以使用
LOOP
来遍历属性列表中的键值对:(loop for (k v) on *plist* by #'cddr do (format t "k=~A v=~A
输出结果将会是:
k=K1 v=V1 k=K3 v=3
🚀 哈希表 - 性能之选
当你需要更快的查找速度时,哈希表就是你的不二选择。与关联列表和属性列表不同,哈希表使用哈希函数来快速定位键值对。它的效率远高于线性结构,尤其是当你有大量数据时。
创建一个哈希表非常简单:
(defparameter *hash* (make-hash-table :test #'equal))
然后你可以向哈希表中添加键值对:
(setf (gethash "key1" *hash*) "value1") (setf (gethash "key2" *hash*) "value2")
查找键值对也非常简单:
(gethash "key1" *hash*) ; => "value1"
如果你不再需要某个键值对,可以用
remhash
删除它:(remhash "key2" *hash*)
🌀 用
LOOP
遍历哈希表哈希表也可以通过
LOOP
来遍历:(loop for key being the hash-keys of *hash* collect key) (loop for value being the hash-values of *hash* do (print value))
📊 数组与向量 - 索引式存储
在某些情况下,你可能需要通过数字索引来访问数据,这时数组和向量将派上用场。数组可以是多维的,而向量则是单维数组。
我们可以用
make-array
创建一个三维数组:(defparameter *array* (make-array '(9 9 9) :initial-element 1))
这个数组的每个维度都包含9个元素,初始值为1。你可以通过
aref
来访问特定位置的元素:(aref *array* 1 2 3) ; => 1
向量是单维数组,创建方法如下:
(vector 1 2 3)
访问向量元素同样使用
aref
:(aref #(1 2 3) 0) ; => 1
🌀 用
LOOP
遍历向量你可以使用
LOOP
来遍历向量中的元素:(loop for n across #(1 2 3) do (print n))
输出结果将会是:
1 2 3
结论
Common Lisp 提供了多种数据结构来满足不同场景下的需求。从简单的关联列表到性能优越的哈希表,再到通过索引访问的数组和向量,每种数据结构都有其独特的优势。正如歌曲所说,我们都在寻找一种不会让我们“生病”的新工具,而 Lisp 的这些数据结构,或许就是我们在编程世界里一直寻找的“新药”。
参考文献
- Common Lisp Documentation
- CLOG GitHub Repository - https://github.com/rabbibotton/clog
面向记忆的学习材料
快速学习并记住Common Lisp中哈希表和数组的重要概念和用法。
知识点: 哈希表的创建
题目: 在Common Lisp中,如何创建一个哈希表,其中键可以是字符串?
选项:
A) (make-hash-table)
B) (make-hash-table :test #'eql)
C) (make-hash-table :test #'equal)
D) (create-hash-table)正确答案: C解析: 在Common Lisp中,创建哈希表使用make-hash-table函数。默认的测试函数是eql,但它不适用于字符串。要使用字符串作为键,应该使用:test #'equal选项。速记提示: "equal for strings" - 记住equal用于字符串键的哈希表。知识点: 哈希表的操作
题目: 在Common Lisp中,如何向哈希表hash中添加键"key1"和值"value1"?
选项:
A) (add-to-hash hash "key1" "value1")
B) (setf (gethash "key1" hash) "value1")
C) (push "key1" "value1" hash)
D) (insert hash "key1" "value1")正确答案: B解析: 在Common Lisp中,向哈希表添加键值对使用setf和gethash的组合。正确的语法是(setf (gethash key hash-table) value)。速记提示: "setf gethash" - 记住setf和gethash的组合用于设置哈希表的值。知识点: 关联列表(a-list)的创建
题目: 如何在Common Lisp中创建一个包含键值对(1 . 2)和(3 . 4)的关联列表?
选项:
A) '((1 . 2)(3 . 4))
B) (list (cons 1 2) (cons 3 4))
C) (make-alist '(1 2 3 4))
D) (create-association-list 1 2 3 4)正确答案: B解析: 创建关联列表可以使用list函数和cons函数的组合。每个键值对用cons创建,然后用list组合成列表。注意不要使用引用的字面量形式,因为它会创建一个常量,不易修改。速记提示: "list of cons" - 记住关联列表是cons对象的列表。知识点: 关联列表的查找
题目: 在Common Lisp中,如何在关联列表alist中查找键为3的项?
选项:
A) (find 3 alist)
B) (assoc 3 alist)
C) (gethash 3 alist)
D) (lookup 3 alist)正确答案: B解析: 在关联列表中查找键使用assoc函数。它返回找到的第一个匹配键的整个cons单元。速记提示: "assoc for alist" - 记住assoc用于在关联列表中查找。知识点: 属性列表(p-list)的创建
题目: 在Common Lisp中,如何创建一个包含键值对k1/v1和k2/v2的属性列表?
选项:
A) (make-plist 'k1 'v1 'k2 'v2)
B) '((k1 . v1)(k2 . v2))
C) (list 'k1 'v1 'k2 'v2)
D) (create-property-list :k1 'v1 :k2 'v2)正确答案: C解析: 属性列表是一个普通的列表,其中奇数位置的元素是键,偶数位置的元素是值。使用list函数可以直接创建这样的列表。速记提示: "list of alternating keys and values" - 记住p-list是键值交替的普通列表。知识点: 属性列表的查找
题目: 在Common Lisp中,如何在属性列表plist中查找键k2的值?
选项:
A) (assoc 'k2 plist)
B) (getf plist 'k2)
C) (gethash 'k2 plist)
D) (get 'k2 plist)正确答案: B解析: 在属性列表中查找键的值使用getf函数。它直接返回与键对应的值。速记提示: "getf for plist" - 记住getf用于在属性列表中获取值。知识点: 哈希表的遍历
题目: 在Common Lisp中,如何使用loop宏遍历哈希表hash的所有键?
选项:
A) (loop for key in hash collect key)
B) (loop for key being the hash-keys of hash collect key)
C) (loop for (key value) in hash collect key)
D) (loop for key across hash collect key)正确答案: B解析: 使用loop宏遍历哈希表的键,需要使用"being the hash-keys of"语法。这允许直接访问哈希表的所有键。速记提示: "being the hash-keys" - 记住这个特殊的loop语法用于遍历哈希表的键。知识点: 数组的创建
题目: 在Common Lisp中,如何创建一个3x3x3的三维数组,初始值都为1?
选项:
A) (make-array '(3 3 3) :initial-element 1)
B) (create-3d-array 3 3 3 :fill 1)
C) (vector 1 1 1 1 1 1 1 1 1)
D) (array 3 3 3 1)正确答案: A解析: 使用make-array函数创建数组。第一个参数是一个列表,指定每个维度的大小。:initial-element关键字参数用于设置所有元素的初始值。速记提示: "make-array with dimensions list" - 记住使用列表指定维度,initial-element设置初始值。知识点: 数组元素的访问
题目: 在Common Lisp中,如何访问名为array的三维数组中坐标为(1,2,3)的元素?
选项:
A) (array 1 2 3)
B) (aref array 1 2 3)
C) (get-array-element array 1 2 3)
D) (elt array 1 2 3)正确答案: B解析: 使用aref函数访问数组的元素。第一个参数是数组,后面跟着每个维度的索引。速记提示: "aref for array reference" - 记住aref用于访问数组元素。知识点: 向量的创建
题目: 在Common Lisp中,以下哪种方式可以创建包含元素1、2、3的向量?
选项:
A) (make-vector 1 2 3)
B) (array 1 2 3)
C) #(1 2 3)
D) '(1 2 3)正确答案: C解析: 在Common Lisp中,可以使用#(…)语法快速创建向量。这是一种特殊的读取语法,直接创建一个包含指定元素的向量。速记提示: "#(…) for quick vector" - 记住#语法用于快速创建向量。知识点: 向量的遍历
题目: 在Common Lisp中,如何使用loop宏遍历向量#(1 2 3)的所有元素?
选项:
A) (loop for n in #(1 2 3) do (print n))
B) (loop for n of #(1 2 3) do (print n))
C) (loop for n across #(1 2 3) do (print n))
D) (loop for n being the elements of #(1 2 3) do (print n))正确答案: C解析: 使用loop宏遍历向量时,需要使用across关键字。这允许直接访问向量的所有元素。速记提示: "across for vector loop" - 记住across用于在loop中遍历向量。知识点: 关联列表的修改
题目: 在Common Lisp中,如何修改关联列表alist中键为3的值为5?
选项:
A) (setf (assoc 3 alist) 5)
B) (setf (cdr (assoc 3 alist)) 5)
C) (setf (getf alist 3) 5)
D) (modify-alist alist 3 5)正确答案: B解析: 要修改关联列表中某个键的值,首先使用assoc找到对应的cons单元,然后使用setf和cdr修改其值部分。速记提示: "setf cdr of assoc" - 记住修改alist值需要setf、cdr和assoc的组合。知识点: 属性列表的移除
题目: 在Common Lisp中,如何从属性列表plist中移除键k2及其对应的值?
选项:
A) (remove 'k2 plist)
B) (delete 'k2 plist)
C) (remf plist 'k2)
D) (setf (getf plist 'k2) nil)正确答案: C解析: 使用remf函数可以从属性列表中移除指定的键及其对应的值。remf是一个宏,它修改原始的属性列表。速记提示: "remf for plist removal" - 记住remf用于从属性列表中移除键值对。知识点: 哈希表的清空
题目: 在Common Lisp中,如何清空哈希表hash中的所有内容?
选项:
A) (clear hash)
B) (empty hash)
C) (setf hash (make-hash-table))
D) (clrhash hash)正确答案: D解析: 使用clrhash函数可以清空哈希表中的所有内容。这个函数会移除所有的键值对,但保留哈希表对象本身。速记提示: "clrhash for clear hash" - 记住clrhash用于清空哈希表。知识点: 符号的属性列表
题目: 在Common Lisp中,如何获取符号some-symbol的属性列表中键some-key的值?
选项:
A) (get 'some-symbol 'some-key)
B) (getf (symbol-plist 'some-symbol) 'some-key)
C) (symbol-property 'some-symbol 'some-key)
D) (plist-value 'some-symbol 'some-key)正确答案: B解析: 每个符号都有自己的属性列表。使用symbol-plist函数获取符号的属性列表,然后使用getf函数从中获取特定键的值。速记提示: "symbol-plist then getf" - 记住先用symbol-plist获取列表,再用getf获取值。知识点: 哈希表的测试函数
题目: 在Common Lisp中,如果要创建一个不区分大小写的字符串键的哈希表,应使用哪个测试函数?
选项:
A) #'eql
B) #'equal
C) #'equalp
D) #'string=正确答案: C解析: 使用#'equalp作为测试函数可以创建一个不区分大小写的字符串键的哈希表。equalp在比较字符串时会忽略大小写。速记提示: "equalp for case-insensitive" - 记住equalp用于创建不区分大小写的哈希表。知识点: 向量和数组的关系
题目: 在Common Lisp中,向量与数组的关系是什么?
选项:
A) 向量和数组是完全不同的数据结构
B) 向量是一维数组的特例
C) 数组是向量的特例
D) 向量和数组是同义词正确答案: B解析: 在Common Lisp中,向量是一维数组的特例。所有的向量都是数组,但不是所有的数组都是向量。向量提供了一些额外的操作符和语法糖。速记提示: "Vectors are 1D arrays" - 记住向量就是一维数组。知识点: 关联列表的反向查找
题目: 在Common Lisp中,如何在关联列表alist中通过值2查找对应的键?
选项:
A) (find 2 alist :key #'cdr)
B) (rassoc 2 alist)
C) (assoc 2 alist)
D) (member 2 alist :key #'cdr)正确答案: B解析: 使用rassoc函数可以在关联列表中通过值查找键。它返回第一个匹配值的整个cons单元。速记提示: "rassoc for reverse assoc" - 记住rassoc用于关联列表的反向查找。知识点: 数组元素的修改
题目: 在Common Lisp中,如何将三维数组array中坐标为(1,2,3)的元素的值修改为5?
选项:
A) (setf (array 1 2 3) 5)
B) (setf (aref array 1 2 3) 5)
C) (set-array-element array 1 2 3 5)
D) (modify-aref array 1 2 3 5)正确答案: B解析: 使用setf和aref的组合可以修改数组中特定位置的元素值。aref用于指定要修改的元素,setf用于设置新值。速记提示: "setf with aref" - 记住setf和aref的组合用于修改数组元素。知识点: 循环遍历哈希表的键值对
题目: 在Common Lisp中,如何使用loop宏同时遍历哈希表hash的键和值?
选项:
A) (loop for (k . v) in hash do (format t "~A: ~A总结
通过这20道题目,我们涵盖了Common Lisp中哈希表、关联列表、属性列表、数组和向量的主要概念和操作。以下是关键点总结:
- 哈希表:使用make-hash-table创建,gethash访问,setf和gethash组合添加或修改,remhash删除,clrhash清空。
- 关联列表(a-list):用cons创建键值对,list组合,assoc查找键,rassoc反向查找值。
- 属性列表(p-list):简单的交替键值列表,getf查找,remf删除。
- 数组:使用make-array创建,aref访问和修改元素。
- 向量:一维数组的特例,可用#(…)快速创建。
- 遍历:loop宏用于遍历各种数据结构,针对不同类型有特定语法。
- 符号属性:每个符号都有自己的属性列表,可通过symbol-plist访问。
掌握这些概念和操作将帮助你更有效地使用Common Lisp进行编程。记住,选择合适的数据结构对于程序的效率和可读性至关重要。
参考文献
- Common Lisp - The Tutorial Part 9.pdf
- https://github.com/rabbibotton/clog/blob/main/LEARN.md
- Huey Lewis and the News (歌词引用)