Ir al contenido principal

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!
Etiquetas:

Comentarios

Publicar un comentario

Entradas más populares de este blog

Impensando acerca de las referencias en Java

Fue hace ya algún tiempo que pase un rato discutiendo con algunos compañeros acerca de si existe o no el paso por referencia; el discurso fue mucho hacia que en Java el comportamiento, en el supuestamente pasamos por referencia un objeto y por valor los objetos primitivos creo mucha polémica. Para ubicarnos en contexto veamos el siguiente ejemplo. public static void main(String[] args) { int value = 10; changeValue(value); System.out.println("value = " + value); User user = new User(); Name name = new Name(); user.setName(name); name.setName("jsanca"); name.setLastName("XXX"); user.setPassword("123queso"); System.out.println("user: " + user.getName().getName() + ", " + user.getName().getLastName() + ", " + user.getPassword()); changeValue1(user); System.out.println("user: " + user.getName().getName() + ", " + user.getName().getLastName() + ", " + user.ge...
11 comentarios
Leer más

Al fin MTV reconoce el potencial de la Internet

Después de mucha lucha y denuncias públicas y demás pleitos para llamar la atención, la cadena mundial de música por televisión mas grande el mundo MTV , abren toda su biblioteca (bueno casi toda, el material en ingles por el momento), al publico. Aseguran tener conciertos, espectáculos acústicos , más todos sus vídeos y a diferencia de YouTube (que es mantenida por una comunidad en buena parte), esta es soportada por MTV , lo que le proporciona idéntica calidad a cada uno de sus temas ( vídeos ), el sitio en donde han publicado el contenido le llaman MTV Music , y yo debo reconocer que estoy como chiquito con juguete nuevo, jejeje . El sitio ofrece una gran cantidad de música , como señale anteriormente y además realiza sugerencias acerca de música o vídeos relacionados, en las búsquedas , te de la oportunidad de ir a un perfil del artista o directamente a los vídeos . Buena noticia y supongo que a MTV le paso como dicta el viejo adajio , " si no puedes vencerlos, unet...
Publicar un comentario
Leer más

Ideas para un eco-hogar

Un Eco Hogar, Ultimamente he estado pensando al respecto (en la implementación de una casa ecológica), leyendo un poco me entero que existen diferentes alternativas para el ahorro de consumo electrico del hogar; paneles solares, mini hidro turbinas, energía eólica, etc. Algunas alternativas interesantes representan los termos calentados por paneles solares, para no gastar energía en la ducha caliente, etc. Todas estas alternativas están muy bien, aunque la inversión por el momento es algo grande para un hogar promedio, con el consumo masivo, podría convertirse en una opción de facto. Estas opciones representa un ahorro en el consumo eléctrico, pero que hay con el consumo del H2O; sin necesidad de ser muy observador, nos damos cuenta que uno de los mayores puntos donde se desperdicia agua son: el baño y la ducha. En cuanto a la ducha no se me ocurre mas que algunos habitos en vez de soluciones tecnicas, como mojarse, cerrar el tuvo, enjabonarse, etc. Cerrar el tuvo cuando no lo estamos ...
3 comentarios
Leer más