Złożoność i szybkość przechodzenia listy wskaźnikowej

Dzień dobry,

jestem w trakcie tworzenia bazy danych opartej o zrównoważone drzewo BST, które w każdym z węźle przechowuje wskaźnik do listy wskaźnikowej przechowującej zmiany wprowadzone w węźle.

Jeżeli użytkownik wprowadza jakieś zmiany w węźle drzewa to tworzona jest lista tych zmian, a jeżeli nie to wskaźnik jest równy zero.

Moje pytanie jest następujące: jaki jest najbardziej efektywny algorytm przechodzenia listy wskaźnikowej? Mający Waszym zdaniem najmniejszą złożoność etc.

Mam tutaj pomysł na trzy:

1. Iteracje do momentu napotkania elementu, który nie zawiera wskaźnika do następnika:
   Ostatni element musi być przetwarzany osobno.

 

Lista *temp = this->lista;

while(temp->nastepny){
	// tutaj przetwarzamy aktualny element.
	temp = temp->nastepny;
}
if(temp->nastepny == 0){
	// tutaj przetwarzamy ostatni element.
}

2. Podobna metoda z tym, że w pętli nieskończonej, która kończy swoje działanie w momencie napotkania zerowego wskaźnika na następnik:

 
Lista *temp = this->lista;

while(temp){
	if(temp->nastepny){
		// tutaj przetwarzamy aktualny element.
		temp = temp->nastepny;
	}
	else{
		// tutaj przetwarzamy ostatni element.
		break;
	}
}

3. Funkcja rekurencyjna, podobna do przechodzenia drzewa BST.

 

void przejdzListe(Lista *temp){
	if(temp){
		// tutaj przetwarzamy aktualny element.
		przejdzListe(temp->nastepny);
	}
}

Wszystko bardzo ładnie mi działa, tylko chciałbym teraz zoptymalizować swój kod.

Pozdrawiam serdecznie
Grzegorz.

Zależy o jaką złożoność Ci chodzi. Bo jeśli o czasową, to wszystkie przykłady mają taką samą - liniową. Jeśli natomiast pamięciową, to pierwsza opcja ma najmniejszą, chociaż ja bym użył pętli do-while zamiast while, żeby się tego ifa pozbyć.

Czasowo nie da się tego przyspieszyć, gdyż jak rozumiem chcesz przetworzyć każdy element listy?

Zmień strukturę tak aby na ten ostatni element był osobny wskaźnik.
Element *the_last_one,*first;
Można nawet się zastanowić czy ma być dołączony do tej listy;

Dziękuję za odpowiedzi.

Tak, chcę przejść każdy element listy szukając np. klucza, którym jest czas modyfikacji pobrany z zegara systemowego. W momencie znalezienia danego elementu pętla ma przestać działać. Rzecz jasna konieczny jest warunek określający kryterium wyszukiwania, o którym nie napisałem, ale to wiadoma rzecz.

Wspomniana pętla do while: tego ifa w pierwszym przypadku dodałem, żeby program przetworzył ostatni element listy gdzie wskaźnik na następny element równy jest zero. Jeśli taki wskaźnik równy jest zero to nie zachodzi warunek while(temp->następny) i ostatni węzeł trzeba przetwarzać osobno. Nie wiem czy do while rozwiążę tutaj problem, ponieważ wykona się raz bez sprawdzania warunku i będzie ok jeżeli lista posiada jeden tylko element ale w przypadku wielu w dalszym ciągu ostatni element nie zostanie sprawdzony.

Tego troszkę nie rozumiem. Mam dodać wskaźnik na ostatni element do struktury opisującej listę? To chyba nie zmniejszy złożoności algorytmu, a wymagać będzie dodatkowych warunków.

Zmień strukturę tak aby na ten ostatni element był osobny wskaźnik.
Element *the_last_one,*first;
Można nawet się zastanowić czy ma być dołączony do tej listy;

Pozdrawiam
Grzegorz

Chodzi o to, że możesz sobie zadeklarować metodę w stylu: bool IsLastOne();

Ja bym zrobił jakiś iterator do tego. Przeciążasz ++ i jest możesz zrobić tak:

do
{
   //...
}while( ++temp );

inkrementacja ostatniego elementu zwróci NULL i będzie dobrze ;)

Ola Nordmann napisał(a):

Chodzi o to, że możesz sobie zadeklarować metodę w stylu: bool IsLastOne();

Ja bym zrobił jakiś iterator do tego. Przeciążasz ++ i jest możesz zrobić tak:

do
{
   //...
}while( ++temp );

inkrementacja ostatniego elementu zwróci NULL i będzie dobrze ;)

O, to jest bardzo dobry pomysł ale jednak trzeba definiować warunki w przeładowanych operatorach :)
Mnie chodzi bardziej o takie rozwiązanie, które przejdzie całą listę od początku do końca i jedynym warunkiem będzie kryterium wyszukiwania.
Wiecie... coś jak przechodzenie drzewa BST tylko może da się to zrobić iteracyjnie.

Czy takie rozwiązanie w ogóle istnieje z wyjątkiem rekurencji w moim pierwszym poście? Bardzo jestem ciekaw tego właśnie.
Nigdzie nie mogę znaleźć takiego rozwiązania dlatego jestem ciekaw czy w ogóle istnieje :D

grzesiek51114 napisał(a):

Tego troszkę nie rozumiem. Mam dodać wskaźnik na ostatni element do struktury opisującej listę? To chyba nie zmniejszy złożoności algorytmu, a wymagać będzie dodatkowych warunków.

Zmień strukturę tak aby na ten ostatni element był osobny wskaźnik.
Element *the_last_one,*first;
Można nawet się zastanowić czy ma być dołączony do tej listy;

Element *the_last_one,*first; // w klasie
for(Element *i=first;i!=the_last_one;i=i->next) { ... }  // wszystkie oprócz ostatniego
if(the_last_one) { ... }// ostatni
A tam gdzie nie chcesz rozróżniać to:
for(Element *i=first;i;i=i->next) { ... }  // wszystkie oprócz ostatniego

Owszem, poprawnie liczonej złożoności nie zmieni w obu przypadkach jest O(n), zaś zamieni dwa warunki na krok na jeden warunek na krok.
Skoro u ciebie ostatni jest osobno obrabiany to podejrzewam że ten ostatni to jest ten ostatnio dodany, więc przy takiej organizacji znacznie przyspieszysz dodawanie nowego z O(n) na O(1).

<quote="973597">

grzesiek51114 napisał(a):

Tego troszkę nie rozumiem. Mam dodać wskaźnik na ostatni element do struktury opisującej listę? To chyba nie zmniejszy złożoności algorytmu, a wymagać będzie dodatkowych warunków.

Zmień strukturę tak aby na ten ostatni element był osobny wskaźnik.
Element *the_last_one,*first;
Można nawet się zastanowić czy ma być dołączony do tej listy;

Element *the_last_one,*first; // w klasie
for(Element *i=first;i!=the_last_one;i=i->next) { ... }  // wszystkie oprócz ostatniego
if(the_last_one) { ... }// ostatni
A tam gdzie nie chcesz rozróżniać to:
for(Element *i=first;i;i=i->next) { ... }  // wszystkie oprócz ostatniego

No rzeczywiście o takiej metodzie nie pomyślałem. Jest to jakieś rozwiązanie - jeden warunek mniej ale pętla i tak pomija ostatni węzeł, który trzeba przetworzyć osobno. :)

Nie wiem... Nie da się chyba inaczej tego zrobić. Zawsze ostatni zostaje poza pętlą.
Hehe chyba, że... zrobię listę cykliczną, która ma w ostatnim elemencie niezerowy wskaźnik temp->nastepny :) Wtedy będzie tylko jeden warunek

 
// Załóżmy, że gdzieś w kodzie jest instrukcja, która ustawia wskaźnik ostatni->nastepny na pierwszy, czyli na this->lista;
// Nie chce mi się tego pisać, bo to nie jest kluczem sprawy.
Lista *temp = this->lista;

while(temp->nastepny){
	if(temp->nastepny != this->lista){
		// Przetwarzanie węzła.		
	}
	else{
		// Przetwarzanie ostatniego.
		break;
	}
	temp = temp->nastepny;
}

Jedyny warunek, w pętli to sprawdzanie czy ostatni->nastepny nie wskazuje na pierwszy.