Бинарные операции над упорядоченными множествами

[sys_int64]

Очень интересно, спасибо за статью.

[0leGG]

Симметрическую разность тоже можно за один проход посчитать, просто отслеживая минимальный элемент из имеющихся двух списков:

function symmetric_diff_sort_arr(array_1,array_2)
{
    var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = [];
    while ((i < n) && (j < m)) // пока не дошли до конца массива 
    { 
        if (array_1[i] < array_2[j]) { 
            array_3[k] = array_1[i];
            k++;
            i++; // сдвинем позицию в первом массиве
        } else if (array_1[i] > array_2[j]) {
            array_3[k] = array_2[j];
            k++;
            j++; // сдвинем позицию во втором массиве
        } else {
            i++, j++;
        }
    }
    while (i < n) { 
        array_3[k] = array_1[i];
        k++, i++;
    }
    while (j < m) {
        array_3[k] = array_2[j];
        k++, j++;
    }
    return array_3;
}

[dooza]

отлично, добавил предложенный вами способ в статью.

[krati]

Можно две строчки изменить в функции объединения и получится функция симметрической разности

if (array_1[i] == array_2[j])
{ 
    //array_3[k] = array_1[i];
    //k++,
    i++,j++;
}

[0leGG]

Ну да, по сути мы разбиваем элементы исходных множеств A и B на три типа — «есть только в A» (ветка a[i] < b[j]), «есть только в B» (ветка a[i] > b[j]), «есть и в A, и в B» (ветка a[i] == b[j]). Все перечисленные функции есть комбинации этих трёх непересекающихся множеств, содержащих в себе все элементы исходных.

[dtestyk]

Упорядоченные не значит отсортированные. Будут ли алгоритмы работать на несортированных данных?

Алгоритм для симметрической разности(тот который «2 прохода»): объединение двух разностей, можно было бы так и записать:

function symmetric_diff_sort_arr(array_1,array_2){
	var arr_diff1=diff_sort_arr(array_1,array_2)
	var arr_diff2=diff_sort_arr(array_2,array_1)
	//return sum_sort_arr(arr_diff1,arr_diff2)
	return arr_diff1.concat(arr_diff2)
}

[dtestyk]

>Упорядоченные не значит отсортированные. Будут ли алгоритмы работать на несортированных данных?
можно не отвечать, перепутал массив и упорядоченное множество

[tagir_valeev]

Никогда не понимал, зачем люди пишут так:

if (j < m)
{
    while (j < m) {
        ...
    }
}

Верхнее условие абсолютно не нужно. Если оно не выполняется, то цикл всё равно не выполнится. А если выполняется, то в начале цикла будет два раза одинаковая проверка.

И да, в JavaScript лучше сравнивать по ===, если у вас нет хорошей причины так не делать.

[dooza]

Действительно, поправил. Сам не обратил внимания на это.