Filtrar eficientemente un ArrayList en Java/Android

Question

Estoy desarrollando una aplicación de Android (Android 1.6), pero esta es probablemente una pregunta más general de Java.

tengo una ArrayList de aproximadamente 10.000 objetos

los objetos contienen 3 cuerdas (firstName, MiddleName, lastName).

Al usuario se le presenta un "cuadro de búsqueda" en Android donde puede buscar un "objeto" en particular escribiendo una parte del nombre.

Tengo una clase (a la que llamo Filterer) que busca en la lista de 10.000 objetos coincidentes y luego los devuelve como una "sublista".

La búsqueda es un poco lenta (especialmente en un dispositivo con Android) y estoy seguro de que no estoy haciendo la búsqueda/filtrado de la manera más eficiente posible.

¿Alguien tiene alguna sugerencia sobre cómo acelerar mi búsqueda? Mi código está abajo. Una posibilidad de buscar contra una "lista maestra" secundaria que ya tiene toda la información en minúscula y concatenada ... pero puede haber otras formas de mejorar esta búsqueda que también podrían ser útiles.

TIA !!

public void filterNames() { 
    this.filteredList.clear(); 
    String sv = this.searchString.toString.trim().toLowerCase(); // search value 
    for (int i = 0; i < this.masterList.size(); i++) { 
    MyObject d = this.masterList.get(i); 
    String fn = d.getFirstName().toString().toLowerCase(); 
    String mn = d.getMiddleName().toString().toLowerCase(); 
    String ln = d.getLastName().toString().toLowerCase(); 

    if (fn.indexOf(sv) >= 0 || 
     md.indexOf(sv) >= 0 || 
     ln.indexOf(sv) >= 0) { 
     this.currentList.add(d); 
    } 
    } 
} 

Answer 1

sí, es sin duda doloroso minúsculas varios objetos para cada iteración del bucle (más una posiblemente redundantes toString?), Y también una mala práctica para llamar list.size() para cada iteración — ese valor debe almacenar en caché antes del bucle empieza.

De todos modos, si está trabajando con esta cantidad de datos, ¿hay algún motivo por el que no esté utilizando una base de datos SQLite para almacenar y mostrar/filtrar su lista usando CursorAdapter?

Esa sería la forma recomendada de implementar algo de este tamaño.

Answer 2

¿Tal vez pueda cambiar algo de espacio por algo de velocidad? ¿Crea alguna forma de índice para sus datos?

Por ejemplo:

1. crear una lista para cada personaje (a-z) con todos los s "MyObject", donde una parte del nombre contiene el carácter (ser consciente de caracteres especiales!). Para cada entrada cuente el número de "MyObject" s
2. Si un usuario escribe en una consulta, busque los caracteres individuales y busque solo en la lista con la menor cantidad de entradas.

Por supuesto, la adición de un nombre requerirá que lo agregue al índice.

Answer 3

Después de investigar un poco más he encontrado que Suffix Arrays podría obtener las respuestas en ayunas. También eche un vistazo a la entrada de Wikipedia para Suffix Trees para una explicación más detallada.
Ofrece que estoy de acuerdo con el answer above que probablemente podría utilizar una base de datos SQL para tales consultas. Hacer una consulta SQL en contra de los datos es probablemente una de las formas más rápidas de obtener lo que desea sin matrices de sufijos.
Una cosa para acelerar un poco las cosas sin hacer SQL sería poner firstName, middleName, lastName en una cadena en minúscula, y poner eso en un nuevo mapa que hace referencia al índice Array. De esta forma, puede reducir la búsqueda a solo 10.000 cadenas del hashmap sin tener que hacer una minúscula cada vez. Puede ser un poco más rápido, pero por supuesto requiere más memoria. Tal vez intente hacer algo con expresiones regulares para acelerar el emparejamiento.
Otra opción sería crear realmente un índice de búsqueda con algo como Lucene, aunque creo que sería demasiado exagerado en un dispositivo Android, pero podría funcionar en Java simple y la búsqueda en el infijo en Lucene tampoco es un gran rendimiento.

Answer 4

¿Cómo está recuperando inicialmente la lista de más de 10.000? Si solo está usando un instance of SQLite, realmente, fuertemente le recomiendo hacerlo en SQL.

Answer 5

puede ser una respuesta demasiado tarde, pero es ayuda para otros en el mismo problema.

Java 8 (2014) resuelve este problema utilizando los arroyos y lambdas en una línea de código:

Usando Stream Api puede filtrar datos sin bucle y más característica de están disponibles.

List<MyObject> mFilteredMyObjectList = mMyObjectList.stream() 
    .filter(d -> d.getFirstName().toString().toLowerCase().indexOf(sv) >= 0 
    || d.getMiddleName().toString().toLowerCase().indexOf(sv) >= 0 
    || d.getLastName().toString().toLowerCase().indexOf(sv) >= 0).collect(Collectors.toList()); 

Para más información véase el enlace a continuación,

Link1 Link2