Java: разница между двумя списками

Ответ 1

Вот алгоритм, который я собрал для объединения двух списков, old и new. Это не самый элегантный или эффективный, но, похоже, он работает хорошо для данных, которые я использую для него.

new - это самый обновленный список данных, а old - это устаревший список, который необходимо преобразовать в new. Алгоритм выполняет свои операции в списке old - соответственно, удаляя, перемещая и вставляя элементы.

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)

Все удаления выполняются заранее, чтобы позиции позиций были более предсказуемыми во втором цикле.

Движущей силой этого было синхронизацию списка данных с сервера с <table> строками в DOM браузера (с использованием javascript). Это было необходимо, потому что мы не хотели перерисовывать всю таблицу всякий раз, когда данные менялись; различия между списками, вероятно, были бы небольшими и затрагивали бы только одну или две строки. Возможно, это не тот алгоритм, который вы ищете для своих данных. Если нет, сообщите мне, и я удалю это.

Возможно, есть некоторые оптимизации, которые можно было бы сделать для этого. Но для меня и данных, которые я работаю, он достаточно прочный и предсказуемый.

Ответ 2

Левенштейн расстояние метрика.

http://www.levenshtein.net/

Ответ 3

Эффективным способом решения этой проблемы является использование динамического программирования. Википедия имеет псевдокод для тесно связанной проблемы: Вычисление расстояния Левенштейна.

Отслеживание фактических операций и включение операции "скремблирования" не должно быть слишком сложным.

Ответ 4

Я знаю, что вопросник искал решение Java, но я столкнулся с этим вопросом, ища алгоритм для реализации на С#.

Здесь мое решение, которое генерирует перечисление простых значений IListDifference: либо ItemAddedDifference, ItemRemovedDifference или ItemMovedDifference.

Он использует рабочую копию исходного списка для установки, по элементам, какие изменения необходимы для его преобразования в соответствии с целевым списком.

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 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 };
            }
        }
    }

Только что заметил, что используется специальный метод расширения в 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;
    }
}

Ответ 5

Я недавно должен был сделать это, за исключением того, что элементы могли существовать несколько раз. Это сложные вещи, но я смог сделать это, используя счетчики вперед и другое безумие. Он очень похож на решение Rob, поэтому благодаря ему за то, что он начал меня!

Прежде всего, предположим, что мы хотим вернуть список операций, которые преобразуют первый список во второй:

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

и у нас есть вспомогательные методы для построения операций. Фактически вам не нужна операция "move", и вы даже можете иметь "своп" (или вместо этого), но это то, с чем я пошел:

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

Теперь мы определим специальный класс, чтобы удерживать наши счетчики вперед:

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);
    }
}

И вспомогательный метод для получения индекса следующего ключа в списке:

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);
}

Теперь мы готовы сделать преобразование:

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;
}

Немного сложно обмануть голову, но в основном вы делаете удаления, чтобы вы знали, для каждого ключа вы либо вставляете, либо двигаетесь. Затем вы снова просматриваете список и если его достаточно, вы перемещаете его из той части списка, которую вы еще не видели, иначе вставьте. К тому времени, когда вы дойдете до конца, все выстроится.