wtorek, lutego 15, 2011

Przeżycie artystyczne ;-)

Ja wiem, że dla wielu to co napiszę będzie przerażające, lub będzie dowodzić, że postradałem zmysły ;-)

Ale i tak napiszę.

Jak mi jest źle i smutno, albo gdy jestem zdenerwowany to zaczynam przeglądać źródła JDK. Np. klasy związane z kolekcjami.

Dziś by uspokoić skołatane nerwy ;-) zajrzałem do PriorityQueue. Jak dobrze zgadłem jej implementacja bazuje na kopcu.
Tak sobie czytając kod próbowałem znaleźć znajome miejsca i już w jednym z konstruktorów mamy wołanie metody heapify(), która działa ciut inaczej niż się spodziewałem (bo robi to co w Introduction to Algorithms robi BUILD-MAX-HEAP()), ale w końcu dochodzimy do kodu, który stara się przywrócić własności kopca maks, tylko że robi to ciut inaczej niżbym się tego spodziewał ;-)

Ja w swojej implementacji, tego co w ItA, używam rekurencji i mam:

void heapify(int i) {
int l = 2*i+1;
int r = 2*i+2;
int largest;
if (l<heapSize && heap[l]>heap[i]) {
largest = l;
} else {
largest = i;
}
if (r<heapSize && heap[r]>heap[largest]) {
largest = r;
}
if (i!=largest) {
swap(i, largest);
heapify(largest);
}
}


Czyli najpierw sprawdzam czy lewy syn jest większy od ojca, a później czy prawy syn jest większy od tego, który był poprzednio większy. Jeśli największy element jest różny od ojca to zamieniam je miejscami i przywracam właściwości kopca dla tego elementu.
Czyli jak w IaT stoi ;-)

Heretycy z Sun'a zrobili to jednak wbrew Słowu IaT, ale za to zrobili to sprytniej ;-)
[tutaj kod z JDK przerobiony z kopca mini na maks i z ogólnego działania na czymś używającym comparatorów na int'y, i jest to nie heapify z JDK, a odpowiednik mojego, czyli żeby przywrócić właściwości kopca to trzeba by było drania zawołać dla wszystkich od heapSize/2 do 0] :-)

void heapify(int i) {
int half = heapSize >>> 1;
int x = heap[i];
while (i < half) {
int child = (i << 1) + 1;
int c = heap[child];
int right = child + 1;
if (right < heapSize && c<heap[right])
c = heap[child = right];
if (x>=c)
break;
heap[i] = c;
i = child;
}
heap[i] = x;
}


Czyż to nie jest śliczne? :-)

Pozbyli się rekurencji, co niby takie trudne nie jest, ale cały ten kod jest po prostu miły. Nie ma tam ani 1 zbędnej linijki ;-)

A co do heretyzmu Sun'owców piszących kolekcje ;-) to w TreeMap sami się przyznają, że ichnie drzewa czerwono-czarne bazują na tym jak rzecze Introduction to Algorithms ;-)


Podobne postybeta
HeapSort, a MergeSort i QuickSort :-) - od strony "chytrości" ;-)
Koszmarne Garbage Collectory part 2 ;)
Mobile only - rezultaty
Odrobina miłości i serwery działają ;-)
Niecne wykorzystanie refleksji... czyli jak poszukać tekstu w drzewie obiektów? ;-)