poniedziałek, grudnia 22, 2008

Jak czytać kod...

Mamy taki kod:
int func(int[] A,int p, int r) {
int x = A[r];
int i=p-1;
for (int j=p; j<r; j++) {
if (A[j]<=x) {
i++;
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
int tmp = A[i+1];
A[i+1] = A[r];
A[r] = tmp;
return i+1;
}

Umiecie patrząc tylko na ten kod, bez użycia kartki i pamięci ;-) stwierdzić co będzie wynikiem jego działania?

Ja nie do końca...

Najpierw rysuję sobie ten kod w głowie:



W rzeczywistości nie tyle sobie wyobrażam rysunek, co na moment "ślepnę" na pewne fragmenty kodu i staram się je analizować bez zbędnych warunków...

Zaczynam od analizy prostszego przypadku, czyli sytuacji gdy w warunku wewnątrz pętli wynikiem jest FALSE, czyli aktualny element fragmentu tablicy jest większy od ostatniego elementu:


Czyli puki A[j]>x to przechodzimy po kolejnych elementach tablicy...
Aż do momentu gdy aktualnie przetwarzany element jest mniejszy bądź równy ostatniemu elementowi tablicy...


Wtedy przesuwamy się o 1 do przodu po naszym dodatkowym indeksie i, który po tym manewrze zacznie wskazywać na 1 element tablicy, a w razie kolejnych przesunięć będzie wskazywał kolejne elementy... i zamieniamy ten wskazywany element z elementem, aktualnie przetwarzanym....

I tu się gubię ;-)

Niby już wiem co robi kod, ale trudno mi zgadnąć co się stanie z tablicą i co będzie opisywać wynik... [czyli indeks i zwiększony o 1].

Nawet analiza jak się będzie zachowywać tablica jest problemem gdy robi się to w głowie... Bo od biedy można operować powiedzmy tablicą 4, no może 5 elementów... do tego dochodzą 2 indeksy... A trzeba zapamiętać nie tylko wartości tych 6-7 liczb, ale jeszcze pozycję w tablicy...

Pomaga mi dopiero wizualizacja:



I wtedy widzę, że wartość zwrócona z tej funkcji to nic innego jak numer indeksu dzielącego tablicę na 2 części, w pierwsze części tablicy znajdują się elementy mniejsze od ostatniego elementu tablicy, a w drugiej większe bądź równe temu elementowi...

OK, to jest metoda partition wykorzystywana w qucik sort.

A teraz kluczowe pytanie ;-)

Macie pomysły, bądź sztuczki które pozwalają na przeczytanie takiego kodu/algorytmu bez babrania się w kartki i inne takie?

Mówiąc inaczej :-)

Ktoś chętny do podzielenia się swoim sposobem analizy kodu? :-)


Ja próbuję od jakiegoś czasu w wolnych chwilach, gdy nie mam innego pomysłu ;-) pisać sobie narzędzie do wizualizacji kodu [o którym już tu kiedyś pisałem].
Jak na razie efekty jego działania nie porażają ;-)



Docelowo chciałbym żeby wyglądało to mniej więcej tak:




Podobne postybeta
Zdradliwa Java i 8 królowych ;-)
HeapSort, a MergeSort i QuickSort :-) - od strony "chytrości" ;-)
Regresja liniowa w Google Docs
Skoro Deep Web jest potrzebny by zapewnić wolność słowa, ale jest wykorzystywany do szerzenia niecnych treści, to może rozwiązaniem jest ograniczenie technologii takiej sieci tak by tylko przekazywała tekst?
Umiejętność programowania pomaga :-)