Procedura w C usuwająca element z listy jednokierunkowej

Poniżej kod procedury, która usuwa element o wskazanej wartości val z listy jednokierunkowej - element listy jest typu Node - jest to struktura, która zawiera pole int value oraz wskaźnik next na następny element.

Problem w tym, że przy mierzeniu czasu działania tej procedury, zawsze działa ona w dokładnie zerowym czasie, nawet dla 100000 elementów. Mierzenie czasu działa na pewno dobrze (używam funkcji clock()), bo działanie innych procedur jest mierzone poprawnie.

Wydaje się, że usuwanie działa ok, bo jak wyświetlam potem listę, to brakuje właśnie usuniętego elementu. Tyle, że ten czas taki krótki - wiem, że jest liniowy, ale czy to możliwe, by dla 100000 elementów tak krótko trwało to usuwanie? Lista jest posortowana (tworzona metodą insertion sort).

Czy ktoś mógłby mi powiedzieć, czy takie zachowanie jest normalne? Jak dla mnie, czas powinien być liniowy względem długości listy i powinien wynieść co najmniej te kilka milisekund... a tu ciągle 0. Próbowałem powtarzać pomiary np. 1000 razy i wyliczać średnią - zawsze 0.

int delItemOfList(Node **root, int valToDel) {	/* if deleted, returns 0, else returns -1 */
	Node *curr = *root, *toDel = NULL;
	if ((**root).value == valToDel) {									
		toDel = *root;						/* delete current root */
		*root = (**root).next;				  /* new root */
	} else {
		while ((curr -> next -> next != NULL) && (curr -> next -> value != valToDel))  /* seeking */
			curr = curr -> next;
		if (curr -> next -> value == valToDel) {		/* item found */
			toDel = curr -> next;
			curr -> next = curr -> next -> next;
		} else return -1;						/* item not found */
	}
	free(toDel);
	return 0;
}

Tylko rzuciłem okiem na kod, ale wygląda dobrze.
Mam jednak 2 ale:

• ta metoda usuwa zawsze tylko jeden element nawet jeśli szukane wartości powtarzają się w liście! Czy to było zamierzone?
• jakiego zrobiłeś testcase'a? bo jeśli mierzyłeś czas, gdy usuwany element był na początku listy to się nie dziwie, że wychodził ci czas 0, bo wtedy rozmiar listy nie ma znaczenia. Umieść element do usunięcia na końcu listy, albo nawet kilka w rożnych miejscach i uwzględnij poprzednią uwagę.

1. Tak, metoda usuwa jeden element. Wartosci sie nie powtarzaja (sa unikalne, jest to zagwarantowane przy tworzeniu listy), i sa ze znanego mi zakresu, zatem zawsze znajduje żądany element do usuniecia.

2. Co do testu: mierzylem usuwanie jednego elementu z listy o rozmiarach od 10 000 do 100 000 elementow, i zawsze jest czas zero! Co wiecej, powtarzalem pomiar np. 10 czy 100 razy i wyciagalem srednia - i tez 0!

3. Wyglada na to - wierzyc mi sie nie chce, ale tak jest - ze problem rozwiazuje zatrzymanie programu na 1 milisekunde przy kazdym przechodzeniu do nowego elementu listy (instrukcja curr = curr -> next;). Wtedy jest liniowa zlozonosc... Wniosek z tego, ze po prostu procedura bez tego zatrzymania (uzywam funkcji sleep(int iloscMilisekund) z biblioteki windows.h), dziala za szybko... Co o tym sadzicie?

Sądzimy, że czas mierzy się robiąc około 10000 testów, nie 10. A spowalnianie funkcji sleepem to najgłupszy pomysł jaki widziałem na tym forum (bez obrazy)

im większą ilość testów wykonasz tym wynik będzie dokładniejszy najlepiej wykonaj tyle testów na ile pozwala ci maszyna(czy budowa kontenera), czyli najlepiej 0xFFFFFFFF razy

Sądzimy, że czas mierzy się robiąc około 10000 testów, nie 10.

Ciężko to zrobić, bo do każdego pomiaru usuwania elementu muszę utworzyć nową listę z losowego ciągu danych, a tworzenie takowej (samosortująca się) jest O(n^2). Wiem, że możnaby usuwać elementy po kolei, ale wtedy lista skraca się, więc nie wiem jak będzie ze złożonością.

A spowalnianie funkcji sleepem to najgłupszy pomysł jaki widziałem na tym forum

Być może :) , ale zastosowałem to do sprawdzenie po to, by upewnić się, że rzeczywiście złożoność jest liniowa - jest bowiem tyle wywołań sleep(), ile razy przechodzi się do następnego elementu listy.

Sorry, ale jaką inną złożoność mógłby mieć ten algorytm?

W sumie nie rozumiem jaki masz problem!
Przeszkadza ci, że coś robi się za szybko? A czy robi się dobrze?
Równocześnie nie zrozumiałeś o co mi chodziło z testcase'm. Jak tworzysz listę do testowania, to kiedy wsadzasz element, który ma być potem usunięty? Jeśli jako ostatni to jest oczywiste czemu uzyskujesz tak krótkie czasy niezależnie od wielkości, jeśli jak pierwszy to faktycznie dziwne.

Popatrzyłem na twój kod i troszkę zagmatwałeś, tak jest prościej:

int delItemOfList(Node **root, int valToDel)
{
     Node * cell = *root;
     while(cell && cell->value!=valToDel)
           {
           root = &(cell->next);
           cell=cell->next;
           }
     if(cell) // coś znaleziono?
           {
           *root = 0;
           free(cell);
           return 1;
           }
     return 0;
}

Sorry, ale jaką inną złożoność mógłby mieć ten algorytm?

Algorytm sam nie, ale lista bedzie coraz krotsza, a chce zbadac czas usuwania losowo wybranego elementu w posortowanej liscie zalezny od jej dlugosci. Oczywiscie, mozna usuwac elementy po kolei, ale wtedy trzeba rejestrowac, ktory byl usuniety i usuwac go z tablicy, z ktorej losuje element nastepny.

W sumie nie rozumiem jaki masz problem!
Przeszkadza ci, że coś robi się za szybko? A czy robi się dobrze?

Robi się dobrze. Nie przeszkadza mi, że robi sie za szybko - tyle, ze zastanawia mnie, ze robi sie w praktycznie zerowym czasie. A kwestia ta interesuje mnie, bo moim zadaniem jest zbadac dzialanie tego algorytmu, by potwierdzic eksperymentalnie jego O(n) zlozonosc.

Równocześnie nie zrozumiałeś o co mi chodziło z testcase'm. Jak tworzysz listę do testowania, to kiedy wsadzasz element, który ma być potem usunięty? Jeśli jako ostatni to jest oczywiste czemu uzyskujesz tak krótkie czasy niezależnie od wielkości, jeśli jak pierwszy to faktycznie dziwne.

Lista jest tworzona w nastepujacy sposob:

1. generowany jest ciag kolejnych liczb od 1 do n,
2. przestawiana jest kolejnosc tych liczb w ciagu (mieszanie)
   (mamy gwarancje, ze wartosci sa unikalne i sa z danego zakresu)
3. tworzona jest lista samosortujaca sie - elementy sa po kolei brane z wspomnianej tablicy; przesuwamy sie po dotychczas stworzonej liscie i wstawiamy element na wlasciwe miejsce - po prostu metoda Insertion-sort.

Przy okazji: mozesz objasnic Twoj kod? Nie bardzo rozumiem jego dzialanie, zwlaszcza ze nie widze obsluzenia warunku takiego, ze trzeba bedzie ustawic nowy root dla listy, jesli szukany element jest pierwszy.

No i czy mamy pewnosc, ze NULL jest zawsze traktowane jako 0 w warunku?

Simone napisał(a)

...
No i czy mamy pewnosc, ze NULL jest zawsze traktowane jako 0 w warunku?

#define NULL 0

po dodaniu komentarzy:

int delItemOfList(Node **root, int valToDel)
{
     Node * cell = *root; // wskaźnik na bieżącą komórkę
     while(cell && cell->value!=valToDel) /* czy bierząca komórka istnieje
                                                         i czy jest różna od szukanej wartości */
           {
           root = &(cell->next); /* uchwyć nowy korzeń z bieżącej komórki listy */ 
           cell=cell->next;        /* idź do następnej komórki listy  */
           }
     if(cell) // coś znaleziono? jeśli tak to cell!=0
           {
           // haha tu miałem głupawy błąd :)
           *root = cell->next; // popraw bieżący korzeń na następną komórkę lub NULL
           free(cell); // kasuj bieżącą komórkę
           return 1;
           }
     return 0; // nić nie znaleziono
}