hashmap - 用计数存储二元组的有效方法

Question

我有几个文本文件，我想用这些二元语法在我的文件中出现的次数来创建二元语法。我在想我可以将它们存储在以二元组为键的 HashMap 中，并计为值。但是，我知道 hashmap 使用的内存比列表多得多，我想我可以用包含三元组 (w1、w2、count) 的列表做同样的事情。

所以，在代码中，我现在这样做:

(defparameter mymap (make-hash-table :test 'equal))

(if (gethash "w1 w2" mymap) 
    (setf (gethash "w1 w2" mymap) (+ 1 (gethash "w1 w2" mymap))) 
    (setf (gethash "w1 w2" mymap) 1))

Answer 1

除非您有少量键，否则列表可能不是您想要的。 HashMap 可能是一个不错的选择。它可能会使用更多的内存，但可能还不够，您需要担心它，您可以调整 rehash-size 和 rehash-threshold 来控制内存/您的特定应用程序的性能权衡。 (例如，较小的 rehash-size 和较大的 rehash-threshold 会使用较少的内存，但查找所需的时间会更长)。

另一种选择是二叉搜索树，例如 AVL 树或红黑树。这些不包含在 cl 包中，但有几个 lisp 库提供了实现，包括 fset、lisp 接口(interface)库和 cl-containers。