Обновление массива с учетом расположения элементов

[Adelf]

[1, 4, 32, 2, 5, 7, 8]
[4, 8, 17, 32, 2, 7, 9, 3]

идем по второму.

4. - в первом - 1 - не то. 4! - генерируем команду "удалить первый элемент".
переходим ко второму. 8. ищем в первом. начиная с 32. и вот тут главное. Либо ищем до конца(и находим в самом конце 8). Либо не до конца(и не найдя сгенерируем команду - вставить 8. сколько искать - можно выбрать как-нибудь.. например не больше трети длины массива). Либо берем оба варианта, и потом сравним какой получился оптимальнее.

Кстати вопрос, а возможна ли такая ситуация, что элемент исчез в середине и обьявился в конце, например?

 

[Silentland]

Кстати вопрос, а возможна ли такая ситуация, что элемент исчез в середине и объявился в конце, например?

Да, частая ситуация при смене позиции. Или имеются в виду разные элементы? Какой-то удалился, а новый появился? Это редкость

 

[Silentland]

Пример кода, чтобы лучше было видно что с чем сравнивается

var o = oArr.length, //old
    n = nArr.length, //new
    collection = element.data('api');

for (var i = 0, m = Math.max(n, o); i < m; i++) {
    if (nArr[i].id !== oArr[i].id) {
        collection.splice(i, 1);
        ...
    }
}

 

[Silentland]

Задача решена. 3 дня сидел, не думал, что такой тупой.

До конца прояснил в голове условия: необходимо преобразовать один массив в другой с минимальным количеством перестановок. Так же в конечном массиве могут присутствовать элементы, которых нет в начальном или, наоборот, какие-то отсутствовать. Алгоритм должен быть оптимизирован для ситуаций добавления/удаления/перестановки одного элемента.

Получилось вот что:
http://plnkr.co/edit/clW0aVqzaisUkUo44EOL?p=preview

Сложность от O(3n) до O(4n), т.е. линейная. Меньше всего операций удаления/вставки при отличии в одном элементе, больше всего — когда элементы идут в обратном порядке. Предполагалось, что элементы в массивах уникальны, хотя работает и с одинаковыми (тут особо не тестировал). Если кто-то подскажет вариант с еще меньшим количеством перестановок, будет здорово, но, думаю, меньше уже некуда.

 

[hell0w0rd]

а почему нельзя было тупо свести к одинаковому кол-ву элементов и прибавить разницу между числами?) Или вообще не переопределить функции плагина?)

 

[Silentland]

Как именно свести? А функции переопределяй — не переопределяй, все равно за ними стоит вставка в ДОМ. Даже если бы плагин прогонял этот цикл внутри и по факту вставлял уже измененный список, сомневаюсь, что было бы быстрее вставить список из 100 элементов, чем переместить один элемент. Сейчас каждая операция вставки-удаления одного элемента занимает пол секунды, так что, вообще, без вариантов.

 

[fixxxer]

Я понимаю, что уже не надо, но пусть тут полежит

http://en.wikipedia.org/wiki/Levenshtein_distance

 

[Silentland]

Я понимаю, что уже не надо, но пусть тут полежит

Такое ощущение, что я бы и этот материал 3 дня курил Кажется, в том алгоритме два вложенных цикла, т.е. сложность выше на n

 

[fixxxer]

А как ты без вложенного цикла или рекурсии найдешь именно минимальное, а не первое попавшееся?

Другое дело, что именно минимальное может быть не важно, но мы ж в разделе "теория" =)

 

[Silentland]

Ну у меня же как-то ищется)) Пока все решения, которые находит алгоритм являются лучшими. Не смог подобрать пример, который можно было бы еще улучшить