martes, octubre 28, 2008

Algoritmos de busqueda en texto (continuación...

Continuando con la discusión acerca de los algoritmos de busqueda de texto dentro de texto;
De mi ultima charla con el profesor Edgar Casasola, salto a la vista que estos algoritmos resultan ser mas eficientes que el simple indexOf de Java, cuando la cadena de entrada (la cadena de búsqueda), es mayor a 7000 caracteres. Cambie ligeramente el algoritmo para incrementar paulatinamente el tamaño de la cadena, a continuación los resultados:

Con una cadena de 419 caracteres:
text size = 419
Contains algo: 0
StringSearch algo: 15


El algoritmo de Java funciona mejor.

text size = 756
Contains algo: 16
StringSearch algo: 15

Con 756, el Boyer, Moore se empieza a meter en la pelea. (Similar resultado para 3947 caracteres)

A partir de los 7909, la ventaja en perfomance del B.M es palpable:

text size = 7909
Contains algo: 125
StringSearch algo: 94

text size = 19678
Contains algo: 313
StringSearch algo: 187
razón: 59%

text size = 39532
Contains algo: 594
StringSearch algo: 391
razón: 62%

text size = 78630
Contains algo: 1218
StringSearch algo: 766
razón: 62%

text size = 157744
Contains algo: 2438
StringSearch algo: 1515
razón: 62%

text size = 315454
Contains algo: 5015
StringSearch algo: 3282
razón: 65%


A la luz de los resultados, podemos resumir: Para analizar cadenas pequeñas (menos de 7000 caracteres), el indexOf al no tener pre-procesamiento de la cadena entrante, resulta mas eficiente. En cadenas mayores a 7000 caracteres, el incremento promedio en el perfomance de la búsqueda, es de un 60%.

Lo anterior nos da un criterio para utilizar una u otra solución, como usted querido lector ya se habrá dado cuenta; en el caso de tener un promedio de cadenas de entradas menores a 7000 o 5000 caracteres, el algoritmo de Java (java.lang.String.contains), funciona bastante bien. Para colecciones de mayor peso, los algoritmos de RI superan considerablemente a los algoritmos simples de Java.

Trea bien!

No hay comentarios.: