在 Racket 的列表中查找出现次数最多的元素

Question

如何找到列表中出现次数最多的元素？

如果有更多相同的号码，任何一个都可以return编辑。

例如，对于列表 '(1 3 3 4 2 2)，函数可以 return 2 或 3。

我想我可以计算每个元素出现的次数，然后 select 计算最大值，但这似乎效率不高。有没有更好的方法，甚至更好的内置函数？

Answer 1

如果在计数之前对列表进行排序，您的效率会稍微高一些。然后所有具有特定值的元素将一起出现在列表中。然后，当您完成示例列表中 2 的计数时，您不必再保留 1 的数量，因为您的函数已经知道 1 不是出现次数最多的元素。

Answer 2

A R6RS Scheme O(n) version using SRFI-69 hash tables

#!r6rs
(import (rnrs base)
        (srfi :69))

(define (max-occurence lst)
  (define hash (make-hash-table))
  (define zero (lambda () 0))
  (let loop ((lst lst) (mfreq 0) (mcur #f))
    (if (null? lst)
        mcur
        (let* ((element (car lst)) (freq (+ 1 (hash-table-ref hash element zero))))
          (hash-table-set! hash element freq)
          (if (> freq mfreq)
              (loop (cdr lst) freq element)
              (loop (cdr lst) mfreq mcur))))))

A #!racket 版本非常相似，除了惯用版本会选择不可变哈希表。

#!racket

(define (max-occurence lst)
  (let loop ((hash (make-immutable-hash)) (lst lst) (mfreq 0) (mcur #f))
    (if (null? lst)
        mcur
        (let* ((element (car lst)) (freq (add1 (hash-ref hash element 0))))
          (if (> freq mfreq)
              (loop (hash-set hash element freq)
                    (cdr lst)
                    freq
                    element)
              (loop (hash-set hash element freq)
                    (cdr lst)
                    mfreq
                    mcur))))))

如果您遇到列表的性能问题，我想您会看到其中任何一个都有很大的改进。更改为 #!racket 中的可变哈希表会使速度加倍，但我怀疑你是否需要它。

Answer 3

这里有一个基于 Racket hash tables 的解决方案。

#lang racket
(define (most-frequent-element xs)
  (define ht (make-hash))
  (for ([x xs]) (hash-update! ht x add1 0))
  (for/fold ([max-x #f] [max-count 0]) ([(x c) ht])
    (if (> c max-count)
        (values x c)
        (values max-x max-count))))

示例：

> (most-frequent-element '(a b c c d a a b c a))
'a
4

这是 argmax 的解决方案。不幸的是它需要从散列 table 到列表的转换。

#lang racket

(define (most-frequent-element xs)
  (define ht (make-hash))
  (for ([x xs]) (hash-update! ht x add1 0))
  (argmax (λ (x) (hash-ref ht x 0)) 
          (hash->list ht)))

示例：

> (most-frequent-element '(a b c c d a a b c a))
'(a . 4)

在 Racket 的列表中查找出现次数最多的元素

Find the element with most occurrences in a list in Racket

scheme

racket