Dato un elemento e un array, il metodo dell'indice Ruby # restituisce la posizione dell'elemento nell'array. Ho implementato il mio metodo di indice utilizzando la ricerca binaria in attesa che la mia sovraperformasse quella integrata. Con mia sorpresa, quello integrato ha funzionato approssimativamente tre volte più veloce del mio in un esperimento.Ruby # index Metodo VS Ricerca binaria
Qualsiasi Rubyista conosce il motivo per cui?
Lo #index is not a binary search integrato, è solo una semplice ricerca iterativa. Tuttavia, è implementato in C piuttosto che in Ruby, quindi naturalmente può essere più veloce di diversi ordini di grandezza.
Grazie. Questo è davvero strano, però. C'è stata una ragione per cui non hanno adottato l'approccio di ricerca binaria? –
Una ricerca binaria implica la possibilità di confrontare due elementi, invece di essere in grado di vedere se due elemnti sono uguali. Notate anche che la documentazione dice che restituisce il * primo * oggetto uguale all'argomento - una ricerca binaria non restituirebbe sempre quell'elemento. Inoltre, la mia versione di #bsearch (supponendo che l'array sia ordinato) non sembra più lento di #index: https://gist.github.com/1220440 –
Presumo che la tua implementazione #bsearch sia in grado di battere la differenza tra Ruby e C con quello tra ricerca binaria e ricerca sequenziale? –
Chi ha detto che il metodo Ruby '# index' non è stato già implementato con la ricerca binaria? E inoltre, chi ha detto che il metodo è stato implementato in Ruby? :-) –
@Platinum Azure Oh, vedo, potrebbe essere implementato in C con la ricerca binaria. Molte grazie! –
Hai capito! :-) –