count - 如何计算lisp列表中每个元素的重复次数？

Question

我想计算lisp列表中每个元素的重复次数。例如 (1 2 1 1 3) 应该给出输出“元素 1：三次” 任何解决方案？

Answer 1

尽管使用该函数单独计算所有不同的元素是count有效的，但它的效率极低，因为它具有二次复杂度，但线性复杂度足以解决此任务。

您需要做的是创建一些将键映射到值的数据结构。（属性列表（如果只有很少的不同元素）或哈希表适用于一般元素。如果元素都是像您的示例中的小整数，则数组将是一个可行的选择。）元素将是键，以及它们的频率值。然后您将遍历列表，并在每个值出现时增加它的频率计数。（只需用于属性列表访问器函数或哈希表访问器函数0的可选默认参数，您可以增加该值而不必担心您之前是否见过该元素。如果您使用数组，只需初始化其所有元素。）getfgethash0

Answer 2

这应该有效：

;Create a set from an initial input list
(defun set-from-list (lst)
    (let ((st))
        (loop for ele in lst
            do
            (if (not (member ele st))
                (push ele st))) st))

;Now iterate over the set as derived from the list, and count the occurrences, and accordingly, output the result
(defun count-in-list (lst)
    (let ((st (set-from-list lst)))
        (loop for item in st
            do
            (format t "~A occurs ~A times in list ~A ~%" item (count item lst) lst))) nil) 

唯一缺少的是将数字转换为相关的字符串表示形式。但这是相当微不足道的，是你可以为自己做的事情。