“我需要一种新的药物,一种不会让我生病的药物,一种不会让我撞车或让我感觉像被压扁三英尺的药物。”
——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 v))
输出结果将会是:
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 v))
输出结果将会是:
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中哈希表和数组的重要概念和用法。
知识点: 哈希表的创建 知识点: 哈希表的操作 知识点: 关联列表(a-list)的创建 知识点: 关联列表的查找 知识点: 属性列表(p-list)的创建 知识点: 属性列表的查找 知识点: 哈希表的遍历 知识点: 数组的创建 知识点: 数组元素的访问 知识点: 向量的创建 知识点: 向量的遍历 知识点: 关联列表的修改 知识点: 属性列表的移除 知识点: 哈希表的清空 知识点: 符号的属性列表 知识点: 哈希表的测试函数 知识点: 向量和数组的关系 知识点: 关联列表的反向查找 知识点: 数组元素的修改 知识点: 循环遍历哈希表的键值对 通过这20道题目,我们涵盖了Common Lisp中哈希表、关联列表、属性列表、数组和向量的主要概念和操作。以下是关键点总结: 掌握这些概念和操作将帮助你更有效地使用Common Lisp进行编程。记住,选择合适的数据结构对于程序的效率和可读性至关重要。
题目: 在Common Lisp中,如何创建一个哈希表,其中键可以是字符串?
选项:
A. (make-hash-table)✅
B. (make-hash-table :test #’eql)✅
C. (make-hash-table :test #’equal)✅
D. (create-hash-table)✅
题目: 在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”)
题目: 如何在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)✅
题目: 在Common Lisp中,如何在关联列表alist中查找键为3的项?
选项:
A. (find 3 ✅alist)
B. (assoc 3 ✅alist)
C. (gethash 3 ✅alist)
D. (lookup 3 ✅alist)
题目: 在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)✅
题目: 在Common Lisp中,如何在属性列表plist中查找键k2的值?
选项:
A. (assoc ‘k2 ✅plist)
B. (getf ✅plist ‘k2)
C. (gethash ‘k2 ✅plist)
D. (get ‘k2 ✅plist)
题目: 在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)
题目: 在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)✅
题目: 在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)
题目: 在Common Lisp中,以下哪种方式可以创建包含元素1、2、3的向量?
选项:
A. (make-vector 1 2 3)✅
B. (array 1 2 3)✅
C. #(1 2 3)✅
D. ‘(1 2 3)✅
题目: 在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))✅
题目: 在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)
题目: 在Common Lisp中,如何从属性列表plist中移除键k2及其对应的值?
选项:
A. (remove ‘k2 ✅plist)
B. (delete ‘k2 ✅plist)
C. (remf ✅plist ‘k2)
D. (setf (getf ✅plist ‘k2) nil)
题目: 在Common Lisp中,如何清空哈希表hash中的所有内容?
选项:
A. (clear ✅hash)
B. (empty ✅hash)
C. (setf ✅hash (make-hash-table))
D. (clrhash ✅hash)
题目: 在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)✅
题目: 在Common Lisp中,如果要创建一个不区分大小写的字符串键的哈希表,应使用哪个测试函数?
选项:
A. #’eql✅
B. #’equal✅
C. #’equalp✅
D. #’string=✅
题目: 在Common Lisp中,向量与数组的关系是什么?
选项:
A. 向量和数组是完全不同的数据结构✅
B. 向量是一维数组的特例✅
C. 数组是向量的特例✅
D. 向量和数组是同义词✅
题目: 在Common Lisp中,如何在关联列表alist中通过值2查找对应的键?
选项:
A. (find 2 ✅alist :key #’cdr)
B. (rassoc 2 ✅alist)
C. (assoc 2 ✅alist)
D. (member 2 ✅alist :key #’cdr)
题目: 在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)
题目: 在Common Lisp中,如何使用loop宏同时遍历哈希表hash的键和值?
选项:
A. (loop for (k . v) in ✅hash do (format t “~A. ~A~%” k v))✅
B. (loop for k being the hash-keys of ✅hash using (hash-value v) do (format t “~A. ~A~%” k v))✅
C. (loop for (k v) across ✅hash do (format t “~A. ~A~%” k v))✅
D. (loop for k v in ✅hash do (format t “~A. ~A~%” k v))✅总结
参考文献