Witam,
Mam krótkie pytanie:
Czy przedstawienie grafu za pomocą listy sąsiedztwa będzie wolniejsze/szybsze od macierzy sąsiedztwa? Oba algorytmy maja złożoność O(V+E), ale gdy badam czasy dla tych dwoch algorytmow, lista jest 3-krotnie wolniejsza od macierzy... I nie wiem czy tak powinno wyjść czy też skopałem kod. Dzieki
0
0
Z czysto technicznego punktu widzenia macierz będzie szybsza -> ze względu na cache procesora. Macierz można łyknąć w całości do cache / można robić read-ahead, szczególnie dla BFSa. Jak masz listę sąsiedztwa to każdy węzeł może leżeć w losowym miejscu w pamięci w efekcie szanse na wykorzystanie cache są znikome.
0
Kazda zlozonosc to z zalozenia: O(C * (cokolowiek Ci podali)), gdzie C to jakas stala. To ze cos ma taka sama zlozonosc nie znaczy ze bedzie tak samo szybkie, a jedynie tyle ze bedzie tak samo skalowac czas od czasu (tj. np. dwukrotnie zwiekszenie elementow zwiekszy dwukrotnie czas trwania). Jesli zaleznosc jest stala to wszystko jest ok. Jesli dwukrotne zwiekszenie elementow spowoduje czterokrotne zwiekszenie czasu to masz buga
0
Dzięki, możecie rzucic okiem na załącznik?
Zielone to graf za pomoca listy, niebieski to macierz.
Wyglada na skopane, czy jest to realne ze tak wygladaje te wyresy?
0
Cache daje naprawdę potężnego kopa, wygląda prawdziwie.
1
Dużo zależy od tego ile jest połączeń między wierzchołkami. Jeśli średnia ilość krawędzi wchodzących/ wychodzących z wierzchołka jest mała (np 5) to lepiej użyć list sąsiedztwa. Jeśli jest duża (np połowa maksimum) to lepiej użyć macierzy sąsiedztwa.