• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Implementacja digrafu i algorytmu djikstry

VPS Starter Arubacloud
+1 głos
284 wizyt
pytanie zadane 11 sierpnia 2019 w C i C++ przez Maciej Złotorowicz Gaduła (4,230 p.)

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?)) 

1 odpowiedź

0 głosów
odpowiedź 11 sierpnia 2019 przez adrian17 Ekspert (344,100 p.)
wybrane 13 sierpnia 2019 przez Maciej Złotorowicz
 
Najlepsza

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.

komentarz 13 sierpnia 2019 przez adrian17 Ekspert (344,100 p.)
edycja 13 sierpnia 2019 przez adrian17
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ć.
komentarz 13 sierpnia 2019 przez Maciej Złotorowicz Gaduła (4,230 p.)
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ę.
komentarz 13 sierpnia 2019 przez adrian17 Ekspert (344,100 p.)

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.

 

komentarz 13 sierpnia 2019 przez Maciej Złotorowicz Gaduła (4,230 p.)
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ą.
komentarz 13 sierpnia 2019 przez adrian17 Ekspert (344,100 p.)

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.

Podobne pytania

0 głosów
0 odpowiedzi 276 wizyt
pytanie zadane 8 stycznia 2021 w Algorytmy przez SmaczySchabowy Początkujący (270 p.)
0 głosów
1 odpowiedź 313 wizyt
pytanie zadane 14 lutego 2018 w C i C++ przez Kurczak Użytkownik (940 p.)
0 głosów
0 odpowiedzi 295 wizyt
pytanie zadane 12 stycznia 2018 w C i C++ przez marcin_kub Obywatel (1,420 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...