Un algoritmo de búsqueda más rápido en una jtable

Question

Estoy tratando de implementar mi propio jtable RowFilter, ya que estoy usando Java 1.4 (RowFilter no parece existir en esta versión). Sin embargo, todavía creo que el algoritmo que estoy usando puede ser reemplazado por uno mucho más rápido. He probado mi algoritmo en una mesa ficticia que contiene 30,000 registros y 8 columnas, y obtengo el resultado en menos de un segundo. Pero a veces, existe este pequeño retraso que ocurre mientras se escribe en los criterios de búsqueda (que es básicamente un JTextfield con un Listenener de documentos). Aquí está el algoritmo que estoy usando:

    public void searchList()
    {  

        for(int i=0;i<list.size();i++)
        {
            Employee e=(Employee)list.get(i);

            Pattern pattern=Pattern.compile(search.getText(),Pattern.CASE_INSENSITIVE);
            Matcher matcher=pattern.matcher(e.getFname());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getLname());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getHeight());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getOccupation());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getSize());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getSkills());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getSsn());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getStrength());
            if(matcher.find())
            {
                result.add(e);

            }
        }
        model.fireTableDataChanged();
        table.updateUI();
    }
    }

La principal datestructura que estoy usando para vincular los datos a mi Tablemodel es una lista de matrices que contiene objetos de una clase llamada "Empleado". Otra ArrayList llamada Result, contiene todos los objetos de "empleado" que coincidían con los criterios de búsqueda. Tenga en cuenta que el filtrado está ocurriendo en las 8 columnas. La única optimización que creo que hice es agregar el objeto "Empleado" en la primera coincidencia de columna, en lugar de tener que pasar por el resto de las columnas.

¿Alguna sugerencia sobre este asunto? Muchas gracias por la ayuda =)

Answer 1

Como parece estar buscando exactamente el mismo valor en todos los campos, solo los concatenaría y haría la coincidencia una vez.

Además, no creo que haya una buena razón por la que compilaría el patrón en cada iteración.

Answer 2

Solo para actualizarlos en mi pregunta, finalmente he hecho lo siguiente: 1- Concatené todos los campos junto con un separador entre ellos (el "!") 2- Descargué la biblioteca de búsqueda de este enlace Johannburkard.de/software/stringsearch 3- Convertió la cadena concatenada y los criterios de búsqueda patatten a minúsculas. 4- Usó el algoritmo Boyer Moore, Raita haciendo lo siguiente: BoyerMooreHorspoolRaita searchAl=new BoyerMooreHorspoolRaita();

Entonces hice esto: int j=searchAl.searchString(match, search.getText()); if(j!=-1) result.add(e);

Intenté comparar el primer método que utilicé con este, en una tabla que contenía 100000 registros, y los resultados fueron los siguientes:

La coincidencia de patrones:PRIMER INTENTO:1 caracteres Patrón largo: la operación tardó 3.328 segundos en completar 2 caracteres Patrón largo de largo: La operación tardó 14.14 segundos en completar 3 caracteres Patrón largo de largo: La operación tardó 11.328 segundos en completar 4 caracteres Patrón largo: Operation tardó 8.437 segundos en completar 5 caracteres Long Patrón: Operación: Operación: Operación: Operación: Operación Tomó 8.344 segundos para completar el patrón de 6 caracteres de largo: la operación tardó 8.078 segundos en completarse

Segunda carrera:1 caracteres Patrón largo: la operación tardó 3.281 segundos en completar 2 caracteres Patrón largo del patrón: la operación tardó 14.14 segundos en completar 3 caracteres Patrón largo: Operation tardó 11.344 segundos en completar 4 caracteres Patrón largo: Operation tardó 8.375 segundos en completar 5 caracteres Long Patrón: Operación: Operación: Operación: Operación: Operación Tomó 8.469 segundos para completar el patrón de 6 caracteres de largo: la operación tardó 8.266 segundos en completarse

Boyer Moore Raita:Primera ejecución: 1 caracteres Patrón largo: La operación tardó 11.688 segundos en completar 2 caracteres Patrón largo: Operation tardó 10.594 segundos en completar 3 caracteres Patrón largo: Operation tardó 7.563 segundos en completar 4 caracteres Patrón largo: Operation tardó 4.328 segundos en completar 5 caracteres largos largos Patrón: la operación tardó 4.5 segundos en completar el patrón de 6 caracteres de largo: la operación tardó 4.969 segundos en completarse

Segunda carrera:1 caracteres Patrón largo: la operación tardó 8.172 segundos en completar 2 caracteres Patrón largo de largo: La operación tardó 8.312 segundos en completar 3 caracteres Patrón largo: Operation tardó 5.484 segundos en completar 4 caracteres Patrón largo: Operation tardó 3.922 segundos en completar 5 caracteres Patrón largo: Operación: Operación: Operación: Operación: Operación: Operación Tomó 3.922 segundos para completar el patrón de 6 caracteres de largo: la operación tardó 4.047 segundos en completarse

Observe que el filtrado de patrones (el primer método) es más rápido cuando se trata de una sola coincidencia de personajes. Pero el Boyer Moore Horspool Raita brilla a medida que aumenta la longitud del patrón.

Espero que esto ayude a alguien de alguna manera. Salud.