Implementacja digrafu i algorytmu djikstry

Question

https://pastebin.com/MLenRzQ8
Dzieńdoby. Mam problem który nie daje mi spać. Stworzyłem dwie implementacje grafu (statyczny, oparty na macierzy sąsiedztwa i "dynamiczny" oparty na tablicy dynamicznych list zawierających krawędzie) Chodzi mi jedynie o tą druga implementacje bo ta pierwsza do niczego się nie nadaje (pod warunkiem że nie chcemy korzystać z grafów z fillem bliskim 100%), więc nawet na nią nie patrzcie. Zaimplementowałem algorytm djikstry żeby sprawdzić jak sobie to radzi.. i.. dla grafu z 40000 vertexów i +/- 300000 krawędzi uzyskałem 12s... Szybko naprawiłem błąd i zszedłem do 7 sekund i potem jeszcze trochę pogrzebałem (w sumie dodałem w jednym miejscu break xD) i uzyskałem 3.5 sekundy. Wiem że nie jest to genialny wynik więc czy da się ten graf jeszcze jakoś przerobić/ulepszyć by działał lepiej(dodałem komentarze w miejscach w których są bottlenecki)? Tworzyłem go z myślą by łatwo do niego dorabiać algorytmy więc stworzyłem "handler'ery dla wierzchołków iteratory dla krawędzi itp by po prostu przyjemnie się z tego korzystało, uznałem że i tak to wszystko się uprości przy kompilacji z optymalizacją (tak?)) 

Answer 1

Na oko, po prostu słabo wybrałeś struktury danych:

	vector<Dynamic_Graph<vertex_props, edge_props>::Vertex> doSprawdzenia;
	doSprawdzenia.resize(graph.get_vertex_count());

			for (auto j : doSprawdzenia) { //bottleneck ok. 50% czasu
				if (i.get_connection_to_id() == j.get_id()) { //bottleneck ok. 20% czasu
					isin = false;
					break;
				}
			}

To zazwyczaj jest traktowane jako zbiór i robimy na nim typowe operacje na zbiorach, więc powinien być raczej std::set, std::unordered_set lub czymś podobnym przechowującym wierzchołki lub ich IDki (dla wydajności).

Podobnie, nie rozumiem tutaj też list linkowanych i kilku innych struktur.

Projekt samego API grafu też jest dziwny.

DjikstraAlgoritm(graph, graph.get_vertex(3));
...
cout << i << " " << graph.get_vertex(i).get_props().distance << "\t";
int id = graph.get_vertex(i).get_props().last;

Wywołanie funkcji zmienia wewnętrzny stan grafu, tak że każdy wierzchołek zna swoją odległość od wierzchołka 3...? Bardzo dziwnie to wygląda.

Comments

Jutro zaimplementuje std::set i zobaczę jak duży jest wzrost. Przy okazji może stworzę jakąś klasę która będzie odzielna od samego grafu ale będzie kojarzyła komórki z danymi wierzchołkami/krawędziami (na początek wierzchołki bo krawędzie może być ciężko zorganizować.) Wtedy będzie to wyglądało tak: distance(vertex id) (albo distance(uint id)) i klasę distance będę przekazywał w argumencie/zwracał funkcją odzielnie "last" i "distance" Wtedy mógłbym się nawet pozbyć tablicy "data" z grafu bo własności wierzchołków były by poza klasą grafu (ew dodam w definicji preprocesora coś ala use_vertex_data jeżeli chciałbym definiować własności koniecznie w grafie). Co sugerujesz mówiąc że nie rozumiesz list linkowanych? Rozumiem że preferował byś użycie struktur danych z std jak np list tak? Dziękuje za podpowiedzi.

---

Rozumiem że preferował byś użycie struktur danych z std jak np list tak? 

Nie - że w ogóle nie rozumiem idei/nie widzę powodu, żeby zbiór krawędzi węzła był listą linkowaną.

---

Zaimplementowałem to co powiedziałeś ale natrafiłem na problem z set którego ni jak nie wiem jak rozwiązać:
https://pastebin.com/NX2imaKn
chodzi o linijkę 969 i 971 gdzie przez to że dane w set muszą być unikalne w niektórych przypadkach nie wrzuca mi wierzchołka (a muszę go wyjąć bo tak naprawdę zmieniła się jego pozycja w setcie) dlatego mam zły output dla trasy 3->6 (15 zamiast 12) przy inicjacji z tym problemem poradziłem sobie tak że zainicjowałem tablice distance z różnymi wartościami. ale tutaj nie mogę tak zrobić.
Wybrałem listę linkowaną bo tak naprawdę nie mogę znać dokładnej ilości krawędzi wychodzących z danego wierzchołka a taka struktura nie utrudnia żadnych innych operacji (mogę je przeszukiwać sekwencyjnie, rzadko jest potrzeba w inny sposób a sprawdzanie czy w liście coś się znajduje to szybciej niż liniowo nie zrobię,
(ew set mógłbym użyć set (co rozumiem było by lepszym rozwiązaniem? bo szukanie log(n)(z n) a nadal mógłbym sekwencyjnie przeszukiwać krawędzie ale wtedy wolniej bym "bydował" graf może zmienie))

---

chodzi o linijkę 969 i 971 gdzie przez to że dane w set muszą być unikalne w niektórych przypadkach nie wrzuca mi wierzchołka (a muszę go wyjąć bo tak naprawdę zmieniła się jego pozycja w setcie) 

No OK, ale to wciąż kwestia struktur danych. Może być dedykowany priority queue, może być ręcznie napisany z zawsze posortowanym vectorem, może do tego być boczny std::unordered_set ze zbiorem już odwiedzonych wierzchołków, może być std::unordered_map mapujący znaleziony wierzchołek na pozycję w kolejce dla szybkich lookupów... etc.

bo tak naprawdę nie mogę znać dokładnej ilości krawędzi wychodzących z danego wierzchołka

std::vector?

---

yh. Bardzo chciałbym pierw zobaczyć jak będzie to działało z set. O ile rzeczywiście jest to możliwe. Więc prosił bym pana o pomoc. O co chodzi z "zawsze posortowanym wektorem"? że nowe elementy będą wkładane w miejsca w których by się znalazły gdyby  posortować wektor? jeżeli zaimplementuje to jako listę linkowaną to wtedy będę musiał przeszukać O(n) elementów by dodać coś do wektora. (vs O(log(n)) z drzewa binarnego może właśnie zaimplementuje (potem, jak zadziała set(o ile zadziała))) takie drzewko które będzie miało własności podobne do set ale będę mógł wyrzucić niepowtarzalność elementów w drzewie (będę np wkładał zawsze wkładał na lewo jeżeli są równe)
o ile mi wiadomo, o ile nie użyje się reserve w vectorze to ma on bardzo niską wydajność przy ciągłym pushowaniu nowych elementów. a użyć reserve to mogę tylko "na oko" np na podstawie mediany z ilości krawędzi z wierzchołka.

---

jeżeli zaimplementuje to jako listę linkowaną

Ale się uparłeś na te listy.

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode

Robisz zbiór Q i go przeszukujesz w każdej iteracji szukając najbliższego. Może być std::set, std::unordered_set etc.

A w wariancie z priority queue (C++owy std::priority_queue raczej się nie nada tutaj, bo trzeba móc zmieniać priorytet) można użyć gotowy kontener z boosta albo std::vector który zawsze będzie posortowany po priorytecie (znajdując wydajnie miejsce do wstawienia używając std::lower_bound).

---

Nie uparłem się na listę linkowaną.. gdybam sobie o nich. uparłem się na set chociaż nie wiem jak użyć set w tym przypadku. Kolejka jest chyba prostsza od drzewka.
Chociaż implementacja drzewka binarnego z modyfikacjami rozwiązała by wszystkie problemy. prawda? nie chce się narobić. Jak sprawdzałem to z wyszukiwaniem logarytmicznym ten algorytm pędzi jak oszalały.. ale daje złe wyniki xD

---

Hm... zmieniłem to na algorytm z rosnącym priority queue (zamiast malejącego zbioru pozostałych) i dla uproszczenia wyrzuciłem te wszystkie warstwy abstrakcji i przerzuciłem wyniki na zewnątrz grafu - wyszło mi z 6x szybciej (<0.5s vs 3s). Sprawdziłem tez że dostałem też te same wyniki.

https://gist.github.com/adrian17/f3554dbe0c0b65b7ebab37ea5897745a

No i z pewnością da się to jeszcze usprawnić.

---

vector nie traci na wydajności gdy używa się insert(iterator,wartosc)? Czy mogę cię jeszcze prosić o jakiś dobry tutorial do std z C++17 i 20? Bo widzę że przez tą niewiedzę tylko cierpię.

---

vector nie traci na wydajności gdy używa się insert(iterator,wartosc)? 

Czasem tak, ale w niektórych przypadkach jest to pomijalne. Tutaj można to dodatkowo lekko zoptymalizować, bo przypadki zmiany priorytetu (erase+insert) można zastąpić przez std::rotate(), co zaoszczędzi z 10% czasu. Ale AFAIK większość czasu teraz jest spędzona w std::find.

W każdym razie jest i tak to znacznie lepsze od tego, co było robione wcześniej.

Czy mogę cię jeszcze prosić o jakiś dobry tutorial do std z C++17 i 20? Bo widzę że przez tą niewiedzę tylko cierpię.

Wydaje mi się że nie użyłem tu nic z C++20, 17 ani nawet 14. Tylko prostą lambdę z C++11.

 

---

niepotrzebnie dodawałem wersję ogólnie tutorial do bibliteki standardowej przystępnie opisujący wszystkie ważne algorytmy, kontenery, schematy i w jakich sytuacjach sobie radzą.

---

Tutoriala nie znam, ale ogólnie tu jest obszerny reference z którego regularnie korzystam:

https://en.cppreference.com/w/cpp/algorithm

Co do ogólnej wiedzy, pewnie jakaś książka o strukturach danych byłaby dobra... ale za bardzo nie jestem w stanie polecić żadnej.