implementacja zbiorów w PHP

Zapewne na pierwszym roku studiów informatycznych spotkacie się z przedmiotem „algorytmy i struktury danych”. Nadarzy się wówczas okazja poznania zbiorów i sposobów ich implementacji, za pomocą wbudowanych typów danych np. w Pascal’u. Pomimo faktu, iż PHP nie oferuje silnej ich kontroli, to wykorzystując właśnie ten język programowania (chociażby dlatego, że to blog o PHP) postaram się wyjaśnić ów zagadnienie. No to zaczynamy.

Według Wikipedii zbiór to:

Zbiór – pojęcie pierwotne w matematyce, a dokładniej w teorii mnogości. Oznacza mnogość, wielość, nieuporządkowany wykaz, kolekcję pewnych różnych elementów rozpatrywanych jako całość. Pojęcie zbioru jest jednym z najbardziej fundamentalnych pojęć matematyki.

Czyli zbiorem możemy nazwać zestaw czterech liter A,B,C i D. Może nim być również kolekcja cyfr 1,2,3,4,5 i 6. Pytanie jakie musimy sobie postawić w tym momencie, to w jaki sposób reprezentować je z wykorzystaniem PHP. Przyda nam się elementarna wiedza na temat operacji logicznych na bitach, oraz użycie pewnego poziomu abstrakcji. Podstawą implementacji będzie bowiem najzwyklejszy integer (tak integer, a nie tablica, która wydaje się dla wielu najlepszym i najprostszym rozwiązaniem). Popatrzmy na poniższy przykład:

	$x = 7;
	// w kodzie dwójkowym 7 to 111

Ponieważ w kodzie dwójkowym mamy do czynienia wyłącznie z wartościami 0 lub 1, możemy skorzystać z tego faktu. Przyjmując założenie, że zero to FALSE (fałsz, element nieobecny) ,a jedynka to TRUE (prawda, element obecny) stwarzamy sobie dobre perspektywy do dalszej pracy. Takie podejście oferuje nam sposób zapamiętywania, czy element występuje czy też należy stwierdzić jego brak.

	$x = 0; // element nie występuje bo
			// w kodzie dwójkowym wartość $x to 0
	$y = 1; // element występuje bo w
			// kodzie dwójkowym wartość $y to 1 

	$f = 3; // zbiór dwuelementowy bo w kodzie
			// dwójkowym wartość $f to 11 (TRUE i TRUE)
	$g = 2; // zbiór jednoelementowy bo w kodzie
			// dwójkowym wartość $f to 10 (TRUE i FALSE)

No dobrze. Ale jakie to ma przełożenie na reprezentację np. dowolnej kolekcji cyfr? Odpowiedź jest trywialnie prosta. Wystarczy przyporządkować każdej możliwej wartości zbioru (np. cyfrze) jeden bit. Zatem w tym przypadku potrzebujemy 10 bitów, odpowiednio dla 0,1,2,3,4,5,6,7,8 i 9. Rzućmy okiem jak to będzie wyglądało.

// 	mapowanie cyfr na bity
//	cyfry				9 8 7 6 5 4 3 2 1 0
//	przyporządkowanie bitów	  0 0 0 0 0 0 0 1 1 0
//	wart. w sys. dziesiętnym	 6
//	-------------------------------------------
// 	w zbiorze mamy dwa elementy: 2 i 1 bo
//	dla tych wartości, bity są równe 1 (TRUE),
//	zatem elementy te występują w zbiorze
$x = 0; 	// zbiór pusty cyfr

$y = 7; 	// zbiór cyfr 0,1 i 2 bo w kodzie dwójkowym
			// to 0000000111

$z = 13; 	// zbiór cyfr 3,2 i 0 bo w kodzie dwójkowym
			// to 0000001101

Wiemy już jak przechowywać zbiory w integerach. Ale to dopiero początek naszych zmagań, ponieważ na obecnym etapie nie mamy zbyt szerokiego pola manewru. Czas dowiedzieć się, że ze zbiorami wiążą się pewne operacje. Możemy je podzielić na dwie grupy.

operacje proste

• sprawdzenie czy zbiór pusty
• sprawdzenie czy element należy do zbioru
• dołączenie elementu do zbioru
• usunięcie elementu ze zbioru
• usunięcie całego zbioru

operacje złożone

• sumowanie zbiorów
• iloczyn zbiorów
• różnica zbiorów
• itp.

Omówmy kolejno poszczególne operacje.

sprawdzenie czy zbiór pusty

Kiedy nasz zbiór będzie pusty? Gdy dla każdego możliwego elementu zbioru, wartość odpowiadającego mu bitu będzie równa 0. Będzie to wyglądać następująco:

function is_empty ($collection) {

	if ($collection === 0)
		return TRUE;
	else
		return FALSE;

}

Krótkie wyjaśnienie. Jeśli ilość elementów będzie równa 0 otrzymamy wartość logiczną TRUE, w przeciwnym zaś przypadku wartość FALSE. Należy zwrócić uwagę, na uniwersalność tej metody. Niezależnie od rodzaju i możliwej liczebności implementowanego zbioru na integerze, funkcja będzie działać poprawnie.

usunięcie całego zbioru

To sytuacja w której nasz zbiór nie posiada żadnych elementów. Rozwiązanie prezentowane poniżej to wyzerowanie wszystkich bitów, poprzez podstawienie wartości 0. Funkcja również uniewersalna.

function remove (& $collection) {

	$collection = 0;

}

Chyba nie wymaga to dodatkowego komentarza, zatem pójdzmy dalej.

dodanie elementu do zbioru

Musimy znaleźć sposób prostego mapowania cyfry na jej odpowiednik bitowy. Potem pozostaje zsumowanie zbiorów. Popatrzmy na kod:

function add_element ($element,& $collection) {

	$x = 1; // reprezentacja bitowa to 0000000001

	$x = $x << $element; // przesuwamy bity w lewo
	// zatem jeśli elementem będzie 4 to przesuniemy bity
	// w lewo 4 razy uzyskamy
	// reprezentację zbioru jednoelementowego
	// składającego się z cyfry 4
	// 9 8 7 6 5 4 3 2 1 0
	// 0 0 0 0 0 1 0 0 0 0

	$collection = $collection | $x;
	// sumujemy dotychczasowy zbiór z nowym elementem

}

 

usuwanie elementu ze zbioru

Podobnie jak poprzednio, z różnicą na końcu:

function delete_element ($element,& $collection) {

	$x = 1;
	$x = $x << $element;

	$collection = $collection & ~$x;
	// np. dla 4:
	// x  - 0000001000 po negacji 1111101111
	// następnie iloczyn dzięki temu  niezależnie od
	// wartości bitu reprezentującego cyfrę 4 zostanie on
	// wyzerowany.
}

 

sprawdzenie czy element należy do zbioru

Wykorzystanie operatora logicznego AND będzie najlepszym rozwiązaniem. Funkcja powinna zwrócić wartość logiczną TRUE (należy) lub FALSE (nie należy):

function is_belong ($element,$collection) {

	$x = 1;
	$x = $x << $element;

	if ($x === ($collection & $x))
		return TRUE;
	else
		return FALSE;

	// np. dla 4:
	// x  - 0000001000
	// dla zbioru 4,3,2,1 i 0
	// collection - 0000011111
	// jeśli element należy to AND x i collection zwróci nam x 

}

I to by było na tyle, jeśli chodzi o operacje proste. Przejdzmy teraz do tych złożonych. Jak można łatwo zauważyć, operują one na dwóch zbiorach i w wyniku tych operacji (np. sumowania) zwracają nowy.
Zadanie będzie bardzo proste, ogranicza się wyłącznie do użycia pojedyńczych operatorów logicznych.

sumowanie zbiorów

function suma ($first,$second) {

	return $first | $second;
}

 

iloczyn zbiorów

 

function iloczyn ($first,$second) {

	return $first & $second;
}

 

różnica zbiorów

function roznica ($first,$second) {

	return $first & ~$second;
}

I to tyle na temat zbiorów (na przykładzie cyfr). Mam nadzieję, że choć w małym stopniu ułatwiłem Wam zrozumienie zagadnienia
Ps. Niektórzy twierdzą, że inicjalizacja zbioru jest również operacją prostą. Ale myśle, że napisanie funkcji, która pod zmienną podstawia 0 nie sprawi nikomu większego problemu i zostawiam to jako zadanie domowe.