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

[DjDiablo]

группы гораздо больше свидетельствуют о структуре чем отдельные числа

После анализа во втором своем посте (#58) Я уже не так уверен в этом. Слишком много возможных интерпретаций результатов сравнения двух массивов. Единственный способ оценить какая интерпритация верна это оценить ее стоимость(колво затраченных операций) или ценность (длинну комбинации). Очень может быть что простые алгоритмы для оценки стоимости которые уже разработаны, (почитать можно на хабре) окажутся эффективней чем выделение групп с последующим поиском наиболее оптимальной(читай длинной) комбинации.

Проверять все это в падлу и так отвлекся.

З.Ы. Стоимость это то что вы потратили, ценность это то что вы получили.

[cyber]

нет, любые данные, числа, обьекты, что угодно, блин а, ты что не знаешь как ui работает?

А вдруг у ты изобрел что то новое, лучше уточнить)

[cyber]

А почему бы не использовать бинарный поиск вместо indexOf, он же быстрее на сколько я вижу http://jsperf.com/binarysearch-vs-indexof/4

var BinarySearchBitshift = function (list, val) {
  	var min = 0
  	  , max = list.length-1
  	  ;
  	
  	for(;;)
  	{
  		// fall back to linear search, 11 seems to be a good threshold, but this depends on the uses comparator!! (here: ===)
  		if ( min + 11 > max ) {
  			for(var i=min ; i<=max; i++ ) {
  				if( val === list[i] ) {
  					return i;
  				}
  			}
  
  			return -1;
  		}
  
  		var mid = (min + max) >> 1;
  		var dat = list[ mid ];
  
  		if ( val === dat ) {
  			return mid;
  		} 
  
  		if( val > dat ) {
  			min = mid + 1;
  		} else {
  			max = mid - 1;
  		}
  	}
  };

[рони]

function compare(f, d) {
    var e = {
        relocation: [],
        insert: [],
        length: d.length
    }, c = d + ", " + f ,
        b = f.slice();
    if (c = c.match(/([^,]\S*[^,])(?=,[\s\S]*\s[\s\S]*\1)/g)) {
        c.reverse();
        for (var a = 0; a < c.length; a++) {
            var g = ("" + b).slice(0, ("" + b).lastIndexOf(c[a]) + 1).split(",").length - 1,
                h = c[a].split(",").length,
                k = b.splice(g, h);
            e.relocation.push([g, h]);
            b = k.concat(b)
        }
    }
    for (a = 0; a < d.length; a++) d[a] != b[a] && (b.splice(a, 0, d[a]), e.insert.push([a, d[a]]));
    return e
};

function conversion(b, c) {
    for (var a = 0; a < c.relocation.length; a++) {
        var d = c.relocation[a];
        b = b.splice(d[0], d[1]).concat(b)
    }
    for (a = 0; a < c.insert.length; a++) d = c.insert[a], b.splice(d[0], 0, d[1]);
    b.length = c.length;
    return b
};

var oldArray = [1, 2, 3, 4, 5];
var newArray = [11, 3, 4, 3, 11, 21];
var changes = compare(oldArray, newArray);
var len = changes.relocation.length + changes.insert.length + 1;//кол-во затраченных операций в conversion
alert(newArray +"\n"+conversion(oldArray, changes)+"\n"+len)
var oldArray = [4, 50, 6, 7, 8, 9,1, 2, 3, 50 ];
var newArray = [1, 2, 4, 50, 6, 7, 8, 9,50];
var changes = compare(oldArray, newArray);
var len = changes.relocation.length + changes.insert.length + 1;
alert(newArray +"\n"+conversion(oldArray, changes)+"\n"+len)
var oldArray = [1, 2, 3, 4, 5];
var newArray = [5, 4, 3, 2, 1];
var changes = compare(oldArray, newArray);
var len = changes.relocation.length + changes.insert.length + 1;
alert(newArray +"\n"+conversion(oldArray, changes)+"\n"+len);
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);
var len = changes.relocation.length + changes.insert.length + 1;
alert(newArray +"\n"+conversion(oldArray, changes)+"\n"+len);
var oldArray = [1, 2, 3, 4, 5];
var newArray = [1, 2, 3, 5, 4, 45];
var changes = compare(oldArray, newArray);
var len = changes.relocation.length + changes.insert.length + 1;
alert(newArray +"\n"+conversion(oldArray, changes)+"\n"+len);

[monolithed]

А почему бы не использовать бинарный поиск вместо indexOf

Бинарный есть смысл использовать только на больших множествах.

[cyber]

рони, скорость выполнения ужасная)
http://jsperf.com/compare-arrays-test

[рони]

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

function rand()
{  var l = Math.round(Math.random() * 100), a = [];
   for (var i=0; i<l; i++)  {a[i]=Math.round(Math.random() * 100)}
   return a
}

function compare_indexOf(fArr,arr) {

    var search = arr.slice(),
        insert = [],
        remove = [],
        replace = [];

    for(var i = 0, index; i < fArr.length; i++) {

        index = search.indexOf(fArr[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
    }

}
function compare(f, d) {
    var e = {
        relocation: [],
        insert: [],
        length: d.length
    }, c = d + ", " + f ,
        b = f.slice();
    if (c = c.match(/([^,]\S*[^,])(?=,[\s\S]*\s[\s\S]*\1)/g)) {
        c.reverse();
        for (var a = 0; a < c.length; a++) {
            var g = ("" + b).slice(0, ("" + b).lastIndexOf(c[a]) + 1).split(",").length - 1,
                h = c[a].split(",").length,
                k = b.splice(g, h);
            e.relocation.push([g, h]);
            b = k.concat(b)
        }
    }
    for (a = 0; a < d.length; a++) d[a] != b[a] && (b.splice(a, 0, d[a]), e.insert.push([a, d[a]]));
    return e
};
var oldArray = rand();
var newArray = rand();
var time_indexOf = new Date();
var changes = compare_indexOf(oldArray, newArray);
time_indexOf = (new Date()).getTime() - time_indexOf.getTime()
var len_indexOf = changes.remove.length + changes.insert.length + changes.replace.length;
var time = new Date();
var changes = compare(oldArray, newArray);
time = (new Date()).getTime() - time.getTime()
var len = changes.relocation.length + changes.insert.length + 1;
alert('len_indexOf : ' + len_indexOf + ' time: ' + time_indexOf + '\nlen: ' + len + ' time: ' + time + '\nlength : ' + newArray.length);

[cyber]

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

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

[рони]

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

так удалять то нечего )))
всё лишнее обрезается строкой

b.length = c.length;

[cyber]

рони, т.е нечего?
Если элемента нет во втором массиве, но есть в первом то его нужно удалить.