Quale è più veloce in ruby: una ricerca hash o una funzione con un'istruzione case?

Question

Abbiamo alcuni punti in uno script time-critical in cui convertiamo i vecchi ID in stringhe. Al momento, usiamo dichiarazioni caso all'interno di una funzione, in questo modo:

def get_name id 
    case id 
    when 1 
     "one thing" 
    when 3 
     "other thing" 
    else 
     "default thing" 
    end 
end 

Sto pensando di sostituire questo con una ricerca hash, in questo modo:

NAMES = { 
    1 => "one thing", 
    3 => "other thing", 
} 
NAMES.default = "default thing" 

Ci si sente come dovrebbe essere più veloce da usare NAMES[id] rispetto a get_name(id) - ma è così?

Answer 1

Un paio di punti, primo. Uno è che costrutti linguistici di basso livello come questo che più o meno fanno la stessa cosa non sono quasi mai il collo di bottiglia in qualsiasi applicazione del mondo reale, quindi è (spesso) folle concentrarsi su di essi. In secondo luogo, come è già stato detto, se sei davvero preoccupato, dovresti metterlo a confronto. Gli strumenti di benchmarking e di profilo di Ruby non sono certamente i più avanzati nell'ecosistema di programmazione, ma svolgono il loro lavoro.

Il mio istinto è che gli hash saranno più veloci perché (ancora, suppongo) la dichiarazione del caso deve controllare ogni condizione a sua volta (facendo trovare gli elementi O (n) invece di O (1)). Ma controlliamo!

Codice completo di benchmarking allo https://gist.github.com/25 Fondamentalmente, genera un file che definisce il caso/hash appropriato e quindi li utilizza. Sono andato avanti e ho inserito la ricerca dell'hash all'interno di una chiamata al metodo, in modo che l'overhead non sia un fattore, ma nella vita reale non c'è motivo per cui debba essere bloccato all'interno di un metodo.

Ecco cosa ricevo. In ogni caso, sto facendo 10.000 ricerche. Il tempo è user-tempo in secondi

Case statement, 10 items 0.020000 
Hash lookup, 10 items  0.010000 

Case statement, 100 items 0.100000 
Hash lookup, 100 items  0.010000 

Case statement, 1000 items 0.990000 
Hash lookup, 1000 items  0.010000 

Così, sembra molto simile alla istruzione case è O (n) (senza shock lì). Si noti inoltre che le ricerche 10K sono ancora solo un secondo anche nell'istruzione case, quindi, a meno che non si stia facendo una metrica con il carico di queste ricerche, è meglio concentrarsi sul resto del codice.

Answer 2

case when ha n complessità.
hash lookup ha ln (n) complessità, ma utilizzando un oggetto aggiuntivo (hash) e chiamando i suoi metodi ha una sua penalità.

Quindi, se si dispone di molti casi (migliaia, milioni, ...) la ricerca hash è migliore. Ma nel tuo caso, quando hai solo 3 varianti, lo case when ovviamente sarà molto più veloce.

Answer 3

Perché non utilizzare un'istruzione case in linea nella parte time-critical del codice, piuttosto che renderla una propria chiamata di funzione? Ciò evita il sovraccarico di uno stack di chiamate ed evita anche il sovraccarico di una ricerca hash.

È anche possibile fare sempre un punto di riferimento. Fai qualcosa del genere:

t = Time.now 
1_000_000.times { ...your code... } 
secs = Time.now - t 

Sostituire "il tuo codice" con ciascuna opzione.

Answer 4

Dal momento che questo dipende da una serie di fattori (quanti ID diversi che si desidera convertire, come intelligentemente il compilatore può compilare i case when statemens), il mio consiglio è: misurare:

scrivere un piccolo prova la routine e converti, ad esempio, 10.000.000 ID in stringhe. Fatelo un paio di volte con entrambe le implementazioni e confrontate i risultati. Se non hai alcuna differenza significativa, prendi quello che ti piace di più (penso che la soluzione hash sia un po 'più elegante ...)

Answer 5

Come ha detto Martin, dipende da quanti ID si desidera controllare. Stai selezionando l'ID e le stringhe corrispondenti dal database o vuoi hardcodificarlo. Se ci sono solo un paio di assegni, allora puoi andare con CASE. Ma non è possibile modificare la coppia ID/stringa, se necessario.

D'altra parte, se si selezionano molti ID da un database, è possibile utilizzare qualcosa come Dizionario per memorizzare coppie nome/valore.

Mentre un dizionario è in memoria, la ricerca potrebbe essere veloce.

Ma alla fine, tutto dipende dal fatto che si stia lavorando con coppie ID/stringa in continua evoluzione o poche costanti.

Answer 6

$ ruby -v 
ruby 1.9.2p0 (2010-08-18 revision 29036) [i686-linux] 

$ cat hash_vs_case.rb 
require 'benchmark' 

def get_from_case(id) 
    case id 
    when 1 
     "one thing" 
    when 3 
     "other thing" 
    else 
     "default thing" 
    end 
end 

NAMES = { 
    1 => "one thing", 
    3 => "other thing", 
} 
NAMES.default = "default thing" 

def get_from_hash(arg) 
    NAMES[arg] 
end 

n = 1000000 
Benchmark.bm do |test| 
    test.report("case 1") { n.times do; get_from_case(1); end } 
    test.report("hash 1") { n.times do; get_from_hash(1); end} 
    test.report("case 42") { n.times do; get_from_case(42); end } 
    test.report("hash 42") { n.times do; get_from_hash(42); end} 
end 

$ ruby -w hash_vs_case.rb 
     user  system  total  real 
case 1 0.330000 0.000000 0.330000 ( 0.422209) 
hash 1 0.220000 0.000000 0.220000 ( 0.271300) 
case 42 0.310000 0.000000 0.310000 ( 0.390295) 
hash 42 0.320000 0.010000 0.330000 ( 0.402647) 

e qui è il motivo per cui si desidera aggiornare:

$ ruby -v 
ruby 1.8.7 (2009-06-12 patchlevel 174) [i486-linux] 

$ ruby -w hash_vs_case.rb 
     user  system  total  real 
case 1 1.380000 0.870000 2.250000 ( 2.738493) 
hash 1 1.320000 0.850000 2.170000 ( 2.642013) 
case 42 1.500000 0.960000 2.460000 ( 3.029923) 
hash 42 1.890000 0.890000 2.780000 ( 3.456969) 

Answer 7

Ecco un esempio che mostra il caso più veloce per la ricerca del simbolo. Gli esempi precedenti erano chiavi basate su interi.

https://gist.github.com/02c8f8ca0cd4c9d9ceb2