algorithm - sirve - listas en python

¿Cuál es el algoritmo estándar para sincronizar dos listas de objetos relacionados?

Question

Estoy bastante seguro de que esto debe estar en algún tipo de libro de texto (o más probablemente en todos ellos) pero parece que estoy usando las palabras clave equivocadas para buscarlo ... :(

Una tarea recurrente a la que me enfrento durante la programación es que estoy tratando con listas de objetos de diferentes fuentes que necesito mantener sincronizadas de alguna manera. Por lo general, hay una especie de "lista maestra", por ejemplo, devuelta por alguna API externa y luego una lista de objetos que creo yo, cada uno de los cuales corresponde a un objeto en la lista maestra (piense en "envoltorios" o "adaptadores"; generalmente contienen información ampliada sobre los objetos externos específicos de mi aplicación y / o simplifican el acceso a los objetos externos).

Características duras de todas las instancias del problema:

• la implementación de la lista maestra está oculta para mí; su interfaz es fija
• Los elementos en las dos listas no son compatibles con la asignación
• Tengo control total sobre la implementación de la lista de esclavos.
• No puedo controlar el orden de los elementos en la lista maestra (es decir, no se puede clasificar)
• La lista maestra no proporciona ninguna notificación sobre los elementos agregados o eliminados o la notificación no es confiable, es decir, la sincronización solo se puede realizar a pedido, no en vivo
• simplemente borrar y reconstruir la lista de esclavos desde cero siempre que sea necesario no es una opción:
  • La inicialización de los objetos de la envoltura debe considerarse cara
  • Otros objetos mantendrán referencias a los envoltorios.

Características adicionales en algunos casos del problema:

• Los elementos en la lista maestra solo pueden identificarse leyendo sus propiedades en lugar de acceder directamente a ellos por índice o dirección de memoria:
  • después de una actualización, la lista maestra puede devolver un conjunto completamente nuevo de instancias aunque aún representan la misma información
  • la única interfaz para acceder a los elementos en la lista maestra podría ser un enumerador secuencial
• la mayoría de las veces, el orden de los elementos en la lista maestra es estable, es decir, los nuevos elementos siempre se agregan al principio o al final, nunca en el medio; sin embargo, la eliminación generalmente puede ocurrir en cualquier posición

Entonces, ¿cómo típicamente abordaría esto? ¿Cuál es el nombre del algoritmo que debo buscar en Google?

En el pasado, lo he implementado de varias maneras (vea a continuación un ejemplo) pero siempre sentí que debería haber una manera más limpia y más eficiente, especialmente una que no requería dos iteraciones (una sobre cada lista).

Aquí hay un ejemplo de enfoque:

1. Iterar sobre la lista maestra
2. Busque cada elemento en la "lista de esclavos"
3. Añadir elementos que aún no existen
4. De alguna manera, realice un seguimiento de los elementos que ya existen en ambas listas (por ejemplo, etiquetándolos o manteniendo otra lista)
5. Cuando haya terminado, repita la lista de esclavos y elimine todos los objetos que no hayan sido etiquetados (vea 4.) y vuelva a borrar la etiqueta de todas las demás.

Actualización 1 Gracias por todas sus respuestas hasta ahora! Necesitaré un poco de tiempo para mirar los enlaces.
[...] (texto movido al cuerpo principal de la pregunta)

Actualización 2 Reestructuró el párrafo medio en una (con suerte) listas de viñetas más fáciles de analizar e incorporó detalles agregados más adelante en la primera actualización.

Answer 1

A menudo, la mejor solución para tales problemas es no resolverlos directamente.

SI realmente no puede usar un contenedor de búsqueda binario ordenado en su parte del código (como un conjunto o incluso un vector ordenado) entonces ...

¿Estás muy ligado a la memoria? Si no, solo crearía un diccionario (un std :: set, por ejemplo) que contenga el contenido de una de las listas y luego iteraré sobre el segundo que quiero sincronizar con el primero.

De esta manera, está haciendo n logn para crear el diccionario (o n X para un hash diccionario dependiendo de lo que será más eficiente) + m logn operaciones para revisar la segunda lista y sincronizarla (o simplemente M Y) - es difícil Bate si realmente tienes que usar listas en primer lugar. También es bueno que lo hagas solo una vez, si lo necesitas, y es mucho mejor que mantener las listas ordenadas todo el tiempo, lo que sería una tarea ^ 2 para ambos. .

Answer 2

Aquí hay una versión de Javascript del código python de Michael Heyek.

    var b= [1,3,8,12,16,19,22,24,26]; // new situation
    var a = [1,2,8,9,19,22,23,26]; // previous situation
    var result = sync_ordered_lists(a,b);
console.log(result);
    function sync_ordered_lists(a,b){
// by Michael Heyeck see http://www.mlsite.net/blog/?p=2250
// a is the subject list
// b is the target list
// x is the "current position" in the subject list
// y is the "current position" in the target list
// i is the list of inserts
// d is the list of deletes
        var x = 0; 
        var y = 0; 
        var i = []; 
        var d = []; 
        var acc = {}; // object containing inserts and deletes arrays
        while (x < a.length || y < b.length) {
            if (y >= b.length){
                d.push(x); 
                x++;
            } else if (x >= a.length){ 
                i.push([y, b[y]]); 
                y++;
            } else if (a[x] < b[y]){ 
                d.push(x); 
                x++;
            } else if (a[x] > b[y]){ 
                i.push([y, b[y]]); 
                y++;
            } else { 
                x++; y++;
            }
        }
        acc.inserts = i;
        acc.deletes = d;
        return acc;
    }

Answer 3

En el C ++ STL el algoritmo se llama set_union. Además, es probable que la implementación del algoritmo sea mucho más simple si realiza la unión en una tercera lista.

Answer 4

Esto se parece al problema de reconciliación establecido, es decir, el problema de la sincronización de datos no ordenados. Se hizo una pregunta sobre SO: Implementación del algoritmo de reconciliación de conjuntos .

La mayoría de las referencias en google se refieren a resúmenes de documentos técnicos.

Answer 5

Fuerza bruta y enfoque técnico puro:

Heredar de su clase de lista (lo siento, no sé cuál es su idioma). Reemplace los métodos de agregar / eliminar en su clase de lista secundaria. Usa tu clase en lugar de la base. Ahora puede hacer un seguimiento de los cambios con sus propios métodos y sincronizar las listas en línea.

Answer 6

Las 2 soluciones típicas son: 1. Copie la lista maestra a la lista de sincronización. 2. Haz una comparación O (N * N) entre todos los pares de elementos.

Ya ha excluido las opciones inteligentes: identidad compartida, clasificación y notificaciones de cambios.

Tenga en cuenta que no es relevante si las listas se pueden clasificar de manera significativa o incluso completa. Por ejemplo, al comparar dos listas de cadenas, sería ideal ordenar alfabéticamente. ¡Pero la comparación de la lista sería aún más eficiente si ordenara ambas listas por longitud de cadena! Aún tendrías que hacer una comparación completa por pares de cadenas de la misma longitud, pero eso probablemente será un número mucho menor de pares.

Answer 7

Parece que un compañero llamado Michael Heyeck tiene una buena solución , O (n) para este problema. Echa un vistazo a esa publicación del blog para obtener una explicación y un código.

Esencialmente, la solución rastrea las listas maestra y esclava en una sola pasada, rastreando índices en cada una. Luego se administran dos estructuras de datos: una lista de inserciones que se reproducirán en la lista de esclavos y una lista de eliminaciones.

Parece sencillo y también tiene el beneficio de una prueba de minimalismo, que Heyeck siguió en una publicación posterior . El fragmento de código en esta publicación es más compacto, también:

def sync_ordered_list(a, b):
x = 0; y = 0; i = []; d = []
while (x < len(a)) or (y < len(b)):
    if y >= len(b): d.append(x); x += 1
    elif x >= len(a): i.append((y, b[y])); y += 1
    elif a[x] < b[y]: d.append(x); x += 1
    elif a[x] > b[y]: i.append((y, b[y])); y += 1
    else: x += 1; y += 1
return (i,d)

Una vez más, crédito a Michael Heyeck.

Answer 8

Tuve ese problema en un proyecto en el pasado.

Ese proyecto tenía una fuente de datos maestros y varios clientes que actualizan los datos de forma independiente y, al final, todos tienen que tener el conjunto de datos más reciente y unificado que es la suma de ellos.

Lo que hice fue construir algo similar al protocolo SVN, en el que cada vez que quería actualizar la base de datos maestra (a la que se podía acceder a través de un servicio web) obtenía el número de revisión. Actualicé mi almacén de datos local a esa revisión y luego comprometí las entidades que no están cubiertas por ningún número de revisión a la base de datos.

Cada cliente tiene la capacidad de actualizar su almacén de datos local a la última revisión.