19 января 2015 в 13:53

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

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

Содержание


  • I. Пересечение массивов
  • II. Разность массивов
  • III. Объединение массивов
  • IV. Симметрическая разность массивов
  • Заключение


I. Пересечение массивов


Пересечение двух массивов A и B — это массив только с теми элементами A и B, которые одновременно принадлежат обоим массивам, без дублей.

image

Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.

function intersection(A, B)
{
	var m = A.length, n = B.length, c = 0, C = [];
	for (var i = 0; i < m; i++)
	{ 
		var j = 0, k = 0;
		while (B[j] !== A[ i ] && j < n) j++;
		while (C[k] !== A[ i ] && k < c) k++;
		if (j != n && k == c) C[c++] = A[ i ];
	}
	return C;
}


Пример:

intersection ([1,2,3,7,9],[4,5,7,2,1,5]); // На выходе [1,2,7]


II. Разность массивов


Разность двух массивов A и B — это массив с элементами A, не совпадающими с элементами B, без дублей.

image

Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.

function diff(A, B)
{
	var M = A.length, N = B.length, c = 0, C = [];
	for (var i = 0; i < M; i++)
	{
		var j = 0, k = 0;
		while (B[j] !== A[ i ] && j < N) j++;
		while (C[k] !== A[ i ] && k < c) k++;
		if (j == N && k == c) C[c++] = A[ i ];
	}
	return C;
}


Пример:

diff([1,2,3,7,9],[4,5,7,2,1,5]); // На выходе [3,9]
diff([4,5,7,2,1,5], [1,2,3,7,9]); // На выходе [4,5]


III. Объединение массивов


Объединение двух массивов A и B — это массив с элементами A и элементы массива B, без дублей.

image

Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.

function sum(A, B)
{
	var M = A.length, N = B.length, count = 0, C = [];
	C = A;
	count = M;
	var cnt = 0;
	for (var i=0;i<N;i++)
	{ 
		var plus = false;
		for (var j=0;j<M;j++)
			if (C[j] == B[i]) {plus = true; break;}
		if (plus === false) C[count++] = B[i];
	}
	return C;
}


Пример:

sum([1,2,3,7,9],[4,5,7,2,1,5]); // На выходе [1,2,3,7,9,4,5]
sum([4,5,7,2,1,5],[1,2,3,7,9]); // На выходе [4,5,7,2,1,5,3,9]


IV. Симметрическая разность массивов


Симметрическая разность двух массивов A и B — это такой массив, куда входят все те элементы первого массива, которые не входят во второй массив, а также те элементы второго массива, которые не входят в первый массив.

image

Сложность алгоритма O(2m*n), где m и n — длины входных массивов A и B соответственно.

По сути это вычитание массивов, сначала A из B, затем B из A.

function symmetricDiff(A,B)
{
	var M = A.length, N = B.length, c = 0, C = [];
	for (var i = 0; i < M; i++)
	{
		var j = 0, k = 0;
		while (B[j] !== A[ i ] && j < N) j++;
		while (C[k] !== A[ i ] && k < c) k++;
		if (j == N && k == c) C[c++] = A[ i ];
	}
	for (var i = 0; i < N; i++)
	{
		var j = 0, k = 0;
		while (A[j] !== B[ i ] && j < M) j++;
		while (C[k] !== B[ i ] && k < c) k++;
		if (j == M && k == c) C[c++] = B[ i ];
	}
	return C;
}


Пример:

symmetricDiff([1,2,3,7,9],[4,5,7,2,1,5]);// На выходе [3,9,4,5]
symmetricDiff([1,2,3,4,5],[3,4,5,6,7]); // На выходе [1,2,6,7]


Заключение


Живой пример на примере друзей вконтакте. При вводе ссылок на страницы пользователей вконтакте сервис выдает все пересечения массивов друзей пользователей (пересечения — это общие друзья пользователей).
Роман Мещеряков @dooza
карма
2,0
рейтинг 0,0
Пользователь
Самое читаемое Разработка

Комментарии (7)

  • +14
    Отсортируйте массивы и сложность всех операций упадёт до O(m+n) — они будут производиться за один проход по массивам.
    И даже если массивы не отсортированы, то предварительная сортировка потребует O(m*log(m)+n*log(n)). Если оба множества достаточно велики, то это будет куда лучше, чем O(m*n).
  • 0
    Гораздо интересней проделывать те же операции, но не с массивами, а коллекциями (массивами объектов).
  • +2
    Ни в коем случае не говорю, что нужно использовать библиотеки без понимания того, как это работает, но время это экономит очень сильно. Lo-Dash отличная штука в таких ситуациях :)

    I. _.intersection — lodash.com/docs#intersection
    II. _.difference — lodash.com/docs#difference
    III. _.union — lodash.com/docs#union
    IV. _.xor — lodash.com/docs#xor

    P.S. Прошу прощения, что без нормального форматирования ссылок — карму слили злостные школьники. :)
  • 0
    Дополню dannyzubarev, хотелось бы бенчей сравнения с аналогичными методами того же lodash.
  • 0
  • 0
    Если множества неупорядочены, то сортировкой мы их уж точно не «испортим» то есть понятно что отсортировать проще.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.