Szybkośc przeszukiwania list

Cześć, dwa pytanka:

1. przyjmijmy, że mamy listę jedno i dwukierunkową, przeszukanie której z nich będzie szybsze?
2. co oznacza przeszukiwanie z wartownikiem?

z góry dzięki za odpowiedź

1. Zależy z której strony, jak masz 2-kierunkową, to od tyłu możesz przeszukiwać tak samo szybko jak od przodu
2. Dodajesz do listy "sztuczny" element, który upraszcza Ci warunek pętli. Np. jeśli szukasz pierwszej liczby ujemnej, to na koniec listy wstawiasz "wartownika" np. Integer.MIN_VALUE (zawsze znajdziesz ujemną, więc odpada Ci bound checking).

Z teoretycznego punktu widzenia, lista jednokierunkowa powinna być minimalnie szybsza, bo każdy węzeł zajmuje mniej miejsca o ten jeden wskaźnik. Ale to już na prawdę jest mikro optymalizacja, z punktu widzenia algorytmiki kompletnie pomijalna.

@neves: no nie do końca trochę :P szczególnie z tym cache. Zauważ, że zwykle listy są implementowane przez alokowanie na heapie po jednym węźle, czyli pesymistycznie węzły są w zupełnie losowych miejscach heapu. W efekcie cache tu niewiele pomoże. Dlatego zresztą czasami ArrayList jest dużo szybsze od LinkedList, bo tablica to spójny obszar pamięci i można na nim robić read-ahead do cache.

Jeśli chodzi o przeszukiwanie to zależy. Jeśli wiesz że szukany element jest np. w drugiej połówce, to szybciej będzie lecieć od końca, czyli dwukierunkowa będzie szybsza. Ale w sumie nic poza tym.

Przeszukiwanie z wartownikiem sprawdza się głównie w przypadku tablic, dla linked list jest to zwykle default i tym wartownikiem jest node.next == NULL.

Tradycyjnie dla N elementowej tablicy musimy wykonać pesymistycznie 2N porównań (jedno czy indeks == rozmiar a drugie czy element==szukany)

Idea wartownika polega na wstawieniu szukanego elementu na koniec i wówczas nie sprawdzamy już indeks == rozmiar. W najgorszym wypadku znajdziemy tylko naszego wartownika czyli wykonamy indeks == rozmiar na samym końcu jeden raz aby się upewnić czy to nasz wartownik i zwrócimy brak wyniku. Liczba pesymistycznych porównań spada do (N + 1)

        //BEZ WARTOWNIKA
        for (int i = 0; i < tablica.length; i++) {
            if(tablica[i] == szukany){
                return i
            }
        }
        return null
                
                
        //Z WARTOWNIKIEM
        tablica[tablica.length] = szukany;
        for(int i = 0; ; i++){
            if(tablica[i] == szukany){
                if(i == tablica.length){
                    return null;
                }
                return i;
            }
        }
        return null;

Oczywiście ma to sens gdy możemy dodać element do tablicy bez jej realokacji. Tak jak mówiłem w przypadku linked list nie sprawdza się rozmiaru a polega właśnie na tego typu wartowniku jakim jest wskaźnik na NULL na końcu listy.

Tak troszkę odchodząc od głównego wątku, jaka jest różnica między agregowaniem a kompilowaniem tablicy?

Nigdy nie słyszałem terminu kompilowanie tablicy. Kompilowanie to zamiana języka wysokiego poziomu na asembler lub postać binarną

Tak troszkę odchodząc od głównego wątku, jaka jest różnica między agregowaniem a kompilowaniem tablicy? skąd pochodzą te pojęcia? Jedynie kojarzy mi się to z "kompresją", np: https://pl.wikipedia.org/wiki/Kodowanie_Huffmana ale podejrzewam, że to nie o to chodzi :)

@Kamil Żabiński: @Charles_Ray: z uczelni, cyt. Operacja polegająca na obliczeniu tablicy wartości wyrażenia zależnego od wartości poszczególnych elementów dwóch tablic