[Programowanie] Podstawy optymalizacji, priorytety, kolejkowanie

[OldSkull]

Z algorytmami i optymalizacją ma do czynienia każdy programista, również programista układów wbudowanych takich jak mikrokontrolery. Czasami optymalizacja jest jedynie dobrym nawykiem, czasami koniecznością. W poniższym artykule postaram się przybliżyć metody optymalizacji niektórych z nich oraz pokazać, dlaczego warto z niej korzystać.

1. Wstępne założenia

Zanim zajmiemy się za optymalizację należy samemu zdecydować:

- czy optymalizacja jest w ogóle potrzebna: jeżeli problem jest na tyle niewielki, że program działa dobrze bez optymalizaowania wielu jego fragmentów, często sięją pomija aby nie tracić czasu

- pod jakim kątem chcemy optymalizować? Zawsze będzie to wypadkowa szybkości działania, zajmowanej pamięci RAM, rozmiaru kodu wynikowego, odporności na sytuacje wyjątkowe (np. dzielenie przez zero lub błędne dane podane przez użytkownika) oraz poświęconego czasu.

- które części programu są najważniejsze? Optymalizacja niektórych fragmentów da znacznie lepsze efekty dla działania programu od innych, a czas na to potrzebny jest istotny.

2. Priorytety, listy i inne zabawki..

Nawet coś tak podstawowego jak kolejkowanie i odkładanie na stos zadań i danych można zrobic na różne sposoby. Dla przypomnienia: o kolejce mówimy wtedy, kiedy w pierwszej kolejności obsługiwane są dane/rozkazy, które pojawiły się wcześniej (jak kolejka do sklepu). O stosie mówimy wtedy, kiedy w pierwszej kolejności obsługujemy dane/rozkazy, które pojawiły się ostatnio. Wadą kolejki są długie opóźnienia, zaletą, że każdy element zostanie obsłużony. W przypadku stosu najnowsze elementy mają dużą szansę obsłużenia w bardzo krótkim czasie, ale mogą zostać również "zagłodzone", czyli znaleźć się na dole stosu.

Zaletą obu rozwiązań jest stosunkowo prosta implementacja, natomiast można jeszcze stosować wszelkie metody związane z priorytetami zadań. Sytuacja jest bardzo podobna do przerwań w mikrokontrolerach: niektóre mają wyższy priorytet i jeśli pojawi się kilka, to jedne będą obsłużone wcześniej od innych (niezależnie od kolejności pojawiania się!), a wręcz mogą wywłaszczyć inne!

Istnieje kilka podstawowych metod określania priorytetów zadań:

- najkrótsze najpierw: aby nie spowalniać działania systemu działania zajmujące najmniej czasu zostają wykonane wcześniej. Wada: długie zadania mogą nigdy nie zostać wykonane.

- zadania, którym czas ważności się najszybciej skończy najwcześniej - rozwiązanie dobre do systemów czasu rzeczywistego. Niektóre zadania jest sens wykonywać tylko w określonym czasie, potem ich użyteczność spada, czy wręcz jest zerowa (zadania nie udało się wykonać na czas, bądź próbka została stracona/nadpisana). Zaletą jest duża sprawność w obsługiwaniu zadań przed końcem ich ważności, wadą duże możliwe opóźnienia jeśli chodzi o zadania o bardzo długim terminie wykonania.

- zadania o wyższym priorytecie (ustawionym na stale lub zmiennym) najpierw.

- zadania, które ostatnio były obsłużone mają zaniżony priorytet (co powoduje, że zadania o niższym priorytecie są w praktyce obsługiwane rzadziej, ale są)

- skrzyżowanie powyższych, np. zadania najdłużej oczekujące zyskują wyższy priorytet

- inne

Warto się zastanowić w jakich sytuacjach w systemach robotycznych mamy do czynienia z systemami wymagającymi wyboru podejścia innego niż np. kolejka. Odpowiedź: w prawie każdym w którym są czujniki. Wyobraźmy sobie np. robota mobilnego, który musi obsłużyć następujące sygnały:

- kilka czujników obecności innego robota

- cztery czujniki linii

- pomiar napięcia akumulatora

- odbiór komend zdalnego sterowania

- enkodery

- prąd silników

- algorytm ruchu

Najprostsze rozwiązanie polegałoby na sprawdzaniu po kolei wszystkich i wykonywaniu odpowiednich czynności. Ale czy byłoby to dobre? Część z nich jest znacznie bardziej istotna od innych: enkodery po chwili podadzą kolejny impuls, przez co możemy zakłamać pomiar, późne obsłużenie czujnika linii spowoduje wyjechanie z ringu (ale jest mniej wymagające niż enkoder), a przez późne obsłużenie czujnika otoczenia nie trafimy we wrogiego robota. Ale czy jest dobrym pomysłem w takim razie przede wszystkim obsługiwać enkoder (skoro obsługa jest krótka) a resztę w wolnym czasie? A co jeśli enkoder i czujnik linii zaczną zgłaszać się jednocześnie i przez to nie zobaczymy nic innego? W wielu przypadkach wystarczy tylko dobrze przemyśleć dowolne rozwiązanie i zastosować lepszy mikrokontroler, aby wszystko było obsłużone w odpowiednim czasie.

Natomiast jeśli system się rozbudowuje (np. robimy rój, albo mamy system rozproszony lub po prostu bardzo złożony) musimy wybrać odpowiednie rozwiązanie. Każdy sam musi zdecydować co dla niego jest najważniejsze, ja postaram się tylko przedstawić kilka sposobów dla każdego rozwiązanie.

3. Kolejka i stos

Najprostsze, czyli kolejka (FIFO - First In First Out) oraz stos można zrobić na kilka sposobów:

- stały rozmiar bufora. Załóżmy, że odbieramy pakiety danych. Możemy otrzymywać dane o różnych rozmiarach i przechowywać kilka pakietów. Oznacza to, że musimy zarezerwować:

NxM

obszaru danych, gdzie N - ilość pakietów, które chcemy móc przechowywać, M - maksymalny rozmiar pakietu.

Problem się pojawia w sytuacji, kiedy przez dłuższy czas nie możemy obsługiwać pakietów i możemy przekroczyć bufor. Oprócz tego marnujemy sporo pamięci w sytuacji, kiedy przechowujemy niewielką liczbę pakietów. Zaletą jest natomiast niewielki nakład czasu potrzebny na obsługę tejże pamięci przy pobieraniu danych z końców oraz odczycie wybranego elementu. Niestety problem się pojawia przy usuwaniu elementu ze środka - w takim przypadku trzeba przepisać sporą część bufora (średnio 1/4 liczby wpisanych rekordów, lub 1/2 w zależności od algorytmu).

- bufor dynamiczny oparty o listę dwukierunkową. Dla nieobeznanych zamieszczam schemat struktury pojedynczej komórki bufora:

struct
{
void* prev;
void* next;
zdefiniowany_typ buffer; lub void* buffer; (komentarz poniżej)
}

Taki bufor zawiera wskaźnik na poprzedni element, wskaźnik na następny oraz właściwą komórkę pamięci (lub wskaźnik do niej o czym za chwilę). Oprócz tego w każdej chwili należy przechowywać wskaźniki na element początkowy i końcowy (tzw. head i tail). Ogromną zaletą jest niewielki zajęty obszar pamięci (nie istnieją pola puste, trzeba dodać dwa wskaźniki w każdej komórce, których rozmiar przy dużych komórkach jest pomijalny). Można również łatwo usunąć element ze środka (wystarczy sąsiadom zmienić wskaźniki prev i next). Niestety dodawanie kolejnych elementów (tak samo usuwanie) jest czasochłonne (deklarujemy nową pamięć przy każdej operacji a nie tylko raz, zwalanianie też jest komendą dotyczącą pamięci), tak samo dostanie się do elementu o określnym położeniu w buforze. Innymi słowy jest to metoda optymalna pod względem wykorzystania pamięci (dla dużych typów buforów), ale słaba pod względem szybkości.

Niektórzy zapewne zastanawiają się co daje wskaźnik w buforze. Otóż pozwala na:

*stosowanie zmiennego rozmiaru komórek pamięci (np. dla różnych rozmiarów komunikatów)

*stosowanie różnych typów zmiennych (np. struktury z elementem opisującym typ struktury, oraz dowolną resztą zawartości)

*stosowanie wskaźników do funkcji, które można wykonywać (mało osób o tym wie, ale wskaźnik do funkcji można przekazywać jako wartość i taką funkcję można nawet wywołać)

Warto przy okazji nadmienić, że często korzystanie z funkcji służących do alokacji pamięci (np. operatory new i delete) może sprawiać problemy z wyciekiem pamięci oraz jej fragmentacją, dlatego trzeba być szczególnie ostrożnym. Szczególnie, że nie wykorzystamy programów przeznaczonych specjalnie do wykrywania takich sytuacji.

- kolejna metoda jest nieco sprytniejsza. Otóż jest ona modyfikacją powyższej, ale jest wyposażona w licznik oraz dynamicznie zmienną tablicę. Jak działa? Zakładamy pewne przedziały bezpieczeństwa jeśli chodzi o możliwą marnowaną pamięć oraz liczbę alokacji i dealokacji pamięci. Najprostsza metoda zakłada, że jeśli zapełnimy cały bufor, zwiększamy jego rozmiar dwukrotnie. Natomiast jeśli zapełnienie spadnie poniżej 25% zmniejszamy go dwukrotnie. W ten sposób oscylujemy między 25 a 100% zapełnienia bufora (czyli marnujemy trochę pamięci), ale zarazem oszczędzamy sporo czasu na rezerwowaniu pamięci. Możemy oczywiście powyższe parametry zmodyfikować, np. zwiększać o połowę i zmniejszać przy 50% o 33%, ale są to tylko szczegóły. Wadą metody jest to, że przy dużej liczbie elementów, dużo pamięci się marnuje, a przy małej zysk jest niewielki (podane granice są często przekraczane). Niestety przy tej metodzie nie unikniemy łatwo przepisywania danych przy powiększaniu, ale warto pamiętać, że nawet jeśli każdorazowo tworzymy nową tablicę a starą usuwamy, to np. dla 16 elementów musimy wykonać liczbę zapisów równą:

16 + (2+4+8+16)

(pierwsze 16 związane z żądaniami zapisu 16 elementów)

Jak można zauważyć dla dużej liczby N wpisów, wartość wyniesie 3N. Wynik nie wygląda zbyt dobrze, ale gdybyśmy stosowali stały rozmiar i przy każdym przekroczeniu byśmy zwiększali rozmiar o 1, a przy pobraniu zmniejszali o 1 (i przepisywali całość), to powiększenie N razy wiązałoby się z (N^2)/2 operacjami, co jest znacznie gorszą wartością.

Modyfikacją metody jest zliczanie wolnego obszaru i po zapełnieniu zwiększanie o stałą wartość, np. 10, oraz zwalniania o 10 przy 20 wolnych elementach (wartości przykładowe). W takiej sytuacji zysk czasowy jest cały czas stały i proporcjonalny do średniej traconej pamięci, która w podanym przykładzie wynosi 10.

Metoda ta jest znakomita dla stosów (łatwo się dodaje u góry), gorsza dla kolejek (działa jak skrzyżowanie stałego bufora i listy dwukierunkowej, ale można korzystać z indeksów head i tail) i zupełnie kiepska dla przypadku usuwania ze środka (w praktyce trzeba by przepisać całą pamięć powyżej albo co najmniej jej części). Jest również szybka jeśli chodzi o dostęp do konkretnego elementu z kolei.

W każdej wymienionej metodzie opisywałem również operacje:

- usunięcia

- sprawdzenia ze środka

Obie są ważne dla list innych niż kolejka i stos: usunięcie i dodanie wartości są w praktyce równie wymagające. Za każdym razem, kiedy pojawi się nowe zadanie, będzie ono wstawiane w środku listy! Tym samym obciążenie obliczeniowe przy korzystaniu z przepisywania buforów będzie zbyt duże. Podobnie przesunięcie przy zmianie priorytetu (aczkolwiek w przypadku listy dwukierunkowej trzeba jedynie zmienić wartości wskaźników). Równocześnie ważne jest sprawdzanie wartości ze środka, ponieważ nie wiemy, w którym miejscu powinniśmy wpiąć nowy element - musimy sprawdzić priorytety już obecnych - co jest praktycznie tożsame z problemem sortowania. I co prawda zawsze musimy się dostać do elementów w środku określoną liczbę razy, to w przypadku listy jest to bardzo czasochłonne dla każdego elementu. Co to oznacza?

Wyobraźmy sobie, że wchodzi nam N zadań, a następnie wszystkie są wykonywane (podejście naiwne, ale dla uproszczenia zakładamy najgorsze scenariusze dla powyższych metod, prawidłowo trzeba by zrobić symulację z długimi szeregami losowego dodawania i odejmowania):

- dla stałej tablicy (przepisywanej i tworzonej na nowo) wpisanie N wartości to (N^2)/2 operacji (zakładam każdorazowe przepisanie wszystkiego przez wstawienie w środku) oraz N*log2(N) operacji porównań i sprawdzenia wartości oraz 0 operacji przechodzenia po tablicy. Oraz (N^2)/2 przy usuwaniu. Czyli N^2+Nlog2(N)

- bufor dynamiczny: wpisanie N wartości to N operacji (przypisanie wektorów pomijam, gdyż przepisanie dużej struktury trwa znacznie dłużej), tyle samo usuwanie, ale przechodzenie po tablicy w poszukiwaniu środków i samo porównywanie to ((N^2)/2)*log2(N). Czyli 2N+((N^2)/2)*log2(N). Jest ot niestety, ale bardzo zły wynik. Nawet jeżeli uda się 1000x skrócić czas przeskakiwania przez wskaźniki po elementach, to potęgowanie i iloczyn z logarytmem powodują, że tracimy potworne ilości czasu. Innymi słowy: metoda mimo pozornej dobrej jakości, jest w praktyce mało wydajna

- metoda z podwajaniem bufora. Z racji wpisywania potrzebujemy 3N*(N/2) operacji(wliczone przepisywanie), usuwanie to 3N, oprócz tego na porównania N*log2(N). Czyli 1.5*N^2+Nlog2(N)+3N - więcej niż w pierwszej metodzie

A co jeśli od razu nie sortujemy, może się wydawać, że całość może działać gorzej?

- metoda ze stałą tablicą. Wpisujemy normalnie (czyli N^2)(zakładamy, że nie wiem ile wynosi N i tablicę trzeba na okrągło przepisywać i poszerzać), a wybór największego priorytetu dokonujemy każdorazowo, co nas kosztuje N sprawdzeń wartości (i niestety (N^2) przepisywania). Czyli 2*N^2+N

- bufor: wpisanie kosztuje N operacji, usunięcie N, poszukanie najwyższego - niestety nie N, bo trzeba to wykonać max N razy. Czyli (N^2)/2. Lepszy wynik, ale najwięcej zyskujemy na tym, że nie musimy przepisywać żadnego elementu, co skraca nam czas zapisu proporcjonalnie do rozmiaru rekordu!

- metoda z podwajanym buforem. Wpisanie to 3N, usuwanie niestety wymaga przepisywania (i zmiany rozmiaru) czyli 3N+(N^2)/2, wybór to N. Czyli 7N+(N^2)/2. Wygląda nieźle? Niestety, ale jest to wynik tylko minimalnie lepszy niż w podstawowej metodzie (i niekoniecznie lepszy niż w liście dwukierunkowej ze względu na częste przepisywanie). W optymalizacji każda szybkość narastania złożoności N^2 lub szybsza jest uznawana za niewystarczającą (bo jeśli na mikrokontrolerze mały problem o złożoności N będzie liczony 1s, to na 1000x szybszym komputerze 1000N problem będzie liczony już 1000s!). W powyższych widać niestety, że zmiana nie wprowadzi nam rewolucji, ale kilkukrotny zysk można uzyskać.

Jak widać bufor dynamiczny sprawdza się dobrze przy korzystaniu z priorytetyzowanych zadań, ponieważ daje najmniejsze obciążenie (chociaż bez szaleństw), jest szybki (mimo iż przeskakiwanie po wskaźniakch na takie nie wygląda) i wydajny pod względem pamięci (dla większych elementów), ale przeszukiwanie bufora zajmuje dużo czasu. Mimo to szczerze polecam zrozumieć ideę listy dwukierunkowej, a nawet drzewa, bo warto 🙂 Natomiast do kolejki i stosu warto przemyśleć inne metody.

4. Listy zadań

Tutaj musimy rozdzielić już wewnątrz programu: czy mamy stałą, niezmienną listę możliwych zadań, czy może lista jest dynamiczna bądź nieznana. W pierwszym przypadku mamy generalnie dwa rozwiązania:

- zadania ważniejsze muszą być wykonane wszystkie, zanim zaczniemy wykonywać kolejne. Obrazuje to poniższy pseudokod:

while(1)
{
if(licznik1)
{
zadanie1;
licznik1--;
}
else if(licznik2)
{
zadanie2;
licznik2--;
}
else if(licznik3)
{
zadanie3;
licznik3--;
}
...
}

kolejne zadania nie zaczną w ogóle być wykonywane, jeżeli pierwsze nie zostanie obsłużone w całości (czyli np. wszystkie pomiary, następnie cała komunikacja itd).

- zadania ważniejsze obrabiają jedną porcję własnych danych, wykonują jedną iterację, następnie kolejne:

while(1)
{
if(licznik1)
{
zadanie1;
licznik1--;
}
if(licznik2)
{
zadanie2;
licznik2--;
}
if(licznik3)
{
zadanie3;
licznik3--;
}
...
}

różnica w kodzie niewielka, w działaniu ogromna. W tym przypadku każde zadanie będzie wykonane, jedynie ważniejsze nieco wcześniej. Można nawet dla nich zrobić modyfikację:

while(1)
{
if(licznik1)
{
do
{
	zadanie1;
	licznik1--;
}
while(licznik1>licznik1Granica)
}
if(licznik2)
{
zadanie2;
licznik2--;
}
...
}

przez co ważniejsze zadanie nie przekroczy swoich wartości krytycznych, ale poza niebezpiecznymi momentami, nie będzie blokować innych.

Dodanie do powyższych przerwań powoduje, że mają one priorytet nadrzędny. W efekcie możemy mieć zbiór "aplikacji" wykonywanych równorzędnie (wersja z if)bądź z priorytetami (wersja else if), w której mogą się pojawić nadrzędne żądania. Gdzie tutaj miejsce na zmienne stosy, kolejki itd.? Otóż wyobraźcie sobie system, w którym poszczególne peryferia dają informacje o zdarzeniach poprzez przerwanie (mogą to być moduły komunikacyjne, przetworniki ADC z buforem, czy nawet kamery z czujnikiem ruchu). W przerwaniu można dane żądanie obsłużyć od razu, ale w takiej sytuacji blokujemy kolejne wywołania). Skutkiem tego może być tracenie informacji o kolejnych żądaniach. Innym rozwiązaniem jest zapis w buforze informacji o żądaniu oraz skopiowanie do bufora danych żądania (do obróbki). W takim wypadku poszczególne żądania wykonujemy w pętli głównej wg. wybranej metody, a ich dane kolejkujemy (możemy też im nadawać priorytety, np. czujnik CO2 może wysyłać zlecenia zapisania pomiaru na dysk, ale może też wysłać alarm o wysokim poziomie stężenia).

W efekcie otrzymujemy dwie warstwy: warstwę żądań, która może mieć dowolną budowę (np. FIFO, priorytety albo kolejno), oraz warstwę danych dla tych żądań, która może być dowolną kolejką, stosem, listą priorytetów itd.

5. Skutki niekorzystania z optymalizacji

Warto zwrócić uwagę na to, że przy dużej liczbie żądań optymalizacja zużycia pamięci oraz czasu okazuje się kluczowa - zasobożerne zadania należy optymalizować, aby móc je efektywnie obsługiwać. Może się okazać, że w różnych okresach działania różne grupy będą potrzebować dużych ilości pamięci, przez co przydzielenie im pamięci na stałe okazuje się złym rozwiązaniem. Równocześnie wolne obsługiwanie zadań może spowodować:

- upłynięcie czasu, w którym sensowne jest wykorzystanie np. danych pomiarów

- w czasie obsługi zadań mogą się pojawiać kolejne zlecenia, co może skutkować wydłużaniem się kolejki w nieskończoność (aż do limitu pamięci), oraz:

- bardzo duże opóźnienia w obsłudze

- tracenie zadań i danych, których nie uda się zapamiętać celem obsługi

6. Przykładowa implementacja najważniejszych funkcji listy dwukierunkowej

Na koniec przedstawiam implementację w języku C listy dwukierunkowej.

Dfinicja struktury:

typedef struct
{
void* prev;
void* next;
zdefioniowany_typ buffer;
}BiDirListStruct;

BiDirListStruct* first = NULL;
BiDirListStruct* last = NULL;
BiDirListStruct* current = NULL;
BiDirListStruct* prev_temp = NULL;
BiDirListStruct* next_temp = NULL;

Wskaźniki poniżej struktury są wykorzystywane do operacji na buforze. Aby tworzyć obiekty skorzystajmy z funkcji:

- enqueue - dodania do kolejki

- dequeue - usunięcia z kolejki

- push - dodanie do stosu, równoważne enqueue

- pop - usunięcie ze stosu

- insert - wstawienie nowego elementu w wybranym miejscu z kolei (wybranym wskaźnikiem, wybrane miejsce, czy przed czy za)

- new - utworzenie nowego elementu (bez wstawienia)

- delete - usunięcie elementu o konkretnym wskaźniku

- cut - wycięcie elementu z bufora

Funkcje te zamieszczam poniżej:

BiDirListStruct* BiDirNew(void)
{
return (BiDirListStruct*) malloc (sizeof(BiDirListStruct));
}

BiDirListStruct* BiDirCut(BiDirListStruct* dst)
{
if((BiDirListStruct*)(dst->next))(BiDirListStruct*)(dst->next) ->prev = (dst->prev);
if((BiDirListStruct*)(dst->prev))(BiDirListStruct*)(dst->prev) ->prev = (dst->next);
return dst;	
}

void BiDirDelete(BiDirListStruct* dst)
{
BiDirCut(dst);
free(dst);
}

void BiDirInsert(BiDirListStruct* src, BiDirListStruct* dst*, bool next)
{
if(next)
{
	dst->next = (void*)src;
	src->prev = (void*)dst;
}
else
{
	dst->prev = (void*)src;
	src->next = (void*)dst;
}
}

void BiDirReinitLast(void)
{
if(last == NULL)	last = first;
while(last->next != NULL) last = (BiDirListStruct*)(last->next);//idziemy do ogona
}

void BiDirEnqueue(BiDirListStruct* src)
{
if(last==NULL)
{
	if(first == NULL)	//bufor pusty
	{
		first = last = src;
		src->prev = NULL;
	}
	else	//bufor istnieje, ale ogon ma urwany
	{
		BiDirReinitLast();
	}	
}
last->next = (void*)src;
src->prev = (void*)last;
}

void BiDirDequeue(void)
{
BiDirListStruct* new_first = (BiDirListStruct*)(first->next);
new_first->prev = NULL;
BiDirDelete(first);
first = new_first;
}

void BiDirPush(BiDirListStruct* src)
{
BiDirEnqueue(src);
}

void BiDirPop(void)
{
BiDirListStruct* new_last = (BiDirListStruct*)(last->prev);
new_last->next = NULL;
BiDirDelete(last);
last = new_last;
}

Jak widać są one zabazpieczone przed dostępem przez wskaźnik NULL.

Ważne są również funkcje do pobierania danych:

- get_element - pobranie wskaźnika do wybranego elementu

- get_first - pobranie wskaźnika do pierwszego

- get_last - pobranie wskaxnika do ostatniego

Zamieszczone poniżej:

BiDirListStruct* BiDirGetElement(uint index)
{
current = first;
for(uint i=0; i<index; i++)
{
	if(current == NULL) return NULL;
	current = (BiDirListStruct* )(current->next);
}
return current;
}

BiDirListStruct* BiDirGetFirst(void)
{
return first;
}

BiDirListStruct* BiDirGetLast(void)
{
return last;
}

Korzystając z tych funkcji można tworzyć nowe, kolejne, taki psosób pisania kodu daje ogromną elastyczność i równocześnie optymalizuje rozmiar kodu wynikowego. Przykładowo można napisać funkcje przenoszące element z miejsca w buforze na inne:

void BiDirMove(uint src_index, uint dst_index)
{
BiDirInsert((BiDirCut(BiDirGetElement(src_index))), BiDirGetElement(dst_index), true);
}

void BiDirShift(BiDirListStruct* dst, bool dir_next)
{
if(dir_next)
{
	current = (BiDirListStruct*)(dst->next);
	(BiDirListStruct*)(dst->prev)->next = (void*)current;
	(BiDirListStruct*)(current->next)->prev = (void*)dst;
	dst->next = (void*)current;
	current->prev = (void*)dst;
}
else
{
	current = (BiDirListStruct*)(dst->prev);
	(BiDirListStruct*)(dst->next)->prev = (void*)current;
	(BiDirListStruct*)(current->prev)->next = (void*)dst;
	dst->prev = (void*)current;
	current->next = (void*)dst;		
}
}

Oraz wiele kolejnych funkcji ściśle związanych z wybraną metodą. Warto nawet czysto treningowo napisać program wykorzystujący w takimstopniu wskaźniki, gdyż są one bardzo wymagające pod względem uwagi i śledzenia kodu, a zarazem często wykorzystywane. Co więcej, warto podobną metodologię (piszemy funkcje uniwersalne, które =mogą być używane w wielu miejscach programu) warto stosować jak najczęściej, gdyż w trakcie wpadamy na kolejne pomysły dotyczące programu, a sam kod można jeszcez nie raz wykorzystać, co oszczędza nam w przyszłości sporo czasu.

Z racji iż możliwości są ogromne, a opisać wszystko dość krótko ciężko, proszę o zadawanie pytań dotyczących niezrozumiałych fragmentów kodu. Podobnie jeśl ichodzi o same wspomniane tematy - gdyż każdy z nich to temat-rzeka. Równocześnie przepraszam za popełnione błędy, gdyż nikt nie jest nieomylny.

[BlackJack]

Hm.. ciekawy art. ale napisany dla średnio zaawansowanych programistów. Początkujący pewnie zagubi się na samym początku. Dla mnie jako programisty poniekąd bo kończyłem LI (Liceum Informatyczne z programowania) i miałem z tym i owym styczność, ciekawe.

Dobrze byłoby graficznie przedstawić jak funkcjonuje stos, kolejka, bufor, bufor pierścieniowy dla początkujących.

[mog123]

zabrakło typowych optymalizacji kodu wg mnie. Typu podpinanie zmiennych pod rejestr by zaoszczedzić na instrukcjach itp. Wstawki assemblerowe też by się przydało opisać. ale ogólnie to wygląda ok

[OldSkull]

BlackJack, nie chciałem się niepotrzebnie powtarzać z łatwo dostępnymi źródłami, ponieważ jeśli wpiszesz w wyszukiwarkę "wiki stos" albo "wiki kolejka", to znajdzie z łatwością opis. Założyłem, że czytelnik będzie posiadał pewną wiedzę, albo łatwo ją samemu w krótkim czasie zdobędzie.

mog123, temat rzeka. Jeśli bym zaczął opisywać podpinanie pod rejestr, to dalej bym musiał opisać optymalizację pod kątem procesora itd. Ogólnie z tego można by napisać oddzielny artykuł, pewnie równie długi jak ten albo i dłuższy. Natomiast jeśli ktoś czuje, że któryś z tych tematów go interesuje, proszę dać znać, spróbuję go jeszcze w tym temacie przybliżyć.

[Polecacz 101]

Produkcja i montaż PCB - wybierz sprawdzone PCBWay!
   • Darmowe płytki dla studentów i projektów non-profit
   • Tylko 5$ za 10 prototypów PCB w 24 godziny
   • Usługa projektowania PCB na zlecenie
   • Montaż PCB od 30$ + bezpłatna dostawa i szablony
   • Darmowe narzędzie do podglądu plików Gerber
Zobacz również » Film z fabryki PCBWay

[BlackJack]

Temat optymalizacji, to nie tyle rzeka, co cały ocean, i można go rozpatrywać to milionem katów. Na pewno ciekawe są wskaźniki, bo wtedy operujemy bezpośrednio na adresach do pamięci, ale bardzo ważną rzeczą jest też pokazanie jak powinno się budować strukturę programu aby była ona optymalna. Samo przyśpieszenie jakiegoś tam procesu nie zawsze dużo daje, bo często zauważam że szczególnie młodzi programiści, dużo tracą, na złej organizacji całego programu, a Delaye to już wręcz grzech pierworodny, gdzie po zoptymalizowanym często sporym kosztem kombinowania w fragmencie kodu, parę linijek dalej mam sprawdzanie przycisku i chlas wstawione Delayem opóźnienie 10-20ms, które i tak zaprzepaszcza całą optymalizacje bo zatrzymuje praktycznie procesor w martwym punkcie.

[Elvis]

To co kolega OldSkull opisuje nie powinno być nazywane optymalizacją, ale raczej podstawami algorytmiki. Każdy dobry podręcznik opisuje podstawowe struktury danych i algorytmy działania na nich.

Zainteresowanym polecam: http://ksiegarnia.pwn.pl/produkt/155839/wprowadzenie-do-algorytmow.html