programacion - Java: Diferencia entre dos listas

manual programacion android español pdf

Question

La aplicación de cría de gatos de mi compañía rastrea un convoy de gatos. Periódicamente, debe comparar la currentOrder previousOrder con la currentOrder (cada una es una ArrayList<Cat> ) y notificar a los cuidadores de gatos cualquier cambio.

Cada gato es único y solo puede aparecer una vez en cada lista (o no aparece). La mayoría de las veces, las listas de los currentOrder previousOrder y de los currentOrder tienen los mismos contenidos, en el mismo orden, pero puede suceder cualquiera de los siguientes (de más frecuentes a menos frecuentes):

1. El orden de los gatos está revuelto por completo.
2. Los gatos se mueven individualmente hacia arriba o hacia abajo en la lista.
3. Nuevos gatos se unen, en un punto específico del convoy.
4. Los gatos salen del convoy

Esto me parece un problema de edición de distancia . Idealmente, estoy buscando un algoritmo que determine los pasos necesarios para hacer que la previousOrder coincida con currentOrder :

• MOVE Fluffy a la posición 12
• INSERTAR Snuggles en la posición 37
• ELIMINAR Mr. Chubbs
• etc.

El algoritmo también debe reconocer el escenario # 1, en cuyo caso el nuevo orden se comunica en su totalidad.

¿Cuál es el mejor enfoque para esto?

( Esta publicación y esa publicación plantean preguntas similares, pero ambas tratan con listas ordenadas . Las mías están ordenadas , pero sin clasificar ).

EDITAR

El algoritmo de Levenshtein es una gran sugerencia, pero me preocupa el requisito de tiempo / espacio para crear una matriz. Mi objetivo principal es determinar y comunicar los cambios lo más rápido posible. Algo que es más rápido que encontrar las adiciones y enviar mensajes a lo largo de las líneas de "Aquí están los nuevos gatos, y aquí está el orden actual".

Answer 1

Aquí hay un algoritmo que junté para fusionar dos listas, old y new . No es el más elegante o eficiente, pero parece funcionar bien para los datos para los que lo estoy usando.

new es la lista de datos más actualizada, y old es la lista obsoleta que debe transformarse en new . El algoritmo realiza sus operaciones en la lista anterior: elimina, mueve e inserta elementos en consecuencia.

for(item in old)
    if (new does not contain item)
        remove item from old

for(item in new)
    if (item exists in old)
        if (position(item, old) == position(item, new))
            continue // next loop iteration
        else
            move old item to position(item, new)
    else
        insert new item into old at position(item, new)

Todas las eliminaciones se realizan por adelantado para que las posiciones de los elementos sean más predecibles en el segundo ciclo.

La fuerza impulsora detrás de esto fue sincronizar una lista de datos del servidor con filas <table> en un DOM del navegador (usando javascript). Era necesario porque no queríamos volver a dibujar toda la tabla cada vez que cambiaban los datos; las diferencias entre las listas eran probablemente pequeñas y solo afectaban a una o dos filas. Puede que no sea el algoritmo que está buscando para sus datos. Si no, hágamelo saber y eliminaré esto.

Probablemente hay algunas optimizaciones que podrían hacerse para esto. Pero para mí y para los datos con los que estoy trabajando es lo suficientemente previsible y lo suficientemente previsible como para mí.

Answer 2

Hace poco tuve que hacer esto, excepto que los artículos podían existir varias veces. Esto complicó las cosas, pero pude hacerlo utilizando contadores de anticipación y otras locuras. Se parece mucho a la solución de Rob, ¡así que gracias a él por ayudarme a empezar!

En primer lugar, supongamos que queremos devolver la lista de operaciones que transformarán la primera lista en la segunda:

public interface Operation {
    /**
     * Apply the operation to the given list.
     */
    void apply(List<String> keys);
}

y tenemos algunos métodos de ayuda para construir operaciones. En realidad, no necesita una operación de "movimiento", e incluso podría tener un "intercambio" también (o en su lugar), pero esto es lo que hice con:

Operation delete(int index) { ... }
Operation insert(int index, String key) { ... }
Operation move(int from, int to) { ... }

Ahora definiremos una clase especial para mantener nuestros conteos anticipados:

class Counter {
    private Map<String, Integer> counts;

    Counter(List<String> keys) {
        counts = new HashMap<>();

        for (String key : keys) {
            if (counts.containsKey(key)) {
                counts.put(key, counts.get(key) + 1);
            } else {
                counts.put(key, 1);
            }
        }
    }

    public int get(String key) {
        if (!counts.containsKey(key)) {
            return 0;
        }

        return counts.get(key);
    }

    public void dec(String key) {
        counts.put(key, counts.get(key) - 1);
    }
}

Y un método auxiliar para obtener el índice de la siguiente clave en la lista:

int next(List<String> list, int start, String key) {
    for (int i = start; i < list.size(); i++) {
        if (list.get(i).equals(key)) {
            return i;
        }
    }

    throw new RuntimeException("next index not found for " + key);
}

Ahora estamos listos para hacer la transformación:

List<Operation> transform(List<String> from, List<String> to) {
    List<Operation> operations = new ArrayList<>();

    // make our own copy of the first, that we can mutate
    from = new ArrayList<>(from);

    // maintain lookahead counts
    Counter fromCounts = new Counter(from);
    Counter toCounts = new Counter(to);

    // do all our deletes first
    for (int i = 0; i < from.size(); i++) {
        String current = from.get(i);

        if (fromCounts.get(current) > toCounts.get(current)) {
            Operation op = delete(i);
            operations.add(op);
            op.apply(from);
            fromCounts.dec(current);
            i--;
        }
    }

    // then one more iteration for the inserts and moves
    for (int i = 0; i < to.size(); i++) {
        String current = to.get(i);

        if (from.size() > i && from.get(i).equals(current)) {
            fromCounts.dec(current);
            continue;
        }

        if (fromCounts.get(current) > 0) {
            Operation op = move(next(from, i + 1, current), i);
            operations.add(op);
            op.apply(from);

            fromCounts.dec(current);
        } else {
            Operation op = insert(i, current);
            operations.add(op);
            op.apply(from);
        }
    }

    return operations;
}

Es un poco difícil moverte de la cabeza, pero básicamente haces las eliminaciones para que conozcas cada tecla que estás insertando o moviendo. Luego recorres la lista nuevamente y, si hay suficiente, mueves una de la parte de la lista que aún no has visto, de lo contrario, insértala. Cuando llegas al final, todo se alinea.

Answer 3

Levenshtein distancia métrica.

http://www.levenshtein.net/

Answer 4

Sé que el interrogador buscaba una solución Java, pero me encontré con esta pregunta mientras buscaba un algoritmo para implementar en C #.

Aquí está mi solución, que genera una enumeración de valores simples de IListDifference: ItemAddedDifference, ItemRemovedDifference o ItemMovedDifference.

Utiliza una copia de trabajo de la lista de origen para establecer, elemento por elemento, qué modificaciones son necesarias para transformarla para que coincida con la lista de destino.

public class ListComparer<T>
    {
        public IEnumerable<IListDifference> Compare(IEnumerable<T> source, IEnumerable<T> target)
        {
            var copy = new List<T>(source);

            for (var i = 0; i < target.Count(); i++)
            {
                var currentItemsMatch = false;

                while (!currentItemsMatch)
                {
                    if (i < copy.Count && copy[i].Equals(target.ElementAt(i)))
                    {
                        currentItemsMatch = true;
                    }
                    else if (i == copy.Count())
                    {
                        // the target item''s index is at the end of the source list
                        copy.Add(target.ElementAt(i));
                        yield return new ItemAddedDifference { Index = i };
                    }
                    else if (!target.Skip(i).Contains(copy[i]))
                    {
                        // the source item cannot be found in the remainder of the target, therefore
                        // the item in the source has been removed 
                        copy.RemoveAt(i);
                        yield return new ItemRemovedDifference { Index = i };
                    }
                    else if (!copy.Skip(i).Contains(target.ElementAt(i)))
                    {
                        // the target item cannot be found in the remainder of the source, therefore
                        // the item in the source has been displaced by a new item
                        copy.Insert(i, target.ElementAt(i));
                        yield return new ItemAddedDifference { Index = i };
                    }
                    else
                    {
                        // the item in the source has been displaced by an existing item
                        var sourceIndex = i + copy.Skip(i).IndexOf(target.ElementAt(i));
                        copy.Insert(i, copy.ElementAt(sourceIndex));
                        copy.RemoveAt(sourceIndex + 1);
                        yield return new ItemMovedDifference { FromIndex = sourceIndex, ToIndex = i };
                    }
                }
            }

            // Remove anything remaining in the source list
            for (var i = target.Count(); i < copy.Count; i++)
            {
                copy.RemoveAt(i);
                yield return new ItemRemovedDifference { Index = i };
            }
        }
    }

Acabo de notar que hace uso de un método de extensión personalizado en IEnumerable - ''IndexOf'':

public static class EnumerableExtensions
{
    public static int IndexOf<T>(this IEnumerable<T> list, T item)
    {
        for (var i = 0; i < list.Count(); i++)
        {
            if (list.ElementAt(i).Equals(item))
            {
                return i;
            }
        }

        return -1;
    }
}

Answer 5

Una forma eficiente de resolver esto es mediante la programación dinámica. Wikipedia tiene pseudocódigo para un problema estrechamente relacionado: calcular la distancia de Levenshtein .

Realizar un seguimiento de las operaciones reales e incorporar la operación "aleatoria" no debería ser demasiado difícil.