Ordina più velocemente nel racket utilizzando tabella hash

Question

Così ho una lista esempio di elementi come questo

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

Ora voglio fare una classifica da questo campione

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

Il risultato dovrebbe essere simile a questo :

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

Perché la funzione di scansione creerà una tabella hash contenente chiavi univoche e il numero di ripetizioni di quella chiave (se cattura una chiave non indicizzata creerà un nuovo posto per quella nuova chiave, contando da 0).

Poi mi piacerebbe ordinare che hash-table perché è indifferenziati:

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

Così il risultato sarebbe simile a questa:

# (('2) (.' e2) ('f.1) ...)

Ora vorrei troncare il tavolo hash e buttare via il fondo alla soglia di n = 1 (alias solo prendere gli elementi con più di 2 ripetizioni).

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

Così il risultato potrebbe essere simile a questo:

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

Tuttavia, alla grande scala, questa procedura non è molto efficiente, ci vuole troppo tempo. Avresti qualche suggerimento per migliorare le prestazioni?

La ringrazio molto,

Parte 2:

ho questa struttura di dati:

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

Poi ho generare casualmente una popolazione di 1.000 di loro. Quindi li scannerizzo e li classifico usando le funzioni di cui sopra. Se li scrivo così com'è, ci vuole già molto tempo. Se provo ad appiattirli in una lista come questa

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

ci vorrebbe ancora più tempo. Ecco la funzione Appiattisci:

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

La funzione di scansione avrà un aspetto un po 'diverso:

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

Answer 1

Sì, credo che vedo il problema. Il tuo algoritmo ha O (n^2) ("n-quadrato") tempo di esecuzione. Questo perché stai contando da uno alla lunghezza della lista, quindi per ogni indice, eseguendo uno list-ref, che richiede tempo proporzionale alla dimensione dell'indice.

Questo è super facile da risolvere.

In effetti, non c'è davvero alcun motivo per ordinarlo o convertirlo in un elenco se questo è ciò che si desidera; basta filtrare direttamente la tabella hash. Ti piace questa ...

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

ho aggiunto la chiamata a time per vedere quanto tempo ci vuole. Per un elenco di dimensioni pari a un milione, sul mio computer questo richiede un tempo misurato di 1 millisecondo.

La complessità asintotica è importante!