¿Cómo recurrir rápidamente a una lista con solo un valor cambiado?

Question

Digamos que tengo una lista de objetos que están ordenados por un campo específico en ese objeto. Si uno de los objetos cambia esa propiedad, su posición en la lista ordenada debería actualizarse.

¿Qué algoritmo de ordenamiento o "trucos" podría utilizar para ordenar rápidamente esta lista, dado que se cae de orden de un solo elemento a la vez?

La estructura de datos es una matriz, y tengo acceso directo al índice del elemento cambiado.

Estoy usando Scala para esto, pero cualquier sugerencia general o consejos sería útil también.

Answer 1

Puede hacer una iteración de clasificación de burbuja: comience desde el principio de la lista e itere hasta encontrar el elemento fuera de servicio. Luego muévelo en la dirección apropiada hasta que caiga en su lugar. Esto le dará en el peor rendimiento 2N.

Answer 2

mover el elemento sin ordenar a la izquierda oa la derecha en la lista parece la solución óptima

Answer 3

Si la lista está ordenada, puede simplemente eliminar el elemento que está a punto de cambiar de la lista, y después de cambiarlo, podrías "insertarlo binariamente", ¿no? Eso tomaría un promedio de pasos de registro (n).

Si puede, cambie de una matriz a java.util.TreeMap: tanto la extracción como la inserción serán operaciones de registro (n): que será más rápido que su O (1) acceso + O (n) solución de inserción usando una matriz.

Answer 4

Quite el elemento y vuelva a agregarlo en la posición correcta. IF solo está haciendo un artículo, su tiempo de ejecución máximo es N.

Si está haciendo más de uno, debe esperar hasta que todo esté listo y luego recurrir. Pero tendrá que decirnos mucho más sobre su espacio problemático. Quick está limitado por la memoria y otros factores que deberá determinar para elegir el algoritmo correcto.

Answer 5

Dependiendo de si el nuevo valor es mayor o menor que el anterior, puede "burbuja" en su lugar.

El pseudo-código sería algo como esto:

if new value larger than old value 
    then if new value is larger than next value in collection 
     then swap the value with the next value 
     iterate until value is not larger than next value 
else if new value is smaller than previous value in collection 
    then swap the value with the previous value 
    iterate until value is not smaller than the previous value 

Por supuesto, una mejor manera sería utilizar una búsqueda binaria.

Primero, ubique el nuevo lugar en la colección donde debería estar el elemento. Luego, cambia los elementos a su lugar. Si el nuevo índice de punto es mayor que el índice de punto actual, desplaza los elementos hacia abajo en un elemento, de lo contrario, los desplazará hacia arriba. Cambias elementos desde el lugar que ocupabas anteriormente hasta el que deseas ocupar. Luego, almacena el valor en el lugar que encontraste.

Por ejemplo, supongamos que esta colección:

a b c d e f g h i j 
10 20 30 40 50 60 70 80 90 100 

entonces usted quiere cambiar el valor del elemento f de 60 a 95.

En primer lugar a determinar donde debería estar.Uso de la búsqueda binaria, encontramos que debería estar entre 90 y 100:

a b c d e f g h i j 
10 20 30 40 50 60 70 80 90 100 
           ^
            +- here 

Entonces usted cambia de elementos desde la posición actual hasta un elemento, como esto:

a b c d e f g h i j 
10 20 30 40 50 60 70 80 90 100 <-- from this 
10 20 30 40 50 70 80 90 ?? 100 <-- to this 

Y luego se almacena el valor en el ?? espacio, lo que le da esta formación

a b c d e g h i f j 
10 20 30 40 50 70 80 90 95 100 

Answer 6

Si la lista es muy grande y hay un gran número de operaciones de actualización se esperaba, un simple conjunto de acceso aleatorio o lista enlazada será demasiado lento. Si usa matrices/listas vinculadas, cada operación de actualización costará O (n). Con listas pequeñas y/o pequeñas cantidades de actualizaciones, esto es adecuado.

Para listas más grandes, puede lograr actualizaciones O (log (n)) usando una estructura de datos O (log (n)) ordenada (árboles AVL/RB, listas de salto, árboles de segmento, etc.). Una implementación simple puede implicar eliminar el elemento que se va a actualizar, cambiar el valor y luego reinsertarlo. Muchos idiomas populares tienen algún tipo de estructura de datos ordenados en su biblioteca (por ejemplo, TreeMap/TreeSet en Java, multiset/multimap en C++ 's STL), o puede encontrar fácilmente una implementación gratuita para su idioma.

Answer 7

Para una matriz, insertar un elemento en la posición correcta sería O (n), porque debe copiar los elementos de la matriz para dejar espacio para un elemento adicional. Puede encontrar el índice al que debe insertar haciendo binary search (O (log n)) o linear search (O (n)). Cualquiera que sea la elección que haga, el algoritmo como un todo será O (n).

La única manera de hacer esto muy rápidamente es utilizar una estructura de datos que se adapte mejor a esta situación: a binary search tree. La inserción sería O (log n) si el árbol permanece decentemente balanceado (Use un self-balancing binary search tree para asegurar esto o espere que sus datos no se inserten en un orden muy regular para aproximarse a O (log n).)

O (log n) es manera más rápido que O (n) incluso para listas moderadamente grandes, por lo que si tiene listas que pueden ser arbitrariamente grandes y realmente se preocupan por clasificar el rendimiento, use un árbol de búsqueda binario.