Minimal value in std::map?
-
Hallo zusammen,
ich programmiere gerade an einem Projekt, bei dem ich mehrere Distanzen in einer normalen map gespeichert habe, bei dem der Key ein Zeiger auf ein Objekt ist und der Value die Distanz zu diesem Objekt darstellt.
Diese Distanzen muss ich öfters spezifisch updaten, wobei ich dann über den Objektzeiger zugreifen muss. Allerdings wäre es auch wünschenswert, wenn ich auf irgendeine Art die Distanzen sortiert haben würde oder dass es eine andere gute Möglichkeit gibt, so dass ich schnell die minimalste Distanz finden kann. Es kann dabei auch durchaus auftreten, dass gleiche Distanzen mehrfach enthalten sind.
Hätte da evtl. jemand eine Idee wie man das realisieren könnte?
-
-
Wenn du dir nicht den Aufwand machen willst eine zweite Datenstruktur zu verwalten gibts keine Moeglichkeit die Suche wesentlich zu beschleunigen.
Wenn du die min-Operation wirklich extrem oft brauchst koennte es sich lohnen einen kleinen Wrapper um std::map zu schreiben, darin koenntest du deine insert-Funktion so anpassen dass Sie dir nen Iterator auf das kleinste Element aktuell haelt.
-
Wie wäre es mit einer zweiten Liste, die nach Distanzen sortiert ist?
Vorteil: Du kannst gezielt nach Distanzen suchen
Nachteil: Wenn sich eine Distanz ändert, musst du dies in beiden Listen ändern, was logischerweise doppelt so lange dauert.Oder falls du nicht alle Distanzen sortiert benötigst sondern nur die kleinste: So wie oben, aber nur eine kurze Liste der kleinsten Distanzen. Wird eine Distanz kleiner als eine Distanz aus dieser Liste, wird sie an der entsprechenden Stelle eingefügt und die größte Distanz aus der Liste fliegt raus. Wird eine Distanz aus der Liste größer fliegt sie ebenfalls raus. Sollte die Liste irgendwann nur noch ein Element enthalten werden alle Distanzen nochmal gescant.
Vorteil: Kann schneller sein als zwei komplette Listen
Nachteile: Weniger effizient wenn sich Distanzen wild ändern. Kann nur die kleinsten Distanzen finden, nicht alle Distanzen sortiert.Oder ein ganz anderer Ansatz:
Gehe ich davon aus, dass du Objekte im Raum verteilt hast? Wie wäre es dann mit Zelllisten anstatt von Distanzlisten?
Vorteile: Je nach Problem kann dies ein viel besserer Ansatz sein.
Nachteile: Je nach Problem kann dies ein viel schlechterer Ansatz sein. Dieser Ansatz ist völlig anders als der alte. Vollständiges Neuschreiben deines Programms wäre nötig.
-
Danke schonmal für die Antworten. Es ist hierbei in der Tat sehr wichtig, dass es so schnell wie möglich geht, weshalb ein "normales" durchlaufen sowie die min_element Funktion nicht so gut sind.
In die Richtung mit dem Iterator hab ich auch schon gedacht, aber das wird dann problematisch, da auch Elemente rausgelöscht werden müssen und dadurch erstens der Iterator nicht mehr gültig ist und zweitens dadurch das zweitkleinste Element "nachrutschen" würde wenn das kleinste gelöscht wird.
Wie könnte denn eine zweite Datenstruktur in dem Fall aussehen?Die Datenpunkte sind tatsächlich im Raum verteilt, genauer gesagt im zweidimensionalen
Das ganze ist ein bisschen komplizierter aufgebaut. Habe sozusagen ein Gitter über die Datenpunkte gelegt, dessen Zellhöhe und Breite durch thresholds festgelegt sind. So muss ich nur Distanzen zu Punkten ausrechnen, die in der Zelle selbst und den umliegenden Zellen ligen. Vielleicht geht das schon ein bisschen in die Richtung deiner Idee mit den "Zelllisten"!? Wie genau hast du das gemeint?
-
Du könntest ein
std::setmit Iteratoren in die Map haben. Das Set wird nach Distanzen sortiert. Beim Einfügen eines neuen Map-Elements fügst du den Map-Iterator im Set ein, beim Löschen analog. Die Zeitkomplexität erhöht sich dadurch nicht, es sei denn, du löschst in der Map in konstanter Zeit (über Iteratoren), dann hast du eben logarithmische Zeit. Um das auch noch zu beheben, könntest du in den Map-Elementen die Set-Iteratoren speichern.Versteht sich, dass du da eine kapselnde Klasse darum herum baust, sodass man nichts falsch machen kann und alles schön konsistent bleibt.
Vielleicht ist auch Boost.Bimap etwas für dich. Ich weiss aber nicht, wie effizient das ist.
-
Sassinator schrieb:
Wie könnte denn eine zweite Datenstruktur in dem Fall aussehen?
Ich würde eine multimap<distanz, pointer auf objekt> nehmen.
Und wie meinst du das mit "Zelllisten"?
Du teilst den Raum in Bereiche auf und führst für jeden Bereich eine Liste, welche Objekte sich darin befinden. Wenn du Objekte suchst, die einen kleinen Abstand zu einem bestimmten anderen Objekt haben, guckst du dir nur die Abstände zu Objekten in diesem Bereich (und evtl. Nachbarbereichen) an. Das ist eine Standardtechnik bei der Programmierung von Simulationen, wo man häufig die Abstände zwischen nahe beisammen liegenden Objekten benötigt. Für solche Modelle ist die Technik äußerst effizient. Falls dieser Fall bei dir vorliegt, solltest du dir das unbedingt mal ansehen.
-
Ah, ok.
Ja, das ist genau das was ich bereits implementiert habe. Wusste nur nicht genau was du meintest
Aber das reicht immer noch nicht wirklich von der Geschwindigkeit her, vor allem wenn es "Inseln" gibt mit vielen Datenpunkten die sehr nahe beieinander liegen.
Die anderen Ansätze hören sich auch alle interessant an.
Bei der Multimap müsste ich dann beim Update/Löschen über alle Distanzen mit dem gleichen Wert iterieren und dabei den entsprechenden Eintrag suchen, oder?zu der Liste von Iteratoren:
Würden mir dabei nicht meine Iteratoren "kaputt" gehen wenn ich Elemente aus der Map lösche?
-
Sassinator schrieb:
Bei der Multimap müsste ich dann beim Update/Löschen über alle Distanzen mit dem gleichen Wert iterieren und dabei den entsprechenden Eintrag suchen, oder?
Ja, das wäre der "Nachteil". Aber ich nehme doch mal an, dass sich die Anzahl der Punkte mit gleichen Distanzen in Grenzen hält, oder? Sollte daher nicht lange dauern.
-
Sassinator schrieb:
zu der Liste von Iteratoren:
Würden mir dabei nicht meine Iteratoren "kaputt" gehen wenn ich Elemente aus der Map lösche?Nur die, die auf die gelöschten Elemente zeigen. Aber die entfernst du ja fortlaufend, sodass nichts ungültig bleibt.
Das Schöne an assoziativen STL-Containern ist, dass Iteratoren, Referenzen und Zeiger auf die Elemente immer gültig bleiben (ausser natürlich, das Element selbst wird gelöscht).
-
SeppJ schrieb:
Ja, das wäre der "Nachteil". Aber ich nehme doch mal an, dass sich die Anzahl der Punkte mit gleichen Distanzen in Grenzen hält, oder? Sollte daher nicht lange dauern.
Prinzipiell sollte das eigentlich der Fall sein, aber ich verarbeite Daten aus der Massenspektrometrie, wo die Abstände dummerweise in sehr vielen Fällen identisch sind
Dann wird das wahrscheinlich nicht sehr effektiv sein...Nexus schrieb:
Das Schöne an assoziativen STL-Containern ist, dass Iteratoren, Referenzen und Zeiger auf die Elemente immer gültig bleiben (ausser natürlich, das Element selbst wird gelöscht).
OK, da war ich mir unsicher. Aber wenn das der Fall ist, könnte das in der Tat ein guter Ansatz sein.
