Dado un elemento y una matriz, el método Ruby # index devuelve la posición del elemento en la matriz. Implementé mi propio método de índice utilizando la búsqueda binaria esperando que el mío supere al de la versión incorporada. Para mi sorpresa, el built-in ejecutó aproximadamente tres veces más rápido que el mío en un experimento.Ruby # index Método VS Binary Search
Cualquier Rubyist sabe la razón por qué?
El #index is not a binary search incorporado, es simplemente una búsqueda iterativa simple. Sin embargo, está implementado en C en lugar de Ruby, por lo que, naturalmente, puede ser varios órdenes de magnitud más rápido.
Gracias. Eso es realmente extraño, sin embargo. ¿Hubo alguna razón por la cual no adoptaron el enfoque de búsqueda binaria? –
Una búsqueda binaria implica poder comparar dos elementos, en lugar de poder ver si dos elementos son iguales. También observe que la documentación dice que devuelve el * primer * objeto igual al argumento - una búsqueda binaria no siempre devolvería ese elemento. Además, mi versión de #bsearch (suponiendo que la matriz esté ordenada) no parece más lenta que #index: https://gist.github.com/1220440 –
Supongo que su implementación de #bsearch puede superar la diferencia entre Ruby y C con eso entre búsqueda binaria y búsqueda secuencial? –
¿Quién dijo que el método Ruby '# index' no estaba implementado con la búsqueda binaria? Y, además, ¿quién dijo que el método se implementó en Ruby en absoluto? :-) –
@ Platinum Azure Oh, ya veo, podría implementarse en C con búsqueda binaria. ¡Muchas gracias! –
¡Lo tienes! :-) –