Są trzy sposoby zachowywania wykres pamięć:trzy sposoby zachowywania wykres w pamięci, zalety i wady
wiem jak napisać wszystkie trzy, ale nie jestem pewien, myślałem ze wszystkich zalet i wad każdego z nich.
Jakie są zalety i wady każdego z tych sposobów przechowywania wykresu w pamięci?
Jednym ze sposobów analizy tych problemów jest złożoność pamięci i czasu (która zależy od sposobu uzyskania dostępu do wykresu).
Przechowywanie węzły jako obiekty ze wskaźnikami do siebie
Przechowywanie matrycę wag krawędzi
W zależności od algorytmu, który zostanie uruchomiony na wykresie i liczby węzłów, należy wybrać odpowiednią reprezentację.
Wierzę, że złożoność czasu dla wyszukiwań w modelu obiektu/wskaźnika to tylko O (n), jeśli przechowujesz te węzły w osobnej tablicy. W przeciwnym razie musiałbyś przejść przez wykres, szukając pożądanego węzła, nie? Przemieszczanie każdego węzła (ale niekoniecznie każdej krawędzi) na dowolnym wykresie nie może być wykonane w O (n), czy może to zrobić? –
Myślę, że twój pierwszy przykład jest trochę niejednoznaczny - węzły jako obiekty i krawędzie jako wskaźniki. Możesz je śledzić, przechowując tylko wskaźnik do jakiegoś węzła głównego, w którym to przypadku dostęp do danego węzła może być nieefektywny (np. Chcesz, aby węzeł 4 - jeśli obiekt węzła nie jest dostarczony, być może będziesz musiał go wyszukać) . W takim przypadku można również stracić fragmenty wykresu, które nie są osiągalne z węzła głównego. Myślę, że tak właśnie jest w przypadku f64 rainbow, kiedy mówi, że złożoność czasu dostępu do danego węzła to O (n).
W przeciwnym razie można również przechowywać tablicę (lub mieszającą) pełną wskaźników do każdego węzła. Pozwala to na dostęp O (1) do danego węzła, ale zwiększa nieco wykorzystanie pamięci. Jeśli n to liczba węzłów, a e to liczba krawędzi, złożoność tego podejścia będzie wynosić O (n + e).
Złożoność przestrzeni dla podejścia macierzowego będzie przebiegać wzdłuż linii O (n^2) (zakładając, że krawędzie są jednokierunkowe). Jeśli twój wykres jest rzadki, będziesz miał wiele pustych komórek w macierzy. Ale jeśli twój wykres jest w pełni połączony (e = n^2), to korzystnie wpływa na pierwsze podejście. Jak mówi RG, możesz również mieć mniejszy brak pamięci podręcznej z tym podejściem, jeśli przydzielisz matrycę jako jedną porcję pamięci, co może przyspieszyć wykonywanie wielu krawędzi wokół wykresu.
Trzecie podejście jest prawdopodobnie najbardziej efektywne pod względem przestrzeni w przypadku większości przypadków - O (e) - ale powoduje, że znalezienie wszystkich krawędzi danego węzła jest zadaniem O (e). Nie mogę wymyślić przypadku, w którym byłoby to bardzo przydatne.
Lista krawędzi jest naturalna dla [algorytmu Kruskala] (https://en.wikipedia.org/wiki/Kruskal's_algorithm) ("dla każdej krawędzi, spójrz w poszukiwaniu związków"). Również Skiena (2nd ed., Strona 157) mówi o listach krawędzi jako podstawowej strukturze danych dla wykresów w swojej bibliotece Combinatorica (która jest * biblioteką ogólnego przeznaczenia * wielu algorytmów). Wspomniał, że jedną z przyczyn tego są ograniczenia narzucone przez model obliczeniowy Mathematica, czyli środowisko, w którym żyje Combinatorica. –
OK, więc jeśli krawędzie nie mają ciężarów, macierz może być tablicą binarną, a używanie operatorów binarnych może sprawić, że wszystko pójdzie naprawdę, bardzo szybko w tym przypadku.
Jeśli wykres jest rzadki, metoda obiekt/wskaźnik wydaje się dużo bardziej wydajna. Trzymanie obiektu/wskaźników w strukturze danych specjalnie w celu nakłonienia ich do jednego kawałka pamięci może również być dobrym planem, lub jakąkolwiek inną metodą uzyskania ich utrzymania razem.
Lista przyległości - po prostu lista połączonych węzłów - wydaje się zdecydowanie najbardziej wydajną pod względem pamięci, ale prawdopodobnie także najwolniejszą.
Odwrócenie skierowanego wykresu jest łatwe z reprezentacją macierzy i łatwe z listą sąsiedztwa, ale nie tak dobrze z reprezentacją obiektu/wskaźnika.
jeszcze kilka rzeczy do rozważenia:
Model matryca nadaje się łatwiej do wykresów z ważonych krawędzi, przechowując wagi w macierzy. Model obiektu/wskaźnika musiałby przechowywać wagi brzegowe w równoległej tablicy, co wymaga synchronizacji z tablicą wskaźnika.
Model obiektu/wskaźnika działa lepiej z ukierunkowanymi wykresami niż grafy nie przekierowane, ponieważ wskaźniki musiałyby być utrzymywane w parach, co może stać się niezsynchronizowane.
Masz na myśli, że wskaźniki powinny być utrzymywane w parach z niekierowanymi wykresami, prawda? Jeśli jest on skierowany, wystarczy dodać wierzchołek do listy sąsiednich wierzchołków, ale jeśli jest on nieukierunkowany, musisz dodać jeden do listy sąsiednich obu wierzchołków? – FrostyStraw
@FrostyStraw Tak, dokładnie. –
Sposób obiekty-i-wskaźniki cierpi z powodu trudności w poszukiwaniu, jak niektórzy zauważyli, ale są całkiem naturalne dla robienia rzeczy jak budowanie wyszukiwania binarnego drzewa, gdzie jest dużo dodatkowej konstrukcji.
Osobiście uwielbiam matryce dopasowania, ponieważ znacznie ułatwiają one rozwiązywanie wszelkiego rodzaju problemów za pomocą narzędzi z teorii grafów algebraicznych. (Kafel mocy macierzy sąsiedztwa podaje na przykład liczbę ścieżek o długości k od wierzchołka i do wierzchołka j. Dodaj macierz tożsamości przed odebraniem mocy kilowej, aby uzyskać liczbę ścieżek o długości < = k. Podejmij pozycję n-1 minor z Laplacian, aby uzyskać liczbę drzew opinających ... I tak dalej.)
Ale wszyscy mówią, że matryce sąsiadujące są drogie! Są tylko w połowie prawe: możesz obejść to za pomocą rzadkich macierzy, gdy wykres ma kilka krawędzi. Rozproszone struktury danych macierzy wykonują dokładnie pracę polegającą na utrzymywaniu listy przyległości, ale wciąż mają pełną gamę standardowych operacji macierzy dostępnych, co daje najlepsze z obu światów.
Istnieje inna opcja: węzły jako obiekty, krawędzie jako obiekty, każda krawędź jest jednocześnie w dwóch podwójnie połączonych listach: lista wszystkich krawędzi wychodzących z tego samego węzła i lista wszystkich krawędzi przechodzących do tego samego węzła.
struct Node {
... node payload ...
Edge *first_in; // All incoming edges
Edge *first_out; // All outgoing edges
};
struct Edge {
... edge payload ...
Node *from, *to;
Edge *prev_in_from, *next_in_from; // dlist of same "from"
Edge *prev_in_to, *next_in_to; // dlist of same "to"
};
Narzut pamięci jest duża (2 wskazówki na węźle i 6 wskaźniki na krawędzi), ale można uzyskać
Struktura może również przedstawiać raczej ogólny wykres: zorientowany multigraph z pętlami (tj. możesz mieć wiele wyraźnych krawędzi pomiędzy tymi samymi dwoma węzłami, w tym wiele odrębnych pętli - krawędzie przechodzące od x do x).
Zobacz na comparison table na stronie wikipedia. Daje dobre zrozumienie, kiedy należy użyć każdej reprezentacji wykresów.
Rozważałbym matrycę tylko wtedy, gdy wykres był bardzo połączony lub bardzo mały. W przypadku rzadko połączonych wykresów, podejście do obiektu/wskaźnika lub listy krawędzi przyniosłoby znacznie lepsze wykorzystanie pamięci. Ciekawi mnie, co oprócz pamięci, którą przeoczyłem. ;) – sarnold
Różnią się również złożonością czasu, macierz to O (1), a pozostałe reprezentacje mogą się znacznie różnić w zależności od tego, czego szukasz. – msw
Pamiętam lekturę artykułu opisującego zalety sprzętowe implementacji wykresu jako matrycy na liście wskaźników. Nie pamiętam wiele z tego, poza tym, że mając do czynienia z ciągłym blokiem pamięci, w dowolnym momencie wiele z twojego zestawu roboczego może być dobrze w pamięci podręcznej L2. Z drugiej strony lista węzłów/wskaźników może być blokowana przez pamięć i prawdopodobnie będzie wymagać pobrania, które nie trafi do pamięci podręcznej. Nie jestem pewien, czy się zgadzam, ale to ciekawa myśl. – nerraga