在Racket中使用哈希表进行更快的排序

Question

在Racket中使用哈希表进行更快的排序

5

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

(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))

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

非常感谢，

第二部分：

我有这个数据结构:

(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...)

如果需要，这将需要更多的时间。这是“flatten”函数：

(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))

- Linh Chi Nguyen

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Clements · Accepted Answer

没错，我相信我看出了问题所在。你的算法具有O(n^2)（"n平方"）的运行时间。这是因为你从1数到列表的长度，然后对于每个索引，执行一个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毫秒。

渐进复杂度非常重要！