使用哈希 table 在 racket 中排序更快

Question

所以我有一个这样的元素列表示例

(define A (list 'a 'c 'd 'e 'f 'e 'a))

现在我想根据这个样本做一个排名

(define (scan lst)
    (foldl (lambda (element a-hash) (hash-update a-hash element add1 0))
           (hash)
           lst))

结果应该是这样的：

> #(('a . 2) ('f . 1) ('e . 2) ....)

因为 `scan 函数会生成一个散列 table，其中包含唯一键和该键的重复次数（如果它捕获到一个未索引的键，它将为该新键创建一个新位置，从 0 开始计数).

然后我想对那个散列进行排序-table 因为它是未排序的：

(define (rank A)
     (define ranking (scan A))         
     (sort ranking > #:key cdr)))

所以结果应该是这样的：

#(('a . 2) ('e . 2) ('f . 1) ...)

现在我想截断哈希-table 并在 n = 1 的阈值处丢弃底部（也就是只取重复次数超过 2 次的元素）。

(define (truncate lst n)
    (define l (length lst))
    (define how-many-to-take 
        (for/list
             ([i l]
               #:when (> (cdr (list-ref lst i))
                          n))
               i))
    (take lst (length how-many-to-take)))

所以结果可能是这样的：

(('a . 2) ('e . 2))

然而，在大规模情况下，这个过程不是很有效，它需要很长时间。您对提高性能有什么建议吗？

非常感谢，

第 2 部分：

我有这个数据结构：

(automaton x 
   (vector (state y (vector a b c))  
           (state y (vector a b c)) ...))

然后我随机生成 1000 个人口。然后我使用上述功能扫描并对它们进行排名。如果我只是按原样扫描它们，已经需要很长时间了。如果我尝试将它们拼合成这样的列表

(list x y a b c y a b c...)

这需要更多时间。这是展平函数：

(define (flatten-au au)
  (match-define (automaton x states) au)
  (define l (vector-length states))
  (define body
    (for/list ([i (in-range l)])
      (match-define (state y z) (vector-ref states i))
      (list y (vector->list z))))
  (flatten (list x body)))

扫描功能看起来会有点不同：

(define (scan population)
    (foldl (lambda (auto a-hash) (hash-update a-hash (flatten-automaton auto) add1 0))
           (hash)
           population))

Answer 1

是的，我相信我看到了问题所在。你的算法有 O(n^2) ("n-squared") 运行时间。这是因为您从一开始计算列表的长度，然后 对每个索引 ，执行 list-ref，这需要的时间与索引的大小成正比。

这非常容易修复。

事实上，如果这是您想要的，真的没有理由对其进行排序或将其转换为列表；直接过滤散列table。像这样...

#lang racket

(define A (build-list 1000000 (λ (idx) (random 50))))

(define (scan lst)
    (foldl (lambda (element a-hash) (hash-update a-hash element add1 0))
           (hash)
           lst))

(define ht (scan A))

(define only-repeated
  (time
   (for/hash ([(k v) (in-hash ht)]
              #:when (< 1 v))
     (values k v))))

我添加了对 time 的调用以查看需要多长时间。对于大小为 100 万的列表，在我的计算机上，这需要 1 毫秒的测量时间。

渐近复杂度很重要！

使用哈希 table 在 racket 中排序更快

Sort faster in racket using hash table

sorting

hash

scheme

fold

racket