2015-12-12 41 views
5

Così ho una lista esempio di elementi come questoOrdina più velocemente nel racket utilizzando tabella hash

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

risposta

5

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!

+0

Grazie, sono abbastanza newbie in Racket. Non è per/hash anche l'intero hash? Ora il computer trascorre la maggior parte del tempo nella funzione di scansione. Avresti qualche suggerimento su questo? Scrivo un ciclo for/fold per la funzione scan ma funziona più o meno lo stesso. – linchi

+0

In risposta alla tua domanda: sì, 'for/hash' passa attraverso l'intera lista. La differenza è che la tua soluzione originale ha attraversato l'intera lista e, per ognuno di essi, ha esaminato l'intera lista! (In realtà, ha attraversato solo parte dell'elenco, ma non impantanarci in una discussione sulla complessità asintotica). Per rispondere alla tua seconda domanda: quanto è lunga la tua lista e quanto dura la scansione? –

+0

È troppo lungo quindi aggiungo la seconda parte alla mia domanda. – linchi