templates vs laufzeit
-
hallo,
ich wollte mal wissen ob sich die verwendung von templates stark auf die laufzeit auswirkt?
als kleines beispiel: ich habe einen graphen (adjanzenzlisten) mit 10^6 kanten und 10^6 knoten und lasse darauf algorithmen laufen. knoten und kanten sind bei template objekte, da sie noch diverse daten speicher können sollen. die frage ist halt nur ob eine feste implementierung des graphen, wo man die typen der daten schon kennt, in der laufzeit schneller läuft.
danke schonmal im voraus
-
hängt von der alternative ab. wenn die knoten und nutzdaten recht schlank sind und die nutzdaten drin mit new allkoiert und über void* angefaßt werden, ist die templateversion hundertmal schneller. sind in den nutzdaten teure sachen, sagen wir mal fünf strings, ein vector<bool> und drei bis vier verkettete listen, daann ist es nicht mehr feststellbar.
-
was bedeutet über void* anfassen?
-
FreakyBKA schrieb:
was bedeutet über void* anfassen?
class Knoten{void* nutzdaten;...dieser stil war in c üblich. wenn man dich in c++ dabei erwischt, gibts haue. aber die basisklassenzeigerversion von c++ ist hier nur eine verschlimmbesserung. deshalb habe ich sie karikiert, indem ich ein paar jahrzehnte in der zeit zurückging.
-
meine knoten bestehen aus einem array mit zeigern auf die ein- und ausgehenden kanten und dann hab ich noch 1 integer, 1 bool und die template variable, aber alles nicht als zeiger. die kanten bestehen aus zwei zeigern jeweils auf anfangs und endknoten und einer template variable sowie 1 bool variable.
-
FreakyBKA schrieb:
meine knoten bestehen aus einem array mit zeigern auf die ein- und ausgehenden kanten und dann hab ich noch 1 integer, 1 bool und die template variable, aber alles nicht als zeiger. die kanten bestehen aus zwei zeigern jeweils auf anfangs und endknoten und einer template variable sowie 1 bool variable.
oh, da hab ich das wort "adjanzenzlisten" ganz falsch interpretiert. ich dachte an adjazenzmatrizen und schlanken knoten.
ich denke, bei dir bringen die templates keinen spürbaren performancevorteil.
nimm sie aber trotzdem, denn sie drücken das geschehen einfach gut aus und der code wird besser verständlich.
-
bei 10^6 knoten sind adjazenzmatrizen nicht handhabbar, viel zu speicherintensiv, dass wären ja 10^12 (1 billion) einträge.
-
FreakyBKA schrieb:
bei 10^6 knoten sind adjazenzmatrizen nicht handhabbar, viel zu speicherintensiv, dass wären ja 10^12 (1 billion) einträge.
Kommt drauf an, wie dicht sie besetzt sind. es gibt viele Sparse-Matrix-Implementationen.
-
Schau dir mal boost::graph an, evtl. ist das ja das richtige für dich.
Ansonsten ist das auch recht schnell selberimplementiert.
-
knivil schrieb:
FreakyBKA schrieb:
bei 10^6 knoten sind adjazenzmatrizen nicht handhabbar, viel zu speicherintensiv, dass wären ja 10^12 (1 billion) einträge.
Kommt drauf an, wie dicht sie besetzt sind. es gibt viele Sparse-Matrix-Implementationen.
Oder falls das Verhältnis von Knoten zu Kanten sehr hoch ist, könnte man als erste Alternative versuchen eine Inzidenzliste/-matrix zu verwenden.
-
FreakyBKA schrieb:
hallo,
ich wollte mal wissen ob sich die verwendung von templates stark auf die laufzeit auswirkt?
als kleines beispiel: ich habe einen graphen (adjanzenzlisten) mit 10^6 kanten und 10^6 knoten und lasse darauf algorithmen laufen. knoten und kanten sind bei template objekte, da sie noch diverse daten speicher können sollen. die frage ist halt nur ob eine feste implementierung des graphen, wo man die typen der daten schon kennt, in der laufzeit schneller läuft.
danke schonmal im vorausWenn zum Compile-Zeitpunkt alle Methoden der Klassen bekannt sind, braucht das Programm diese nicht zur Laufzeit dynamisch zu ermitteln, verwendest Du aber viritual base classes, ist das der Fall und verschlechtert die Performance.
Wenn es wirklich laufzeitkritisch sein sollte, waere sicher zu ueberlegen darauf zu verzichten.
Ein anderes Problem kann (!) die std::string sein, da diese bei jedem Zugriff verschiedene Check-Up macht. Das ist im Einzelfall kein Problem, passiert dies aber 10^8 und mehr in der Laufzeit kann das sich der Performance auswirken und dann kann ein Pointer auf char besser sein.