统计列表中符号的频率

Question

我想找一个更优雅的解决方案来解决以下问题。

下面看上去是正确的，但很难读懂。

我第一次使用下面的地图功能在文体学上很差吗？

感觉是这样的，我想找出原因。

我不知道有什么更好的方式来实现这一点。

;; ANSI Common Lisp ex 3.3, p56.
;; "Define a function that takes a list and returns a list indicating
;;  number of times each (eql) element appears, sorted from most common
;;  element to least common"
;; > (occurrences '(a b a d a c d c a))
;; ((A . 4) (C . 2) (D . 2) (B . 1))

(defun occurrences (lst)
  (labels ((build-flist (lst res)                                                            ; [1]
            (if (null lst)
                res
                (build-flist (cdr lst) (mapcar #'(lambda (x) (if (eql (car x) (car lst))     ; [2]
                                                                 (cons (car x) (1+ (cdr x))) ; [3] ; rtn inc'd freq entry
                                                                 x))                               ; rtn unchanged freq entry
                                               res))))
           (remove-dups (lst)                               ; [4]
            (if (null lst)
                nil
                (adjoin (car lst)
                        (remove-dups (cdr lst))))))

    (sort (build-flist lst (mapcar #'(lambda (x) (cons x 0)) (remove-dups lst))) ; [5]
          #'> :key #'cdr)))

;;[1] build-flist builds a frequency list. it is called like:
;;    (build-flist '(a b a d a c d c a) '((A . 0) (B . 0) (C . 0) (D . 0))
;;[2] map over entire res assoc list, incrementing frequency if it equals
;;    the el just removed from head of list, else just keep entry as is (inefficient).
;;[3] inelegant. in map, is there some kind of when form.                 ;; <<< STILL TENSION HERE, CODE IS HARD TO READ
;;[4] remove-dups uses adjoin, (set-based operator). this will help us    ;; --------------------------------------------
;;    build an zero-initialised freq list, to get us started.
;;[5] Finally, our actual function builds the frequency list, then sorts the result.
;;    We pass it a frequency list initialised to zero to get started.

;; Discussion
;; It doesn't always help to encapsulate helper functions in labels.
;; If the functions are simple, perhaps they could be global, if they're complex, perhaps they could be simplified.
```

Answer 1

build-flist的一个问题是它是一个双循环。它在lst上迭代，对于每个元素迭代结果列表(它有相同的长度减去重复项)。对于每个lst元素，结果列表由mapcar复制。

此外，还可以在lst上使用递归进行迭代。在函数式编程中使用的模式是一种reduce。

remove-dups将是移除重复项的基元函数。

在典型的Lisp风格中，可以破坏性地更新结果列表。因为它是一个assoc列表，所以可以使用assoc查找元素并更新它。

首先尝试使用破坏性更新

因此，如果我们首先尝试创建结果列表：

(defun occurrences (list)
  (flet ((create-result-list (list)
           (mapcar (lambda (item)
                     (cons item 0))
                   (remove-duplicates list)))
         (count-occurrences (list result)
           (mapc (lambda (item)
                   (incf (cdr (assoc item result))))
                 list)
           result))
    (sort (count-occurrences list (create-result-list list))
          #'>
          :key #'cdr)))

第二次尝试破坏性更新

我们也可以构建结果列表，而我们移动到列表上。

(defun occurrences (list &aux result)
  (mapc (lambda (item &aux (pair (assoc item result)))
          (if pair
              (incf (cdr pair))
            (push (cons item 1) result)))
        list)
  (sort result #'> :key #'cdr))

对于更大的列表，它仍然是缓慢的，但是对于许多应用程序来说，它可能已经足够了，而且我们还可以添加任意测试，使用哈希表可能会更困难.

Answer 2

这是将元素映射到其频率计数的哈希表非常适合的典型情况。

(defun occurrences (lst)
  (let ((table (make-hash-table)))                   ; [1]
    (loop for e in lst
          do (incf (gethash e table 0)))             ; [2]
    (sort (loop for k being the hash-key of table    ; [3]
                  using (hash-value v)
                collect (cons k v))                         
          #'>= :key #'cdr)))                         ; [4]

1. 我们创建哈希表:键将是列表的一个元素，值将是频率计数。请注意，没有必要对其进行初始化，因为gethash函数为表中尚未出现的键提供了值的初始化。
2. 对于列表中的每个元素，我们增加(incf)与其相关联的频率值。这个值是由gethash获得的，如果它还没有在表中，默认情况下它将初始化为0(gethash的最后一个参数)。
3. 最后，我们使用“循环对哈希表”语法来收集列表中的所有对(key count)，并对第二个元素对列表进行排序。

这个解决方案简单，非常有效和优雅。

如果您只想使用列表，下面的解决方案与排序算法的复杂性相同：

(defun occurrences (lst)
  (if (null lst)                                            ; [1]
      nil
      (let ((sorted (sort (copy-list lst) #'string<=)))     ; [2]
        (do ((c 1)                                          ; [3]
             (l (cdr sorted) (cdr l))                       ; [4]
             (el (car sorted) (car l))                      ; [5]
             (res nil))                                     ; [6]
            ((null l)                                       ; [7]
             (sort (cons (cons el c) res) #'>= :key #'cdr)) ; [8]
          (if (eql (car l) el)                              
              (incf c)                                      ; [9]
              (progn
                (push (cons el c) res)                      ; [10]
                (setf c 1)))))))

1. 如果列表为空，则返回零。
2. 根据元素的名称(假设它们是原子)对元素进行排序，这样相同的元素是连续的。
3. 开始循环。变量c计算找到多少个相等的元素(频率)。
4. l用于扫描排序列表。它从sorted的第二个元素开始。
5. el是当前元素，而(car l)是第二个元素。
6. res用于累积结果。
7. 当l到达列表末尾时，迭代就停止了。
8. 结果是通过将最后一对(元素、频率)添加到结果中，并按频率对其进行排序。
9. 循环的主体:如果第一个元素等于第二个元素，则增加计数器并继续迭代。
10. 否则，将找到一个新元素。因此，按旧的频率在结果上，并将计数器重置为1。

Answer 3

我想找一个更优雅的解决方案来解决以下问题。

虽然可能不是实现的最出色的方式，但它确实很短，而且snappy...and --取决于口味--更优雅：

(defun occurrences (l &optional acc)
  (if l
      (occurrences
       (remove (first l) l)
       (cons (cons (first l) (count (first l) l))
         acc))
      acc))

它计算l中第一个项目出现的次数，然后删除它们。直到l是空列表。