4

我正在学习 LISP，只是想问在 LISP 程序中存储键值对的最佳选择是什么。

对于我提到的键值对，我想像JAVA中的Map Collection一样使用它：我想将键与值一起存储，并且可以通过键查找值。
例如：如果我有一个"apple"与 匹配的字符串"fruit"，如果它不存在，我希望能够存储它，并且可以查询与 关联的值"apple"，即水果。

任何建议或代码示例都会非常有帮助。先感谢您

4

3 回答 3

2

你没有指定你正在学习哪个 Lisp（Scheme、Common Lisp 等）所以我猜是 Common Lisp。如果我不正确，请发表评论，我会相应地进行编辑。

在 Lisp 中，这样的东西称为关联列表。它非常常用，因此有一些方便的功能可以使它成为可能。不过，它的核心实际上只不过是一个 pair 列表((key . value) ... )。

我建议查看Carnegie Melon 的解释，它会给你一个简单的函数概述，比如assoc使alist-cons使用关联列表变得容易。我发现它很有帮助。

关联列表的问题在于，虽然它们具有恒定的时间插入、删除和查找都是O(n)。因此，如果速度是一个大问题，您将需要转向实际的哈希表。

Common Lisp Cook 书对这些有很好的解释。它们依赖于允许恒定时间随机访问的实际数组（有时称为向量）。与关联列表不同，它们确实提供O(1)查找。然而，它们不像关联列表那样易于使用，因为 Lisp 通常擅长列表。

注意：对于Scheme，如果您的编译器默认不提供这些函数，那么这些函数中的大部分都应该提供SRFI 1 和69 扩展。

于 2012-10-21T18:38:50.433 回答
1

在 Common Lisp 中，您可以使用关联列表。

有关关联列表和函数ASSOC ，请参阅 Common Lisp Hyperspec

对于任何更复杂和更快的事情，Common Lisp 提供了哈希表。

于 2012-10-21T19:51:27.657 回答
0

为了公平起见，MapJava 中是一个接口。它有各种不同的实现，它们在读/写/删除操作中可能不会为您提供相同的复杂性。有些可以实现为链表，有些可能是二进制尝试等。

Map在 Java 中只定义了访问数据的方式，但没有定义数据的存储方式。

Lisps，好吧，如果你考虑CLOS，没有接口的概念，这是因为CLOS支持多重继承。Java 没有足够的类似物，Map因为没有以这种方式访问​​集合的概念，也没有接口的概念，因为它们存在于 Java 中。

Java中有几种标准实现Map。一个是HashMap（Hashtable与它非常相似）。hash-table这与Common Lisp中的类非常相似。Java 中也有LinkedHashMap，它与 Lisp 中的关联列表非常相似。一个简单的 Lisp 不提供红黑树映射，并且没有关于线程的标准化行为 - 您需要阅读有关特定实现的文档，但您可以在这里找到各种数据结构的许多良好实现：http://www.cliki.net/Data%20structure。

于 2012-10-21T21:42:24.983 回答