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!

lunes, octubre 27, 2008

Algoritmo Boyer, Moore, Horspool, Raita vrs java.lang.String.contains

En mi paso por la Universidad, entre los cursos de Licenciatura tuve la suerte de llevar el curso de Recuperación de Información (RI), con el prof. Edgar Casasola.

A continuación un extracto del correo, que recientemente le escribí comentandole una cuestión acerca de la comparación de los algoritmos Boyer, Moore, Horspool, Raita vrs java.lang.String.contains; los resultado a la luz de mi pequeño estudio, arrojaron que el "perfomance" para buscar al menos una ocurrencia de texto dentro de otro, del objeto de Java resulta mas eficiente que las técnicas RI, mas elaboradas.

---------------*-----------------------------*--------------------------
.....

Para comentarle el contexto; Actualmente trabajo para la compañía avVenta en Costa Rica y como parte de un proyecto para uno de sus clientes, existía una implementación que toma un archivo con palabras vulgares o obscenas y realiza una búsqueda a fuerza bruta (O(n)), recorriendo todas las palabras hasta encontrar la ocurrencia de una de las palabras en el texto, el pseudo-stremmer que tiene este algoritmo, consiste en agregar palabras sobre el corpus de las obscenidades, pero cambiando por ejemplo las “o” por un “0” (cero), o la “a” por un (4), etc.

 

Me pregunte que desempeño tendría esta implementación contra la búsqueda vectorial y contra algoritmos de búsqueda de texto dentro de texto.

 

Además de un algoritmo “custom” que el cliente me facilito (valga decir que es el mas deficiente a nivel de resultados, sin embargo vale resaltar, el mismo tiene “stremmers” para diferentes lenguajes y soporte para búsqueda i18n), también hice una prueba con Apache Lucene (la implementación de un buscador vectorial Open de Apache, http://lucene.apache.org/java/docs/index.html), utilizando un Índice invertido en memoria, además utilice el algoritmo, que según leí es mas rápido de esta biblioteca (http://johannburkard.de/software/stringsearch/), el cual se basa en un hibrido de Boyer, Moore, Horspool, Raita, los resultados en milisegundos y orden descendiente los comparto a continuación.

 

{203=implementación basada en java.lang.String.contains (indexOf > -1)

 2266=implementación basada en Apache Lucene

 2312=implementacion basada en el stringsearch (http://johannburkard.de/software/stringsearch/),

 11406=obscenityProfanityFilter, este fue un algoritmo propietario que me pasaron, el mismo que tiene los stremmer.

}

 

Valga decir que hice otros “Junit” (pruebillas de unidad) para determinar que la funcionalidad de los algoritmos fuera idéntica y en efecto, todos funcionan de la manera esperada.

 

Dudoso con los resultados, fui curioso e implemente el siguiente código:

 

String text = "Hello folkes jiji opa oop upa lupa as and tropes and listes and shomis and tepos";

              String wordToSearch = "shomis";

              int loop = 2000;

              long millins = 0;

              long totalElapse = 0;

              int hit = 0;

              StringSearch so = new BoyerMooreHorspoolRaita();

 

              millins = System.currentTimeMillis();

              for (int i = 0; i <>

 

                     if (text.contains(wordToSearch)) {

 

                           hit += 1;

                     }

              }

 

              wordToSearch = "upalupa";

 

              for (int i = 0; i <>

 

                     if (text.contains(wordToSearch)) {

 

                           hit += 1;

                     }

              }

 

              totalElapse = System.currentTimeMillis() - millins;

 

              System.out.println("Contains algo: " + totalElapse);

              System.out.println(hit + " = " + loop);

 

              // **********************

              // **********************

              // **********************        

 

              hit = 0;

              wordToSearch = "shomis";

             

              millins = System.currentTimeMillis();          

              for (int i = 0; i <>

 

                     if (so.searchString(text, wordToSearch)!= -1) {

 

                           hit += 1;

                     }

              }

             

              wordToSearch = "upalupa";

 

              for (int i = 0; i <>

 

                     if (so.searchString(text, wordToSearch)!= -1) {

 

                           hit += 1;

                     }

              }

              totalElapse = System.currentTimeMillis() - millins;

 

              System.out.println("StringSearch algo: " + totalElapse);

              System.out.println(hit + " = " + loop);

 

El resultado:

 

Contains algo: 0

2000 = 2000

StringSearch algo: 15

2000 = 2000

 

Dejando de lado que la implementación de StringSearch permite utilizar “wildcard” y que quizá funcione mejor en colecciones grandes (esto es un supuesto), me pareció interesante compartir estos resultados con alguien que esta mas comprometido con el tema, como comprenderá el mercado nacional, nos proporciona poco espacio para jugar con este tipo de cosas muy interesantes y el conocimiento que no se refresca tienen a marchitarse un poco (lo cual es una pena).

......

Operadores en Java

En esta entrega vamos a ver algunos de los operadores con los cuales cuenta Java.

Aritméticos

Los operador aritméticos nos sirven básicamente para realizar operaciones matemáticas, del tipo de suma, resta, etc. Funcionan en todos los tipos numéricos que vimos anteriormente, como enteros, long, etc.
  • Suma
     int i = a + c + 1; i += 2;
  • Resta
     int i = a – c; i -= 2;
  • División
      int i = 4 / 2; i /= 2;
  • Multiplicación
      int i = 4 * 2; i *= 2;
  • Incremento
      ++i or i++.
  • Residuo
      int i = 4 % 2; i %= 2;
  • Decremento
      --i or i--

A continuación un ejemplo:
public static void doArithmetic() {

int i = 0;
int step = 0;

System.out.println("Initial value: " + ++step + " = " + i);

i = 2 + 2;

System.out.println(++step + " = " + i);

i += 2;

System.out.println(++step + " = " + i);

i = i - 4;

System.out.println(++step + " = " + i);

i -= 1;

System.out.println(++step + " = " + i);

i++;

System.out.println(++step + " = " + i);

i *= 2;

System.out.println(++step + " = " + i);

i += 1;
System.out.println(++step + " = " + (i % 2));
System.out.println(++step + " = " + (i / 2));

--i;

System.out.println(++step + " = " + (i % 2));
}

Operadores lógicos y algunos ejemplo de instrucciones condicionales

&, |, ^, >>, <<, !

De orden izquierdo a derecho; and,or y xor logicos, operador de shift y negación.

==, >, >=, =<, <, != , ?:

De orden izquierdo a derecho; comparador igual, mayor, mayor igual, menor igual, menor, diferente, operador ternario.

Veamos un ejemplo:

public static void doLogicalAndConditional() {


int i = 3;

int x = 3;


int j = i <<>

int m = (int) Math.pow(2.0, x) * i;


System.out.println("j = " + j + ", m = " + m);


i = m;

j = i >> x; // i * 2^x

m = i / (int) Math.pow(2.0, x);


System.out.println("j = " + j + ", m = " + m);


if (i == 3) {


System.out.println("I is equal to 3");

}


if (m != 3) {


System.out.println("I is diff to 3");

}


int a = 1;

int b = 0;

int c = 1 & 0;


System.out.println("c = " + c);


c = 1 | 0;


System.out.println("c = " + c);

c = 0 ^ 0;


System.out.println("c = " + c);


c = 1 ^ 0;


System.out.println("c = " + c);

if (!(c == 0)) {

// ... do something.

}

}


martes, octubre 21, 2008

Primera Reunion del JUG

Hey gente,

La espera esta apunto de terminar, la primera reunión del Java User Group en Tiquicia, va tener lugar este Jueves a las 2 P:M, en el auditorio de la ULatina.

Quien se apunta a llegarle, va estar realmente cool, no solo por lo expositores, si no también por conocer a la comunidad Java del país, ojala un intercambio de impresiones, yo que sé, hablar paja.

Si alguien de avVenta, va llegar al evento, no duden en avisar, para llegar con alguien.

Tuanis,
J

Guía de posicionamiento - Ojo buscador

Desde el Ojo buscador, nos lleva la guía de posicionamiento.
Según leo en el sitio, esta guía podrá ser comprada, tanto en su versión digital, como en papel, además se puede acceder on-line, aquí el link a la noticia.

lunes, octubre 20, 2008

Nuevo podcast - Javahispano

Saludos,

Ya tenemos nuevo podcast en Java Hispano, estuve escuchándolo ayer tarde y les puedo decir que el mismo esta muy interesante. Ahora se trata de una entrevista con Carlos Sanchez, este señor es un español que se a podido mezclar entre las filas de variados proyectos open source, que van desde Spring Security, Codehaus, Fundacion EclipseFundacion Apache (Maven).
Nos comenta la forma en que se pudo meter a estas fundaciones y un poco de lo que ha estado haciendo.

domingo, octubre 19, 2008

Eclipse breve guía


A continuación intentaremos dar una breve introducción al Eclipse IDE.

Instalación

La instalación del IDE, resulta muy sencilla, simplemente descarge las versión mas estable y nueva que existe (yo en lo personal estoy utilizando Europa).

Una vez que la descargues a tu maquina, solo debes descomprimirla y ejecutar el archivo eclipse.exe.

Workspace

Inicialmente eclipse necesita una carpeta (cualquier carpeta), para almacenar la meta información de los proyectos que vamos a almacenar, así pues, crea la carpeta  "javacourse" yseleccionalá al inicio, cuando tu eclipse arranque.

En primera instancia, verás una pantalla azul, la cual contiene ciertos tópicos, como donde empezar, acerca de eclipse, etc. Por el momento no es relevante así que cierrala y continua con eclipse.

Lo primero que vamos hacer, es crear un proyecto, para ello vamos al espacio de trabajo, en la cejilla de "Project Explorer" y da clic derecho (ver imagen 1).

Una vez ahí, ponle un nombre al proyecto, por ejemplo, clase 1 y listo.

Una vez creado el proyecto, veremos una carpeta (con el nombre clase 1) y dentro de ella, una carpeta con el nombre de src (en esta almacenaremos nuestros paquetes, clases y recursos, necesarios para los programas Java), ver imagen 2.

Creando clases, archivos de recursos y paquetes.

Como parte de los archivos que podemos utilizar en 
un programa Java, se encuentran los paquetes (s
imples carpetas con alguna estructura jerárquica), archivos Java (simples archivos de texto, con el código de nuestros programas), archivos de recursos (también simples archivos de texto, los cuales se encuentran organizados en llave, valor y son fuertemente soportados en Java), tambiénpodemos colocar imagenes, archivos XML, casi cualq
uier cosa, pero debemos recordar que lo que coloquemos aquí, será eventualmente empaquetado en un archivo jar, para posteriormente ser cargado en nuestro classpath, desde donde serán visibles por nuestro "class loader".

Para crear un paquete o una clase, damos:

clic derecho sobre src > New >Package > por ultimo en la casilla de name, colocamos nuestro paquete, por ejemplo com.avventa.training.jav
a.class1.

El proceso, para crear una clase resulta muy similar, solo que elegimos Class en vez de Package.
En el mismo cuadro de dialogo podemos, indicar un paquete diferente (si no existe, este se crea), indicar una o mas interfaces a implementar y la clase base (en caso de no colocar ninguna en
 especifico, heredamos de java.lang.Object, el objeto padre de todos en Java).

Explorando mi Eclipse


Si vamos la imagen 3, vamos que en el titulo se encuentra el recurso, con la dirección que actualmente se encuentra abierta.

Debajo tenemos los "items" como file, edit, source, etc;  Los dos primeros y el ultimo (Help), sonestándares.

Source, contiene funcionalidades para manipular el código, formatear, etc.
Refactor, contiene funcionalidades para refactorizar el código.
Navigate, contiene funcionalidades para abrir declaraciones, tipos (buscar clases en el classpath), buscar una linea, etc.
Search, busca archivos, archivos Java, texto, referencias, declaraciones, etc.
Project, utilidades para compilar y manipular el proyecto.
Run, disparará nuestras clases, tanto en debug como modo normal.

El Package Explorer, nos permites navegar y buscar entre nuestros proyectos (los que se encuentren en nuestro espacio de trabajo).

Outline, muestra los miembros y propiedades de la clase, entre otros puedes agregar o quitar laslengüetas que quieras.

Por ultimo, en la parte inferior podemos encontrar los problems (errores de sintaxis, advertencias), anotaciones del JavaDoc, la consola, etc.



Image 1




Imagen 2





Imagen 3






Temario Curso de Java

Como les comente hace algunos días, inicié un curso de Java básico en la compañia avVenta.
A continuación les dejo los temarios y como se habrán dado cuenta, intentaré ir colgando en el blog, información (un pequeño resumen) de los temarios del curso.

Java Basic for 5.0 version.

Java Basic #1

11 hours


  • Brief Introduction of Java. (1 hour)

  • Installation and tools (Overview of Eclipse IDE) (1 hour)

  • Type data (1/2 hour)

    • Primitive Types.

    • Custom types.

    • Var names.

    • Constants.

  • Brief introduction to standard coding.

    • Operators (1/2 hour)

    • Arithmetic operators.

    • Conditional operators.

  • Flow Control (1 hour)

    • If-else

    • Switch

    • Do… While

    • For (foreach)

  • Arrays and Strings (1 hour)

    • Arrays.

    • Strings.

    • Buffering.

  • Classes in Java (2 hours)

    • Constructors

    • SuperClass.

    • Interfaces.

    • Public, Private, package, abstract, final.

    • Anonymous class.

    • Inner class.

    • Overriding.

    • Pass by value.

    • Pass by reference: We need to be careful here - Java only has by-value parameters. The "by reference" is an illusion - you're actually passing the value of
      the reference as the parameter. This distinction is important because
      it differs greatly from what other languages such as C++ permit.

  • Exception control (1 hours)

    • Concept of exception in Java.

    • Try, catch, finally.

    • Creating Custom Exceptions

    • Hierarchy exceptions and context (Throwable , Runtime and Exception)

  • Classes in JDK

    • Class object. (1/2 hour)

    • Equal method and Comparable interface (1 hour).

    • HashCode method (1/2).

    • Java Lang (1 hour)

      • Integer, Long, Double, Buffering, String, Math.


Java Basic #2

10 hours



  • Classes in JDK


    • Multi-threaded (2 hours).

      • Thread class.

      • Runnable interface.

      • ThreadGroup.

    • Java Util package. (4 hour)

      • Collections and Generics.

      • Logs.

      • Zip, RE.

    • Java Text package. (2 hour)

      • Collators, DateFormat, NumberFormat, MessageFormat.

    • Java IO. (2 hours)

      • File, Writer’s, Reader’s. Input and Output, Tokenizer’s.



Java Basic #3

11 hours


  • Classes in JDK


    • Java Thread Second Part (3 hours)

      • Monitors, synchronization, mutex: It would be wise to discuss both standard synchronization, and
        manual lock-based synchronization.

    • Java NIO (2 hours)

      • Add here the java nio topics.

    • Java Net (2 hours)

      • InetAddress.

      • ServerSocket, Socket.

      • URL, HttpURLConnection, URL, URLConnection, Decoder & Encoder.

    • Java Reflect and Beans. (4 hours)

      • ClassForName.

      • Constructor, Field, Method, BeanInfo, BeanDescriptor, PropertyDescriptor, XMLDecoder, XMLEncoder, Annotations.


Java Basic #4

10 hours


  • Classes in JDK


    • Java Security and Crypto (2 hour)

      • Digest (MD5), Key’s, Provider, Algorithm’s, etc.

    • Java Image (1 hour)

      • How create and manipulate an image.

    • Java SQL (4 hours)

      • JDBC, Connection, Statement, ResultSet.

    • Java XML (3 hours)

      • DOM and SAX. JAXB


Java Basic #5

10 hours


  • Classes in JDK


    • Java Swing and Awt (4 hours)

      • JFrame. JPanel, JInternalFrame.

      • JTextField, JButton, JList, JTree, JTable.

    • Java and Applet’s (3 hours)

    • Review of the Java Sun Coding guidelines. (2 hours)

    • Java and Java Web Start (Overview). (1 hour)

viernes, octubre 17, 2008

Nombres de variables

En Java como en muchos otros lenguajes, existen convenciones para codificar, a continuación proporcionaremos algunos lineamientos para los nombres de variables.

Regularmente un nombre de variable inicia en minúscula, el mismo debería ser lo mas identificativo al propósito o aspecto que esta cubriendo, también se suele capitalizar los diferentes pronombres que tienen la variable, vamos un ejemplo:

Persona carlos = new Hijo ();

Persona maria = new Hija ();

Persona jose = new Padre ();
Persona carla = new Madre ();

Familia familiaCarmona = new NucleoFamiliarBasico();

familiaCarmona.add(jose);
familiaCarmona.add(carla);
familiaCarmona.add(carlos);
familiaCarmona.add(maria);

En este ejemplo, vemos que los nombres tanto de las variables, como de los métodos ("add"), se encuentran en minúsculas.
En el caso de la familia Carmona, se capitaliza el segundo nombre y en el caso de los nombres de las clases, estas se encuentra en mayúscula, mismo caso de capitalización para la clase "NucleoFamiliarBasico".

Ademas de los metodos y los nombres de variables, podemos hacer uso de constantes o valores para las  enumeraciones, en ambos casos; los nombres van totalmente en mayusculas y en vez de capitalizarlos, se utiliza un "_" para dividir los pronombres o aspectos, volvamos al ejemplo:


Persona carlos = new Hijo ();
carlos.setSexo (Persona.SexoType.MASCULINO);  // Aquí el nombre de la enumeración sigue los estándares de las variables, pero el valor "MASCULINO" va conforme a el estándar de una constante.

carlos.setDescripcion(Persona.SIN_DESCRIPCION);  // SIN_DESCRIPCION es una cadena que indica que el tipo en cuestión aun no cuenta con una descripción, observe la forma en como se dividen los tokens, se utiliza una "_" y toda la palabra se encuentra en minúscula.

Por ultimo, las constantes se declaran así en la clase o interface:

interface Persona {

  public static final String SIN_DESCRIPCION = "NO DESCRIPCION";


Saludos,
J