Búsqueda eficiente en una lista

Question

Tengo una situación en la que estoy rellenando un ArrayList con "TransactionEvent" s. TransactionEvent tiene una propiedad "ID de transacción". En la gran mayoría de los casos, cada evento nuevo tiene una ID de transacción mayor que la ID del evento anterior. Sin embargo, esto no está garantizado; es decir, los datos son casi ordenados.

Mi pregunta es: ¿cómo puedo realizar búsquedas rápidas basadas en la identificación de la transacción? Mi idea actual es llamar al Collections.binarySearch(...) y, si esto falla, realizar una búsqueda lineal. Sin embargo, noté que el Javadoc establece que el resultado de binarySearch no está definido, es que los datos están desordenados, así que es posible que tenga que implementar mi propia implementación.

adicional:

• He intentado usar un mapa de índice -> ID de transacción, pero este enfoque es erróneo porque cada vez que se actualiza un elemento de la lista/borrado tengo que reconstruir todo el mapa; es decir, cualquier ganancia se borrará con esto.
• Este no es un caso de optimización prematura: el List es la base de un TableModel que actualmente funciona muy lentamente cuando contiene una gran cantidad de filas (100,000).

Cualquier ayuda apreciada.

Answer 1

Puede mantener ordenada la lista ArrayList buscando el punto de inserción a medida que agrega cada TransactionEvent. Collections.binarySearch devuelve

índice de la clave de búsqueda, si está en la lista; de lo contrario, (- (punto de inserción) - 1).El punto de inserción se define como el punto en el que la clave se insertaría en la lista: el índice del primer elemento mayor que la clave, o list.size(), si todos los elementos en la lista son menores que la clave especificada. Tenga en cuenta que esto garantiza que el valor de retorno será> = 0 si y solo si se encuentra la clave.

Una vez que busca el punto de inserción se puede utilizar el método de ArrayList add(int index, Object element) en lugar de limitarse a añadir al final de la lista como lo haría normalmente. Esto reducirá la velocidad de cada inserción por un pequeño factor, pero le permitirá usar la búsqueda binaria para una búsqueda rápida.

Answer 2

Por lo que ha dicho, parece que las búsquedas rápidas son lo más importante aquí.

Así que tal vez debería utilizar un HashMap en lugar de un ArrayList. En HashMap, almacene sus TransactionEvents usando TransactionID como la clave. Las búsquedas en un HashMap son O (1).

Tenga en cuenta que agregar al HashMap puede ser bastante lento si excede su capacidad inicial, ya que tiene que volver a realizar hash. Si puede, intente inicializarlo con una mejor estimación (erróneamente en el lado alto) en cuanto al número de elementos que contendrá.

Con 100k filas, puede que tenga que aumentar su tamaño de almacenamiento Java para evitar OutOfMemoryErrors.

java -Xms<initial heap size> -Xmx<maximum heap size> 

Los valores predeterminados son:

java -Xms32m -Xmx128m 

EDIT:

Si el pedido es realmente importante que usted podría utilizar un SortedMap.

Answer 3

Usando un LinkedHashMap, que combina una lista de doble enlace que tiene acceso hash, usted debe poder interactuar con el modelo de tabla tal como está con un ArrayList pero también acceder a las entradas mediante una búsqueda de hash en TransactionID.

Incluso puede reemplazar (por ejemplo, actualizar) en función de una clave sin afectar el orden de iteración.

Answer 4

Puede mantener su lista ordenada. Si lo inserta, clasifíquelo mientras agrega elementos, y los elementos que se agregarán estarán casi ordenados, entonces las inserciones seguirán ejecutándose efectivamente a tiempo constante. Esto le permitiría realizar búsquedas binarias en tiempo logarítmico.

Answer 5

Utilizaría una búsqueda binaria para obtener una ubicación aproximada de la identificación y luego buscar hacia fuera linealmente. La desventaja de esto es que si la identificación que estás buscando no está en la lista, entonces tomará O (n + log n).

Las búsquedas binarias son muy fáciles de implementar y recomiendo leer la wikipedia article.

Answer 6

Tuve el mismo problema. La solución que se me ocurrió fue la colección personalizada basada en ArrayList que también incluye el Mapa de todos los elementos. Esto no es difícil de hacer. Si desea que publique el código fuente, hágamelo saber

Answer 7

ArrayList es para problemas de tamaño de juguete. 100.000 filas se están saliendo un poco del espacio de los juguetes. Eso significa que debe ser más preciso sobre los patrones de acceso que necesita para respaldar. Una ArrayList ordenada podría ser suficiente, y si la velocidad de procesamiento aumenta más rápido que el tamaño de su problema, es posible que no desee molestarse, pero un BTree será más rápido con 100K elementos.

ArrayList tiene los siguientes problemas con tamaños problema mayor:

• añadir al final es lento cuando la colección tiene que crecer (copiar todos los elementos)
• inserto en una posición aleatoria es lenta ya que en promedio la mitad de la colección tiene que ser movido una posición

una colección de dos niveles con tamaño de página fijo (por ejemplo BTree) puede ayudar porque un cultivo significará la adición de un sobre sqrt (tamaño) página (idealmente) y un inserto de azar dividirá al máximo una página en dos.

Con dos criterios de ordenación necesarios, puede simplemente usar dos (clasificados) Btrees

[editar] La respuesta a la pregunta anterior es la clave del problema. Para ArrayList de 1000 elementos, la inserción cuesta 7 microsegundos, para 1000000 elementos, 7 milisegundos. El BTree se mantiene en el rango de microsegundos (pero puede ser el doble de lento para el tamaño de página de 1000 elementos).

Acceso indexado que puede crear manteniendo un índice del número de elementos en cada página. Si establece un indicador sucio en cada página, puede usar un hilo de fondo para actualizar el índice de inicio de cada página, o puede agregar operaciones masivas con la creación de índice diferido.

El índice puede ser no válido, pero es simplemente sqrt (tamaño) grande. Para elementos de 100K, solo está incrementando 150 índices en promedio.Eso lleva microsegundos, no milisegundos

Answer 8

Mi voto es que usted inserte en la lista en orden. Entonces puedes hacer una búsqueda binaria. Unas pocas notas:

1. Esto será más rápido que las inserciones normales debido a la inserción en un ArrayList cerca del final es más rápida que la inserción cerca del principio (menos elementos tienen que ser movido) y la mayoría de sus inserciones estarán en o cerca de el final (porque están casi ordenados).
2. Normalmente, encontraría el punto de inserción para insertar en una ArrayList utilizando un algoritmo de búsqueda binario. En este caso, es más rápido buscar linealmente, comenzando desde el final, ya que la mayoría de las inserciones se producirán en o cerca del final.

Answer 9

¿Por qué no utilizar una colección ordenada como su modelo de tabla en lugar de una lista? TreeMap parece lógico ya que todas las entradas están ordenadas. Si también necesita acceso rápido por fila o cualquier otra columna, simplemente puede agregar un mapa secundario. Básicamente estás haciendo lo que hacen los índices de base de datos.

Pensé por alguna razón que podría usar el map.headSet (clave) y encontrar la entrada k - esto no funcionará. Debe poder obtener desde la fila de la tabla -> EventID (o cerca de ella).

si se utiliza un modelo como este

Map<EventID, Event> model = new TreeSet<EventID, Event>(); 

Conceptualmente su getValueAt() tiene el siguiente aspecto:

getValueAt(int row, column) { 
eventID = getSortPosition(row); 
Event e = model.headSet(eventID).next(); 
return getColumn(e, column); 
} 

La clave es ser capaz de mantener de manera eficiente un mapa de índice de tipo -> clave (un mapa inverso). Esto no es trival, ya que insertar un nuevo evento en la parte superior afecta el orden absoluto de todos los que están debajo. Parece que debería haber una respuesta CS aquí, pero se me escapa.

Aquí está la implementación más básica: - en cada inserción, actualiza su mapa, luego materializa su mapa ordenado.

ArrayList<Event> orderedEvents = new ArrayList<Event>(); 
public void insert(Event event) { 
model.put(event.getID(), event); 

// update the 
model.headSet().addAll(orderedEvents); 
} 

Su getValueAt() sería bastante simple.

getValueAt(int row, column) {w); 
Event e = orderedEvents.get(row); 
return getColumn(e, column); 
} 

• esto hace inserciones O (n) en lugar de O (n log n) (todavía no es muy bueno)

Creo que debería reconsiderar su diseño de interfaz de usuario Si tiene los usuarios navegan en una tabla de 100K filas, agregar un filtro de búsqueda resolverá su problema de rendimiento:

• Ningún usuario LEERÁ NUNCA 100k filas
• Si es significativo para sus usuarios buscar por eventID entonces esto funciona muy bien, cuando los usuarios seleccionan el eventID, lo hace: sortedMap.headSet (searchFilterID) // tome los primeros 200 póngalos en su tabla
• Si es significativo para los usuarios buscar por tiempo, luego hacer un mapa y hacer lo mismo.

Answer 10

Mi primera respuesta no fue exactamente lo que estaba buscando. Ahora que entiendo el problema mejor, pruébalo. Solo implementé las partes clave.Esto requerirá un poco más de memoria, pero como estoy seguro de que ArrayList almacena las referencias, no los objetos en sí, la diferencia de memoria no debe ser demasiado grande en comparación con el almacenamiento de objetos real.

class TransactionEventStore 
{ 
    private ArrayList<TransactionEvent> byOrder, byId; 

    private void insertByOrder(TransactionEvent e) { this.byOrder.add(e); } 

    private void insertById(TransactionEvent e) 
    { 
     for(int i = this.byId.length() - 1; i > 0; i--) 
      if(e.getId() > this.byId.get(i).getId()) 
      { 
       this.byId.add(i,e); 
       break; 
      } 
    } 

    public void insert(TransactionEvent e) 
    { 
     this.insertByOrder(e); 
     this.insertById(e); 
    } 
} 

Ahora cuando se necesita para las operaciones de búsqueda por orden de inserción, mira this.byOrder y cuando es necesario para buscar por id, mira this.byId.

Answer 11

He limpiado un poco las cosas de mi publicación anterior. @Lizzard, a su solución le conviene más la propiedad de que las nuevas entradas sean usualmente al final. La solución a continuación debería funcionar mejor si tiene llegadas al azar a costa de más memoria para los mapas. También le permite diferir su inserción de matriz (potencialmente O (n) el peor caso) hasta que realmente necesite dibujar la celda para una fila debajo del punto de inserción más temprano.

// sorted events (using natural ordering on eventID) 
SortedSet<Event> model = new TreeSet<Event>(); 
ArrayList<Event> sortedList = new ArrayList<Event>(); 
Event lowestAddition, additionPrevEntry; // low water mark for insertions 

public void insert(Event x) { 
if (x < lowestAddition) { 
    Set<Event> headSet = model.headSet(x); // find the insertion point 
    additionPrevEntry = headSet.isEmpty()?model.last():headSet.first(); 
    lowestAddition = x; 
} 

model.add(x); // add 
} 

public void materialize() { 
SortedSet<Event> tailSet = model.tailSet(additionPrevEntry); 

Event firstValue = tailSet.first(); // this element does not change its order 
Integer order = firstValue.getOrder(); // keep order on Event 
for (Event x : tailSet) { 
    x.setOrder(order); 
    sortedList.set(order, x); 
    order++; 
} 

lowestAddition = null; additionPrevEntry = null; 
} 

Esto es lo que el código de oscilación se parece, que suponga que está utilizando oscilación, ya que desea un modelo de mesa:

// now your model code uses the array 
public Object getValueAt(int row, int col) { 
return getColumn(sortedList.elementAt(row), col); 
} 

// you can gain significant performance by deferring 
// materialization until you acutally need it 
public class DeferredJTable extends JTable { 
public void paintComponent(Graphics G, ...) { 
    // if you knew what rows in the table were being drawn 
    // ahead of time, you could further defer 
    materialize(); 

    super.paintComponent(); 
} 
}