Как найти различие между двумя массивами?

[Maxmaxmaximus4]

Нужно замутить что-то наподобие гита. Чтобы функция смотрела различия между массивами и возвращала примерно такой обьект:

var oldArr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var newArr = [1, 2, 5, 6, 7, 10, 10, 8, 9];

var differences = {
    removed : [2, 3],
    inserted: [5, 6],
    changed : []
}

У кого есть какие идеи?

[monolithed]

У кого есть какие идеи?

Какие тут могут быть идеи, это банальная задача на вычисление редакционного расстояния Левенштейна.
Если нужна транспозиция, то Дамерау — Левенштейна.

[Maxmaxmaximus4]

Ушел гуглить, спасибо, а то я уже свой алгоритм мутить начал. Кстати вопрос, оно вообще быстрое? Это мне нужно для оптимизации repeat'ера чтобы если у нас 2000 элементов то и новый добавляется вначале то он не вставлял новый dom в конец а все предыдущие перерендеривал, а тупо вставил dom вначало )

[l-liava-l]

Какие тут могут быть идеи, это банальная задача на вычисление редакционного расстояния Левенштейна

что то меня ржать понесло с этой строки

[monolithed]

Кстати вопрос, оно вообще быстрое?

O (M * N)

новый добавляется вначале то он не вставлял новый dom в конец а все предыдущие перерендеривал, а тупо вставил dom вначало

Element.insertAdjacentHTML ?

[cyber]

походу зря я делал в "лоб")
Пошел читать про "расстояния Левенштейна"

imageLoader.prototype._compare = function(images) {

	 images = images[this._activeCategory];

 	var  imgList = this.ImageList[this._activeCategory],
      
      leng = Math.max(images.length, imgList.length);
	  

	for(var i = 0; i < leng; i++) {

		if(imgList[i] &&
			!~images.indexOf(imgList[i])) {

			this._removeImage(imgList[i]);
		}


		if(images[i] && 
		   !~imgList.indexOf(images[i])) {

		   	this._createImage(images[i]);

		}

	};


	return this;
};

[Maxmaxmaximus4]

Element.insertAdjacentHTML ?

Не, ты не понял немного, там как короче есть scope обьект там хранятся данные, и есть <li>{item}</li>

мы хотим повторить li столько раз сколько элементов в массиве и значение каждого элемента засовывать в scope.item и она будет рисоваться в элементе. Для этого мы создаем scope для каждого li. И делаем такие пары scope+li столько раз сколько элементов в массиве.
Потом пробегаемся по созданным скоупам и добавляем туда в scope.item соответствующее значение массива. Суть в том что перерисовка {в таких тегах} дорогая операция.

Если у нас массив [1,2,3,4], то разметка будет такой:

<li> {item}</li>
<li> {item}</li>
<li> {item}</li>
<li> {item}</li>


и при рендеринге в {теги} подставятся значения

<li> 1</li>
<li> 2</li>
<li> 3</li>
<li> 4</li>


потом человек делает arr.unshift(0);
массив становится такой [0, 1,2,3,4], и мой текущий алгоритм посмотрит, увидит что длинна изменилась и стала больше, добавит один li в конец того списка li, снова пробежится по всем скоупам и установит им соответствующие значения массива.
суть тут в том что по сути новый элемент массива мы добавили в начало массива, а li добавили в конец. И все значения сместились ка бы вниз, и требуется перерисовка всех элементов, понятно почему? Ну вот, а все потому что алгоритм тупой, и не знает ГДЕ ИМЕННО добавились данынне а где удалились, и я хочу это узнавать.

Представим что у нас 2000 элементов и мы добавили в начало массива одно значение, html элемент добавится в конец, а все 2000 элементов перерисуются в соответствии с новыми сместившимися значениями, это очень не оптимально.


Конечно кто-то из вас скажет - просто сделай обертки на методы массива такие как pop push unshift и.т.п. и смотри как они вызываются и запоминай это, но я считчаю это костылем при чем грубым.

[cyber]

Maxmaxmaximus4, а не проще не давать прямой доступ к массиву ?
А сделать к примеру методы Add, Remove, Edit, это будет оптимальнее сравнения 2х массивов.

[Maxmaxmaximus4]

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

<li repeat="item in arr">{item}</li>

function Ctrl() {
    arr = [1, 2, 3, 4, 5] //челоевк работает только с этим
    arr = [10] //захочет, вообще новый массив засунет, и DOM должен все это отражать 
}

monolithed, щас я короче свой алгоритм запилю) посмотрим чо выйдет.

[nerv_]

Какие тут могут быть идеи, это банальная задача на вычисление редакционного расстояния Левенштейна.
Если нужна транспозиция, то Дамерау — Левенштейна.

Мне почему то кажется, что ты не так понял. Задача не найти "похожие с учетом k различий", а "поиск по точному совпадению" (если можно так выразится).

Грубо говоря у него есть два массива, ему надо пробежаться циклом по одному и проверить наличие этого элемента в другом. Я сейчас не принимаю во внимание, что элементом массива может быть массив или объект. К слову, объекты придется сравнивать по значению (как и массивы).

1. Идешь циклом по новому массиву
2. Смотришь, если ли такой элемент в старом массиве
3. Если есть и в той же позиции, идешь дальше
4. Если нет, добавляешь
5. Если отличается позиция перемещаешь
6. Останется отсечь элементы кот. остались в старом массиве, но нет в новом

На первый взгляд можно сделать за один проход по новому массиву (с доп. массивами индексов). Могу ошибаться.

upd: в пыхе, кстати есть http://php.net/manual/ru/function.levenshtein.php и http://www.php.net/manual/ru/function.similar-text.php

upd2: А вот левенштейн на js