MalDevBlog

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

Czasem warto napisać coś dedykowanego, lub połączyć 2 algorytmy, oczywiście na ile jest to możliwe i w miarę proste, szczególnie, gdy oba algorytmy maja podobną budowę.

Miałem taki problem, potrzebowałem z 2 kontenerów wyznaczyć różnice 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 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, 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 algorytmu i mamy zysk prawie 50%.

Poniżej „moja” implementacja algorytmu set_differences, wyznaczającego różnice dwóch posortowanych zakresów (algorytm operuje na posortowanych danych) względem siebie, tak, że dest1 zawiera wszystkie elementy występujące w pierwszym zakresie, a nie występujące w drugim, a dest2 odwrotnie, czyli elementy z drugiego nie występujące w pierwszym.

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 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";

ukazujący, ż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 z niewielkim wysiłkiem można osiągnąć dużo lepsze efekty ;p