Obecnie programista potrzebujący stosu albo kolejki priorytetowej niestety musi je sobie zaimplementować w samym PHP na bazie zwyczajnej tablicy. O ile proste struktury nietrudno stworzyć za pomocą już istniejących funkcji (np. bierzemy array_unshift() i array_push() i już mamy prostą kolejkę), ale w dalszym ciągu konieczne jest ręczne bawienie się w to. Co więcej, do bardziej zaawansowanych zadań zaczyna szwankować wydajność. Nie dość, że za całość odpowiada kod interpretowany, to jeszcze typ Array pochłania zarówno czas, jak i pamięć na swoje potrzeby (tak naprawdę od strony implementacyjnej jest to tablica z haszowaniem).

Przegląd struktur

Oto lista wszystkich struktur danych, jakie wymienia dokumentacja i/lub zostały zatwierdzone - nie będę dokładnie opisywać, co robi każda ze struktur, ponieważ nie ma za bardzo na to tu miejsca. Jak ktoś wie, to dobrze. Jak nie, a chce zostać zawodowym programistą, powinien nadrobić zaległości.

1. SplDoublyLinkedList - lista dwukierunkowa
2. SplStack - stos
3. SplQueue - kolejka
4. SplHeap - kopiec
5. SplMinHeap - kopiec typu min
6. SplMaxHeap - kopiec typu max
7. SplPriorityQueue - kolejka priorytetowa
8. SplFastArray - implementacja szybkich tablic podobnych do tych z C

Szczególnie interesująca jest ostatnia propozycja. Myślę, że wielu programistów korzystało z prostych, kilkuelementowych tablic, których rozmiar znali już na początku. Uniwersalny typ Array to w tym wypadku wyciąganie kombajnu do koszenia trawnika. SplFastArray charakteryzuje się właśnie stałym, predefiniowanym przez nas rozmiarem oraz dopuszczeniem wyłącznie indeksów numerycznych, co przekłada się zarówno na zajętość pamięci, jak i na wydajność. Testy autorów pokazują, że w zależności od platformy, nowy typ jest od 10 do 30% szybszy od Array.

Przykłady

Poniżej parę przykładów wykorzystania pozostałych struktur danych. Załóżmy, że chcemy stworzyć prosty menedżer zadań. Zadania muszą być wykonywane w kolejności określonej przez ich priorytety. Idealnie nadaje się do tego celu kolejka priorytetowa:

<?php
 
$ts = new SplPriorityQueue;
$ts->insert('zadanie 1', 2);
$ts->insert('zadanie 2', 4);
$ts->insert('zadanie 3', 1);
$ts->insert('zadanie 4', 3);
 
foreach($ts as $task)
{
  echo 'Wykonuję '.$task.'<br/>';
}
?>

Skrypt ten wyprodukuje nam:

Wykonuję zadanie 2
Wykonuję zadanie 4
Wykonuję zadanie 1
Wykonuję zadanie 3

Inny przykład to nierekurencyjne przeszukiwanie drzewa:

<?php
 
/* zakladamy, ze mamy strukture drzewka gdzies zaimplementowana */
$tree = generujMiDrzewko();
 
// tworzymy kolejke wezlow oczekujacych na przetworzenie
$queue = new SplQueue;
$queue->enqueue($tree);
 
while($queue->count() != 0)
{
  // pobieramy nastepny w kolejnosci wezel i go przetwarzamy
  $item = $queue->dequeue();
  zrobCosZWezlem($item);
 
  // wsadzamy dzieci tego wezla do kolejki
  foreach($item as $child)
  {
     $queue->enqueue($child);
  }
}
?>

Złożoność

Wiadomo, że w listach dwukierunkowych, stosach i kolejkach dodawanie oraz usuwanie elementów na początku lub końcu będzie wykonywane w czasie jednostkowym (nawet chwalą się tym w dokumentacji). Nic nie wiadomo o implementacji kopców, a tym samym złożoności operacji kolejek priorytetowych. W najgorszym wypadku możemy spodziewać się czasów O(log n) lub O(n), zależnie od operacji. Jeżeli jednak autorzy pokuszą się o kopce Fibonacciego (taką mam nadzieję, w końcu po coś je wymyślono), wtedy prawie wszystkie operacje będą wykonywane w czasie jednostkowym.

Zakończenie

Goście od SPL-a odwalają kawał dobrej roboty. Ech, gdyby tak jeszcze uporządkowano wreszcie API tablic i ciągów tekstowych, byłbym w siódmym niebie... Struktury danych spadają mi dosłownie z nieba, gdyż potrzebuję ich do nowego OPT. Niestety z powodu konieczności czekania na PHP 5.3 na razie napisałem sobie zamienniki w PHP, które ładowane są, jeżeli interpreter nie zawiera właściwych klas. Oby nie kazali czekać zbyt długo.

UPDATE: ukazało się PHP 5.3-alpha1. Zamiast SplFastArray używane jest SplFixedArray.

Powrót

• Opis struktur danych w dokumentacji
• SplFastArray na blogu Etienne Kneussa

Na Zyxist.com panuje swoboda wyrażania opinii oraz krytyki pod dowolnym adresem. Jedyny warunek: musi być ona kulturalna i rzeczowa. Na chamstwo, prostactwo lub jawne obrażanie kogokolwiek nie ma tu miejsca i takie komentarze są bardzo szybko usuwane. Jeśli zamierzasz polemizować z treścią wpisu, wpierw uważnie ją przeczytaj.