Бінарні операції над впорядкованими множинами

В попередній статті я писав про бінарних операцій над невпорядкованими наборами. У цій статті ми розглянемо алгоритми з меншою складністю виконання, для впорядкованих множин.



Зміст
I. Перетин впорядкованих множин
II. Різниця впорядкованих множин
III. Об'єднання впорядкованих множин
IV. Симетрична різниця впорядкованих множин
Висновок

I. Перетин впорядкованих множин
Перетин двох упорядкованих множин A та B — це безліч тільки з тими елементами A та B, які одночасно належать обом множиною, без дублів. Складність алгоритму O(m+n), де m та n — довжини вхідних множин A та B відповідно.

Зробив невелику анімацію, щоб показати як працює алгоритм.
image

Приклад реалізації на javascript:
function intersec_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]; // запишемо елемент в масив array_3
k++,i++,j++; // і зрушимо позицію у всіх масивах 3
} else {
if (array_1[i] < array_2[j]) {
i++; // зрушимо позицію в першому масиві
} else {
j++; // зрушимо позицію у другому масиві
}
}
}
return array_3;
} 


Звернення до функції:
intersec_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // на виході [3, 8]


II. Різниця впорядкованих множин
Різниця двох упорядкованих множин A та B — це безліч з елементами A, не збігаються з елементами B, без дублів. Складність алгоритму O(m+n), де m та n — довжини вхідних впорядкованих множин A та B відповідно.



function 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])
{ 
i++,j++;
} else {
if (array_1[i] < array_2[j]) {
array_3[k] = array_1[i];
k++;
i++; // зрушимо позицію в першому масиві
} else {
j++; // зрушимо позицію у другому масиві
}
}
}
if (i < n)
{
while (i < n) {
array_3[k] = array_1[i];
k++, i++;
}
}
return array_3;
} 


diff_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // на виході [1, 2, 5]


III. Об'єднання впорядкованих множин
Об'єднання двох упорядкованих множин A та B — це безліч з елементами A і елементи множини B, без дублів. Складність алгоритму O(m+n), де m та n — довжини вхідних впорядкованих множин A та B відповідно.



function sum_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++,j++;
} else {
if (array_1[i] < array_2[j]) {
array_3[k] = array_1[i];
k++;
i++; // зрушимо позицію в першому масиві
} else {
array_3[k] = array_2[j];
k++;
j++; // зрушимо позицію у другому масиві
}
}
}
if (i < n)
{
while (i < n) {
array_3[k] = array_1[i];
k++, i++;
}
} else {
if (j < m)
{
while (j < m) {
array_3[k] = array_2[j];
k++, j++;
}
}
}
return array_3;
} 


sum_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // на виході[1, 2, 3, 5, 6, 8, 12, 24, 47]


IV. Симетрична різниця впорядкованих множин
Симетрична різниця двох упорядкованих множин A та B — це така множина, куди входять всі ті елементи першого упорядкованого безлічі, які не входять у другу впорядкована множина, а також ті елементи другого упорядкованого безлічі, які не входять в перше впорядкована множина. Складність алгоритму O(2(m+n)), де m та n — довжини вхідних впорядкованих множин A та B відповідно.

По суті це віднімання множин, спочатку A з B, потім B з A.

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])
{ 
i++,j++;
} else {
if (array_1[i] < array_2[j]) {
array_3[k] = array_1[i];
k++;
i++; // зрушимо позицію в першому масиві
} else {
j++; // зрушимо позицію у другому масиві
}
}
}
if (i < n)
{
while (i < n) { 
array_3[k] = array_1[i];
k++, i++;
}
}

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

return array_3;
} 


symmetric_diff_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // на виході[1, 2, 5, 6, 12, 24, 47]


Висновок
Мені часто доводиться працювати з відсортованими масивами, тому ці алгоритми дуже сильно прискорюють процес. Приклад реалізації методу intersec_sort_arr, ви можете подивитися в моєму додатку vk.com. За допомогою цього методу я знаходжу загальних учасників спільнот працюючи з відсортованими масивами, в мільйони елементів, метод справляється дуже швидко. До цього використовував метод описаний в моїй попередній статті, обробка масивів була дуже повільною.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.