使用哈希表在球拍中排序更快

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函数将使哈希表包含唯一键和该键的重复次数(如果它捕获未编制索引的键,它将为该新键创建一个新位置,从0开始计数).

然后我想对哈希表进行排序,因为它没有排序:

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

所以结果看起来像这样:

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

现在我想截断哈希表并在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平方")运行时间.这是因为你从一个到列表的长度计数,然后对于每个索引,执行a list-ref,这需要与索引的大小成比例的时间.

这非常容易修复.

事实上,如果这是你想要的,那么没有理由对它进行排序或将其转换为列表; 只是直接过滤哈希表.像这样...

#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查看需要多长时间.对于一百万大小的列表,在我的计算机上,这需要1毫秒的测量时间.

渐近复杂度很重要!