La mejor estructura de datos para la lista de objetos que se consulta con frecuencia

Question

Tengo una lista de objetos, por ejemplo, Lista. La clase Entity tiene un método igual, en pocos atributos (regla comercial) para diferenciar un objeto Entity del otro.

La tarea que suelen llevar a cabo en esta lista es eliminar todas las copias o menos así:

List<Entity> noDuplicates = new ArrayList<Entity>(); 
for(Entity entity: lstEntities) 
{ 
    int indexOf = noDuplicates.indexOf(entity); 
    if(indexOf >= 0) 
    { 
      noDuplicates.get(indexOf).merge(entity); 
    } 
    else 
    { 
      noDuplicates.add(entity); 
    } 
} 

Ahora, el problema que he estado observando es que esta parte del código, se está desacelerando desciende considerablemente tan pronto como la lista tenga objetos de más de 10000. Entiendo que el arraylista está haciendo una búsqueda de ao (N).

¿Existe una alternativa más rápida, el uso de HashMap no es una opción, porque la singularidad de la entidad se basa en 4 de sus atributos en conjunto, sería tedioso introducir la clave en el mapa? ordenará set help en consultas más rápidas?

Gracias

Answer 1

Ahora, el problema que he estado observando es que esta parte del código, se ralentiza considerablemente tan pronto como la lista tiene objetos de más de 10000. Entiendo que el arraylist está haciendo una búsqueda de o (N).

El algoritmo informados es en realidad peor que O (N)

• iteración a través de la lista de entrada lstEntities - O (N)
• dentro de este bucle, que está llamando ArrayList.indexOf(T) que tiene para escanear la lista - O (N) otra vez

Su algoritmo es realmente O (N^2) ya que potencialmente puede escanear la lista dos veces dentro de un bucle.

Suena como si lo que se quiere hacer es en realidad dos operaciones:

1. Desde la entrada List, eliminar los duplicados
2. Cuando encuentre duplicados, "fusionar" las entidades.

Puede hacerlo escaneando la lista una sola vez, en lugar de hacerlo en bucles anidados. Recomendaría dividir su Entity para mover los campos que "identifican" una Entidad a otro tipo, como ID, o al menos agregar un método getID() que puede devolver estos campos agrupados en un solo tipo. De esta forma, puede construir fácilmente un Mapa entre los dos tipos para poder fusionar entidades con identidades "duplicadas". Esto podría ser algo como esto:

Map<ID, Entity> map = new HashMap<ID, Entity>(inputList.size()); 
for (Entity e : inputList) { 
    Entity existing = map.get(e.getID()); 
    if (existing == null) { 
     //not in map, add it 
     map.put(e.getID(), e); 
    } 
    else { 
     existing.merge(e); 
    } 
} 

Iterar a través de la lista es O (n), mientras que HashMap.get(K) es una operación de tiempo constante.

Answer 2

Una idea es utilizar un Set en lugar de un List, no hay duplicados en un Set. Para eliminar los duplicados de una lista, usted podría agregar el List a un nuevo Set

List<Entity> list = //your list. 
Set<Entity> set = new HashSet<Entitiy>(); 
set.addAll(list); 

Pero, de nuevo, tal vez hay alguna razón para utilizar un List en el primer lugar? De lo contrario, podría usar un Set y no tener que preocuparse por ningún duplicado.

EDITAR

No hay ninguna referencia índice de los elementos en un Set (en comparación con un List, donde se puede hacer get(int index)). Los elementos en un Set están flotando sin un punto de referencia específico.

Si necesita encontrar una específica, necesita recorrer todas ellas. Si eso no está bien y/o no puede estar sin la referencia indexada, que permite get(int index) y remove(int index), supongo que Set no es una opción para usted.

Answer 3

En lugar de una estructura de lista, puede usar un conjunto (más apropiado si le preocupa la singularidad de la entidad), como ha sugerido Lars. Además, si el rendimiento es un problema, consideraría usar un TreeSet e implementar un Comparator para comparar instancias de Entity basadas en sus atributos. La estructura de árbol permitirá operaciones de inserción, eliminación y recuperación rápidas (complejidad logarítmica).

Answer 4

Todo depende de lo que esté haciendo la operación merge. ¿Cambia merge cualquiera de los atributos que se comparan al hacer equals? Si no, entonces usted se sorprenderá de lo rápido que será si hace esto:

En primer lugar, definir un hashCode para su clase Entity que sea compatible con su definición de equals.Una forma común de hacer esto es:

public int hashCode() { 
    // assuming the four attributes that determine equality are called 
    // attrFoo, attrBar, attrBaz, and attrQux 
    int hash = 1; 
    hash += attrFoo == null ? 0 : attrFoo.hashCode(); 
    hash *= 37; 
    hash += attrBar == null ? 0 : attrBar.hashCode(); 
    hash *= 37; 
    hash += attrBaz == null ? 0 : attrBaz.hashCode(); 
    hash *= 37; 
    hash += attrQux == null ? 0 : attrQux.hashCode(); 

    return hash; 
} 

A continuación, utilice un HashMap de manera que se pueden encontrar estas cosas:

Map<Entity, Entity> map = new HashMap<Entity, Entity>(); 
for(Entity entity: lstEntities) { 
    if (map.containsKey(entity)) { 
    map.get(entity).merge(entity); 
    } else { 
    map.put(entity, entity); 
    } 
} 
return map.values(); // or keys(). Whichever. 

debo señalar que me siento un poco sucia escribir el código anterior, debido realmente no debería hacer que las claves Map no sean inmutables, pero esto funcionará y será mucho, mucho más rápido que lo que está haciendo ahora.

Answer 5

A menos que tenga un motivo para necesitar el pedido de una lista, probablemente sea mejor que tenga un conjunto, específicamente un HashSet.

Veo su preocupación sobre el uso de una colección hash porque "la singularidad de la entidad se basa en 4 de sus atributos en conjunto", pero eso se supera fácilmente. Solo tiene que definir un método hashcode() que sea compatible con su método equals() existente, y luego puede insertar sus entidades en un conjunto, y como efecto secundario mágico, nunca tendrá que eliminar duplicados nuevamente.

Answer 6

Dos pasos simples para un O (N * log (N)) algoritmo:

1. Ordenar la lista mediante un comparador sobre la base de los cuatro campos importantes
2. iterar sobre la lista de la comparación de cada elemento a la siguiente en la lista, si son iguales, combínalos y elimina uno.