Ordenar una gran colección mientras se muestra el progreso

Question

¿Cuál es la mejor manera de ordenar una colección al actualizar una barra de progreso? Actualmente tengo un código como éste:

for (int i = 0; i < items.size(); i++) 
{ 
    progressBar.setValue(i); 

    // Uses Collections.binarySearch: 
    CollectionUtils.insertInOrder(sortedItems, item.get(i)); 
} 

Esta muestra progreso, pero la barra de progreso se ralentiza a medida que el número de artículos en sortedItems se hace más grande. ¿Alguien tiene un mejor enfoque? Idealmente, me gustaría utilizar una interfaz similar a Collections.sort() para que pruebe diferentes algoritmos de clasificación.

Cualquier ayuda sería grande!

---

como un poco de fondo, este código está tirando hacia atrás un montón de documentos (1-10 millones) de Lucene y la ejecución de un comparador de encargo sobre ellos. Ordenarlos escribiendo datos en el disco será demasiado lento para ser práctico. La mayor parte del costo es leer el artículo en el disco y luego ejecutar el comparador sobre los artículos. Mi PC tiene mucha memoria, así que no hay problemas relacionados con el intercambio en disco, etc.

Al final fui con la solución de Stephen porque era muy limpia y me permitió agregar fácilmente un algoritmo de clasificación de subprocesos múltiples.

Answer 1

Quiere tener cuidado aquí. Has elegido usar un algoritmo que construye incrementalmente una estructura de datos ordenados para que (lo tomo) puedas mostrar una barra de progreso. Sin embargo, al hacer esto, usted puede haber elegido un método de clasificación que es significativamente más lento que el tipo óptimo. (Ambos tipos serán O(NlogN) pero hay más de rendimiento que el comportamiento de orden O ...)

Si le preocupa que esto podría ser un problema, comparar el tiempo para ordenar una colección típica usando TreeMap y Collections.sort. El último funciona copiando la colección de entrada en una matriz, ordenando la matriz y luego volviéndola a copiar. (Funciona mejor si la colección de entrada es ArrayList. Si no necesita el resultado como una colección mutable, puede evitar la copia final utilizando Collection.toArray, Arrays.sort y Arrays.asList.)

Una idea alternativa sería usar un objeto Comparator que realice un seguimiento de la cantidad de veces que ha sido llamado y lo use para seguir el progreso del ordenamiento. Puede utilizar el hecho de que el comparador se suele llamar aproximadamente N*log(N) veces, aunque es posible que deba calibrarlo con el algoritmo real utilizado .

Dicho sea de paso, contar las llamadas al comparador le dará una mejor indicación del progreso que obtiene contando las inserciones. No logrará que la velocidad del progreso disminuya a medida que se acerque a completar el orden.

(Tendrás diferentes hilos leyendo y escribiendo el contador, por lo que debes considerar la sincronización. Declarar el contador como volatile funcionaría, a costa del tráfico de memoria adicional. También podrías ignorar el problema si eres feliz por la barra de progreso a veces muestran los valores rancios ... dependiendo de la plataforma, etc.)

---

^{1 - Hay un problema con esto. Hay algunos algoritmos donde el número de comparaciones puede variar drásticamente dependiendo del orden inicial de los datos que se ordenan. Para dicho algoritmo, no hay forma de calibrar el contador que funcionará en casos "no promedio".}

Answer 2

Si solo está comparando tiempos de ordenación, imprima la hora antes y después de la ordenación.

Predecir cuánto tardará un género en la naturaleza es difícil. Para algunos tipos, depende del orden de la entrada. Usaría i/(double) items.size() para generar una proporción del trabajo realizado y llamarlo un buen día. Puede optar por actualizar la barra cada items.size()/100 iteraciones. No hay razón para cerrar la barra de progreso con actualizaciones inútiles.

Answer 3

El tema aquí es el mecanismo físico de la clasificación - como sortedItems se hace más grande, insertInOrder será, por definición, tomar más tiempo, ya que es más probable un O(n lg n) + O(n) operación (mediante la búsqueda binaria para encontrar el siguiente elemento más pequeño y luego insertar el elemento) Es inevitable que a medida que su colección crezca, la inserción del siguiente elemento en el lugar adecuado demorará más.

La única forma de aproximar una barra de progreso cuyo tiempo aumenta linealmente sería utilizar una aproximación similar a la inversa de la función lg, ya que ordenar los primeros 1000 elementos podría tomarse un tiempo similar a ordenar los 10 últimos (es decir por supuesto una generalización).

Answer 4

¿Puede utilizar una barra de progreso indeterminate? Esto aún proporciona retroalimentación al usuario de que algo está sucediendo. Su código se vería así:

progessbar.setIndeterminate(true); 
ArrayList sorted = new ArrayList(items); 
Colletions.sort(sorted); 

progessBar.setString("Hey you're done!"); 

Creo que se va a conseguir mucho un mejor rendimiento de utilizar el construido en especie, en lugar de la inserción binaria tipo que está haciendo.

Answer 5

que puede haber perdido algo, porque nadie más lo ha mencionado, pero suena como los tipos de tiempo de ejecución de su objeto de origen List no es un implementador de RandomAccess y por lo tanto su invocación Collections.binarySearch se ejecuta en tiempo O (n). Eso desaceleraría un poco las cosas, muy notablemente, cuando dupliques el número de elementos para ordenar.

Y además, si está utilizando, por ejemplo, un LinkedList para sortedItems, entonces la inserción también es O (n).

Si ese es el caso, tiene mucho sentido que cuando pase de 1 millón a 2 millones de elementos, su tiempo esperado también se duplique aproximadamente.

Para diagnosticar cuál de los 2 List objetos es problemático

1. Si la barra de progreso es lento desde el principio, es items; intente utilizar un contenedor diferente, algo tree-ish o hash-y
2. Si la barra de progreso se vuelve cada vez más lenta a medida que se acerca al 100%, es sortedItems; El mismo consejo que el anterior

Tenga en cuenta que pueden ser ambos List s los que están causando la desaceleración. Además, esto no tiene nada que ver con una barra de progreso. El problema que describió es algorítmico con respecto a la clasificación, no la actualización de una barra de progreso.

Answer 6

Por qué no implementar su propio tipo de combinación (que es lo que está haciendo Collections.sort) y actualizar la barra de progreso en los puntos clave del algoritmo (por ejemplo, después de cada fusión de más del 5% de la matriz)?

Answer 7

Un enfoque simple en la barra de progreso es esto.

Puede corregir el número de llamadas para actualizar el progreso independientemente del tamaño del elemento utilizando mod. Por ejemplo,

public void run(int total) { 
    int updateInterval = total/10; 
    System.out.println("interval = " + updateInterval); 
    for(int i = 0; i < total; i++) { 
     if(i % updateInterval == 0) { 
      printProgress((float)i/total * 100f); 
     } 
     // do task here 
    } 
} 

private void printProgress(float value) { 
    System.out.println(value + "%"); 
} 

Esto actualizará la barra de progreso 10 veces (o 9? Comprobar las condiciones de contorno) si el tamaño es de 10 o 10 millones.

Esto es solo un ejemplo, ajuste los valores en consecuencia.