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

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

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 : []
}

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

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

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

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

O (M * N)

Element.insertAdjacentHTML ?

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

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

Не, ты не понял немного, там как короче есть 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 и.т.п. и смотри как они вызываются и запоминай это, но я считчаю это костылем при чем грубым.

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

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

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

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

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

Мне почему то кажется, что ты не так понял. Задача не найти "похожие с учетом 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

nerv_, почти верно =) но все немного сложнее.

У меня есть 2 массива и 2 каретки, вначале обе каретки на нулях, начинаем итерировать.

1) смотрим, если значения равны, увеличиваем обе каретки на 1 continiue.
2) смотрим, если значения не равны, то начинаем делать грязь, вначале одну каретку держим на месте, а второй пробегаемся вперед пока не наткнемся на такие же число которое в первой каретке, запоминаем какое расстояние пробежала вторая каретка. Потом делаем то же самое с первой кареткой. получаем 2 кратчайщих расстояния до ближайшего "совпадения" элементов.

3) смотрим, если первое расстояние больше, то элементы были удалены, если второе больше то добавлены.

короче трудно описать словами как сделаю покажу



ай красавец)!! но оно какой-то бред выдает)

Грубо говоря я хочу получить карту изменения которые мне надо произвести чтобы получить из одного массива второй =)

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

Короче, это гемор :D

nerv_, так ты определишь вставку, а как ты определишь что элементы были удалены не пробегаясь по второму массиву?

И вообще давай ка код раз такой умный) мне кажется у тебя не получится пробегаться только по одному массиву.

при чем моя реализация уже возвращает обьект типа

{
remove:[{start:3,end:4},{start:6,end:11}],
insert:[{start:1,end:2}],
replace:[]
}

Maxmaxmaximus4,
может проще форкнуть ангуляр? :)

так?

Array.prototype.compare = function(arr) {
    
    var search = arr.slice(),
        remove = [];
    
    for(var i = 0, index; i < this.length; i++) {
        
        index = search.indexOf(this[i]);

		if(!~index) {
          
			remove.push(this[i]);
            
            continue;
        }
        
        delete search[index];

	};
    
    return {
        remove: remove,
        insert: search
    }
    
}

console.log([1,2,3,4].compare([2,3,4,5, 34, 2 , 3434]));

а там нет этого лол) там они вообще ядерно не оптимально делают)
я и хочу переплюнуть их по этому вот.

cyber, да, ты верно понял что надо =) тока твоя реализация не может схавать даже
var q = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var w = [1, 2, 4, 5, 6, 7, 8, 9];

Maxmaxmaximus4, честно , завязывай с наркотиками...

Array.prototype.compare = function(arr) {
    
    var search = arr.slice(),
        remove = [];
    
    for(var i = 0, index; i < this.length; i++) {
        
        index = search.indexOf(this[i]);

		if(!~index) {
          
			remove.push(this[i]);
            
            continue;
        }
        
        delete search[index];

	};
    
    return {
        remove: remove,
        insert: search
    }
    
}

//console.log([1,2,3,4].compare([2,3,4,5, 34, 2 , 3434]));

alert([1, 2, 3, 4, 5, 6, 7, 8, 9].compare([1, 2, 4, 5, 6, 7, 8, 9]).remove);

cyber, я вообще не понимаю чо делает твоя функция она должна возвращать массив индексов, а не массив значений.

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

возможно я не очень внимательно читал, но исправить ее не проблема.
просто сникерсни.
Хотя насчет скорости я не уверен)

Array.prototype.compare = function(arr) {
    
    var search = arr.slice(),
        insert = [],
        remove = [];
    
    for(var i = 0, index; i < this.length; i++) {
        
        index = search.indexOf(this[i]);

		if(!~index) {
          
			remove.push(i);
            
            continue;
        }
        
        delete search[index];

	};
    
    search.forEach(function (elem, i) {
        if(elem)
          insert.push(i);     
    });
    
    return {
        remove: remove,
        insert: insert
    }
    
}

//console.log([1,2,3,4].compare([2,3,4,5, 34, 2 , 3434]));

console.log([1, 2, 3, 4, 5, 6, 7, 8, 9].compare([1, 2, 4, 5, 6, 7, 8, 9]));

cyber, слушай, ну она даже не справляется с этим
var arr1 = [3, 3, 3, 3, 3];
var arr2 = [3, 3, 11, 3, 3];

и с этим

var arr1 = [3, 3, 3, 3, 3];
var arr2 = [3, 3, 3, 3, 11];

Maxmaxmaximus4, так либо ты наркомана, либо я.

Array.prototype.compare = function(arr) {
    
    var search = arr.slice(),
        insert = [],
        remove = [];
    
    for(var i = 0, index; i < this.length; i++) {
        
        index = search.indexOf(this[i]);

		if(!~index) {
          
			remove.push(i);
            
            continue;
        }
        
        delete search[index];

	};
    
    search.forEach(function (elem, i) {
        if(elem)
          insert.push(i);     
    });
    
    return {
        remove: remove,
        insert: insert
    }
    
}

//console.log([1,2,3,4].compare([2,3,4,5, 34, 2 , 3434]));

console.log([3, 3, 3, 3, 3].compare([3, 3, 11, 3, 3]));

код вернет

insert: [2] // элемент с индексом 2 из нового массива нужно вставить
remove: [4] // элемент с индексом 4 из старого массива нужно удалить

cyber, походу я наркоман, я забыл что ты replace не сделал. щас добавлю replase в твою реализацию и посмотрим как фурычит. но пока, я должен признаться, я охренел) так просто вроде все сделал. если честно я вообще в ахуе, не верится что оно работает)

к слову, вот здесь он должен выдать

var oldArray = [1, 2, 2, 200, 6, 6];
var newArray = [1, 2, 2, 200, 200, 6];

replaсe:[4],
remove:[],
insert:[]

задача то кратчайшее преобразование найти

Давай подумаем как в эту реализацию можно добавить replace?

я тут слегка отрефакторил

Array.prototype.compare = function(arr) {
    var search = arr.slice();
    var insert = [];
    var remove = [];

    for (var i = 0, index; i < this.length; i++) {
      index = search.indexOf(this[i]);
      if (index < 0) remove.push(i);
      else delete search[index];
    }

    for (var i = 0; i < search.length; i++) {
      if (i in search) insert.push(i);
    }

    return {
      remove: remove,
      insert: insert
    }
}

по уму, взять и посмотреть где в remove и insert есть одинаковые элементы, это ознчает что там происходит удаление и вставка, то есть замена =) но нет, не всегда замены детектируется так, щас поищу я когда тестировал её там было пару случаев когда индексы разные были, если изменения происходили на коцне массива.

Maxmaxmaximus4, лучше ищи нормальный вариант, так как мой работает слишком медленно даже для сравнения массива из 100 элементов.
http://learn.javascript.ru/play/7rjdL

я обьясню почему, просто это тут у нас ладно li, а вдруг у нас там в этом li целые контроллеры и куча детей это допустим сообщения в чате и они сложные там стока разметки в каждом и.т.п. не хотелось бы ПРОСТО ТАК удалять одно и заменять другим, дело в том что ui изменения то автоматически перерисовывает. ладно я думаю это мелочи, вообще ты гений блин) это то что нужно! СПАСИБО! Я даже показывать не буду какого монстра Я напилил)

он будет вызываться только если обсервер обнаружит изменения в массиве=) так что это не страшно, это миллисекунды, они КУДА быстрее чем вставка и перерисовка DOM

Maxmaxmaximus4, хотя, тест какой то кривой, щас проверю скорость выполнения и скажу)

cyber, кстати зачем ты ставишь такое ядерное количество красных строк там где они по смыслу не нужны? они же теряют свою ценность так и когда они ВЕЗДЕ, настоящие красные строки не заметны =)



шо-то с тестом явно не так

мне так читать свой код легче потом)

Знаешь как надо потестить? Используя эти преобразования из старого массива получить новый, у меня что-то не получается.

Хз, я сонный немного, голова уже не варит.

Кстати тест, реально еврейский у меня он 3 раза показал 3к

Твоя функция не справилась с этим

var oldArray = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var newArray = [1, 2, 3, 5, 34, 32, 4, 45];
var changes = compare(oldArray, newArray);

console.log(changes);

function compare(oArr, arr) {
    var search = arr.slice();
    var insert = [];
    var remove = [];

    for (var i = 0, index; i < oArr.length; i++) {
      index = search.indexOf(oArr[i]);
      if (index < 0) remove.push(i);
      else delete search[index];
    }

    for (var i = 0; i < search.length; i++) {
      if (i in search) insert.push(i);
    }

    return {
      remove: remove,
      insert: insert
    }
}

выбирать рандомно индексы и менять?
Как то так, писал прям в форме отправки (может не работать)

function genArr(count) {
   
    var arr = [];
    
    for(var i = 0; i < count; i++) {
     
      arr.push(i % 2 ? Math.random(): i);
    
    }
    
    return arr;
  
  }

var arr = genArr(100),
     arr2 = arr.slice();

for(var i = 0, index; i < 20; i++) {
index = Math.round(Math.random() * 100);
arr2[index] = i;

}

var oldArray = [1, 2, 3, 4, 5];
var newArray = [1, 2, 3, 5, 4, 45];

вот с этим не справляется пишет что insert:[5] и все
он не видит разницы между 4,5 и 5,4 щам будем фиксить)

я так и не понял где

"remove 5,6,7,8 insert 4,5,7 "

Maxmaxmaximus4, ну вообще то она порядок не учитывает)

cyber, уже учитывает, блять не против изредка помогать в написании великой и ужасной ui? ты гениален!!!! я серьезно!! я блять чо тока не придумал чтобы это сделать, да, мое было бы оптимальнее и "правильнее" но млять, кому оно науй надо если и так РАБОТАКЕТ и так МАЛО КОДУ, при чем не факт что мое было бы быстрее так как там несколько проходов и прочего, моя возвращала дамп который потом надо было бы парсить и делать по нему что-то, а твоя ГЕНИАЛЬНАЯ функция ТУПО ВОЗВРАЩАЕТ ПОРЯДОК ДЕЙСТВИЙ КОТОРЫЕ НАДО СДЕЛАТЬ ЧТОБЫ ПОЛУЧИТЬ ИЗ ОДНОГО МАССИВА ДРУГОЙ)!!!!! ЭТО ТО-ЧТО-НУЖНО!! Ты гениален! Правда!

вот кстати исправленная версия:

function compare(oArr, arr) {
    var search = arr.slice();
    var insert = [];
    var remove = [];

    for (var i = 0, index; i < oArr.length; i++) {
      index = search.indexOf(oArr[i], i);
      if (index < 0) remove.push(i);
      else delete search[index];
    }

    for (var i = 0; i < search.length; i++) {
      if (i in search) insert.push(i);
    }

    return {
      remove: remove,
      insert: insert
    }
  }

Maxmaxmaximus4,
лови, теперь с блэкджеком и replace

Array.prototype.compare = function(arr) {
    
    var search = arr.slice(),
        insert = [],
        remove = [],
        replace = [];
    
    for(var i = 0, index; i < this.length; i++) {
        
        index = search.indexOf(this[i]);

		if(!~index) {
          
			remove.push(i);
            continue;
        }
        
      	i != index && replace.push({old: i, new: index});
        
        delete search[index];

	};
    
    search.forEach(function (elem, i) {
        if(elem)
          insert.push(i);     
    });
    
    return {
        remove: remove,
        insert: insert,
      	replace: replace
    }
    
}


console.log([1, 2, 3, 4, 5].compare([1, 2, 3, 5, 4, 45]));

ща потестим)