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

Вот алгоритм, который я составил для объединения двух списков, 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). Это было необходимо, потому что мы не хотели перерисовывать всю таблицу при изменении данных; различия между списками, вероятно, были небольшими и затрагивали только одну или две строки. Возможно, это не тот алгоритм, который вы ищете для своих данных. Если нет, дайте мне знать, и я удалю это.

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

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

http://www.levenshtein.net/

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

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

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

Вот мое решение, которое генерирует перечисление простых значений 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'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 };
            }
        }
    }

Только что заметил, что в 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;
    }
}

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

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

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

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

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

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