Cześć, dwa pytanka:
- przyjmijmy, że mamy listę jedno i dwukierunkową, przeszukanie której z nich będzie szybsze?
- co oznacza przeszukiwanie z wartownikiem?
z góry dzięki za odpowiedź
Cześć, dwa pytanka:
z góry dzięki za odpowiedź
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