Quale funzione è la migliore in termini di efficienza e tempo di utilizzo dello stack

Ho scritto 3 funzioni che contano il numero di volte in cui un elemento viene visualizzato in un elenco. Ho provato vari input e li ho profilati, ma non so ancora quale funzione sia la migliore in termini di efficienza di utilizzo dello stack ed efficienza temporale. Per favore aiutatemi.Quale funzione è la migliore in termini di efficienza e tempo di utilizzo dello stack

;; Using an accumulator 
    (defn count-instances1 [a-list an-element] 
     (letfn [(count-aux [list-aux acc] 
         (cond 
          (empty? list-aux) acc 
          :else (if (= (first list-aux) an-element) 
            (count-aux (rest list-aux) (inc acc)) 
            (count-aux (rest list-aux) acc))))] 
     (count-aux a-list 0))) 

;; Normal counting 
    (defn count-instances2 [a-list an-element] 
    (cond 
     (empty? a-list) 0 
     :else 
      (if (= (first a-list) an-element) 
       (+ 1 (count-instances2 (rest a-list) an-element)) 
       (count-instances2 (rest a-list) an-element)))) 

;; using loop. does this help at all? 
    (defn count-instances3 [a-list an-element] 
     (loop [mylist a-list acount 0] 
      (if (empty? mylist) 
       acount 
       (if (= (first mylist) an-element) 
       (recur (rest mylist)(inc acount)) 
       (recur (rest mylist) acount)))))

fonte

2009-07-22 unj2

Quali sono stati i risultati dei vostri sforzi di profilazione? –

'defn' annidato probabilmente non fa quello che pensi. 'defn' definisce sempre una funzione di livello superiore. Puoi usare 'letfn' (o anche' (let [f (fn ...)]) ') se vuoi definire una funzione interiore. –

Grazie Brian. Ma non riesco a far funzionare il letfn. Potresti modificare la mia domanda con letfn? Molte grazie. – unj2

La versione anello/persistono, è la strada giusta. Clojure non può ottimizzare le chiamate di coda a causa delle limitazioni della JVM.

fonte

2009-07-22 21:01:06 Svante

Non è accurato. Dovresti dire che Clojure * sceglie * di non ottimizzare le chiamate di coda, perché è piuttosto difficile da ottenere in una lingua (Java) che non le possiede già. Di fatto esistono alcune implementazioni di linguaggi (ad es. SISC - http://sisc-scheme.org/) in cima alla JVM che ottimizzano le chiamate di coda. –

Questo è davvero strano. Perché non dovrebbe voler ottimizzare le chiamate tail? Ci avrebbe risparmiato un sacco di problemi? Ci sono trade off? – unj2

'recur' è bello perché è esplicito e puoi solo usarlo dalle posizioni di coda (il compilatore si lamenta in caso contrario) che cattura le istanze in cui pensi che stai ricalcando la coda ma non lo sei. Potrebbe essere tutto automaticamente rimosso, ma non è poi così complicato sostituire il nome della tua funzione nella coda con il simbolo 'recur'. –

Scrivere il codice in modo che il compilatore/interperter possono essere regolate per ricorsione in coda, dovrebbe portare ad un aumento delle prestazioni e stack riduzione del loro utilizzo. Penso che la tua normale funzione di conteggio possa qualificarsi per la ricorsione della coda in modo che uno debba essere abbastanza veloce. Non sono sicuro dato che mi diletto in Lisp solo per hobby.

http://en.wikipedia.org/wiki/Tail_recursion

fonte

2009-07-22 20:45:27 anio

Clojure non è in grado di ottimizzare le chiamate di coda a causa delle limitazioni della JVM. – Svante

Il commento di Rich Hickey su questo era che era meglio avere un'astensione esplicita che funziona sempre (recidiva) di quella implicita che funziona quasi tutto il tempo (a causa della complessità di farlo sulla JVM) –

@Svante - Clojure può e fa ottimizzare le chiamate di coda. Devi solo essere esplicito che lo vuoi usando 'recur' (che era una scelta di design del linguaggio di Rich Hickey). La maggior parte del tempo è possibile eseguire TCO sulla JVM. Le limitazioni JVM influiscono solo sulla ricorsione reciproca reciproca (che in realtà è un caso piuttosto raro). – mikera

Quale funzione è la migliore in termini di efficienza e tempo di utilizzo dello stack

risposta

Problemi correlati