Algorytm set_differences

Zbiór gotowych algorytmów ze standardowej biblioteki języka C++ jest bardzo użyteczny, o tym nie trzeba długo nikogo przekonywać. Choć czasem, gdy trzeba wykonać kilka rzeczy naraz, bądź kilka kolejnych algorytmów na tych samych danych, możemy stracić na wydajności, szczególnie jak danych jest wiele, a złożoność algorytmu liniowa.

Czasem warto trochę pomyśleć i napisać coś dedykowanego, ewentualnie połączyć 2 algorytmy. Oczywiście tylko, jeśli jest to możliwe i w miarę proste, np. gdy oba algorytmy mają podobną budowę.

Właśnie miałem taki problem. Potrzebowałem z 2 kontenerów wyznaczyć różnicę jednego kontenera względem drugiego i odwrotnie. Pierwotny problem był nieco inny, chciałem jeszcze wyznaczyć część wspólną, ale jak się później okazało, nie jest mi ona do niczego potrzebna ;)

Do wyznaczania różnicy dwóch zbiorów STL posiada odpowiedni algorytm, jest to set_difference w standardowej przestrzeni nazw. Jego budowa wewnętrzna jest dosyć prosta, a złożoność liniowa. Aczkolwiek wywołanie dwukrotne tego algorytmu na tych samych zakresach w celu wyznaczenia różnić w stosunku do siebie samych zajmie dwa razy więcej czasu. A wystarczy tylko dodać “jedną linijkę” do kodu algorytmu i mamy zysk prawie 50%.

Poniżej “moja” próba implementacji algorytmu set_differences, wyznaczającego różnice dwóch posortowanych zakresów (algorytm operuje na posortowanych danych) względem siebie. W wyniku dest1 zawiera wszystkie elementy występujące w pierwszym zakresie, a nie występujące w drugim, a dest2 odwrotnie. Kod prezentuje się tak:

template<typename InIt1, typename InIt2, typename OutIt1, typename OutIt2>
void set_differences(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2,
					 OutIt1 destDiff1, OutIt2 destDiff2)
{
	while (first1 != last1 && first2 != last2) {
		if (*first1 < *first2) {
			*destDiff1 = *first1;
			++destDiff1;
			++first1;
		} else if (*first2 < *first1) {
			*destDiff2 = *first2;
			++destDiff2;
			++first2;
		} else {
			++first1;
			++first2;
		}
	}
	std::copy(first1, last1, destDiff1);
	std::copy(first2, last2, destDiff2);
}

I jeszcze kod testujący:

int src1[] = { 0, 1, 2, 3, 4, 5 };
int src2[] = { 4, 5, 6, 7, 8, 9 };

int* src1_end = src1 + sizeof(src1) / sizeof(int);
int* src2_end = src2 + sizeof(src2) / sizeof(int);

std::vector<int>dst1;
std::vector<int>dst2;

set_differences(src1, src1_end, src2, src2_end,
	std::back_inserter(dst1), std::back_inserter(dst2));

std::ostream_iterator<int> out(std::cout, " ");

std::cout << "dst1: ";
std::copy(dst1.begin(), dst1.end(), out);
std::cout << "\n";

std::cout << "dst2: ";
std::copy(dst2.begin(), dst2.end(), out);
std::cout << "\n";

Pokazuje on, że to rzeczywiście działa, wynik powinien być następujący:

dst1: 0 1 2 3
dst2: 6 7 8 9

Chcąc dodać jeszcze wspomniane wyżej wyznaczanie sumy, wystarczyłoby dodać kolejną dodatkową linijkę do kodu, bo budowa set_intersection jest zbliżona do set_difference.

Jak widać czasem warto pomyśleć i się zastanowić, bo niewielkim wysiłkiem można osiągnąć dużo lepsze efekty ;)