element und seine position in z.b. vektor _schnell_ finden

ANGs_Pino

Wenn ich einen Vektor (ich könnte ihn auch in eine liste/set/... ändern) nach einem Element durchsuchen will und dessen Position im Vektor (elementnummer) benötige, wie geht das am schnellsten (vektor ist sehr lang!).

Ich hatte die Idee mit einem set und dann .find(). Dann habe ich zwar einen Pointer auf das Element, mir fehlt aber die Position des Elements.

Jemand ne gute Idee?

bisher mache ich es so:

std::vector< int > v; //v füllen
int Element = 5;
int position = find (v.begin(), v.end(), Element) - v.begin() - 1;

ANGs_Pino

Vektor sortieren und binäre Suche durchführen.

Nexus

Paul___ schrieb:

Vektor sortieren und binäre Suche durchführen.

std::binary_search gibt aber z.B. nur zurück, ob das Element vorkommt, und nicht, wo. Da müsste man was anderes nehmen.

Wenn du die Position mehrmals brauchst, lohnt sich ein Sortieren schon. Ansonsten könntest du auch mit Indizes suchen, ist möglicherweise ganz leicht schneller als mit Iteratoren, was aber nicht sein muss. Probier am besten mehrere Möglichkeiten aus.

Tachyon

#include <set>
#include <iterator>

//...

std::set<SomeType> data;

//befuellen

std::set<SomeType>::difference_type pos = std::distance(data.begin(), data.find(elemToFind));

Mir ist jedoch nicht so ganz klar, wozu.

volkard

vielleicht std::lower_bound()
http://www.cplusplus.com/reference/algorithm/lower_bound.html

Nexus

std::distance() wird in assoziativen Containern aber nicht allzu schnell sein. Da lohnt es sich meines Erachtens mehr, Random-Access-Container wie std::vector oder std::deque einmal zu sortieren und dafür in konstanter Zeit den Index zu erhalten. Besonders, wenn man mehr als einmal die Position im Container braucht.

Tachyon

Nexus schrieb:

std::distance() wird in assoziativen Containern aber nicht allzu schnell sein. Da lohnt es sich meines Erachtens mehr, Random-Access-Container wie std::vector oder std::deque einmal zu sortieren und dafür in konstanter Zeit den Index zu erhalten. Besonders, wenn man mehr als einmal die Position im Container braucht.

Das hängt auch etwas davon ab, was in dem Container gespeichert wird, bzw. wie komplex die Vergleiche beim Suchen sind.
Aber wenn der TO mal beschreibt, wozu das überhaupt gut sein soll, könnte man evtl. einen alternativen Vorschlag machen.
Siehe auch die Sache mit dem Slave-Vektor in diesem Thread. Und nicht zu letzt stellt sich mal wieder die Frage, ob sich dieser Abschnitt im Programmfluss beim Profiling als Flaschenhals entpuppt hat, oder ob das eine weiterer Fall von "premature Optimization" ist.

Vielleicht gleich ne bessere Datenstruktur zum suchen verwenden oder warum muss es vektor sein?

Nexus

Tachyon schrieb:

Das hängt auch etwas davon ab, was in dem Container gespeichert wird, bzw. wie komplex die Vergleiche beim Suchen sind.

Bei Random-Access-Iteratoren verwendet std::distance() den operator- . Bei bidirektionalen Iteratoren, wie sie in assoziativen Containern vorkommen, wird dagegen solange inkrementiert, bis eine Gleichheit zustande kommt. Und da der Container angeblich sehr gross ist, ist O(n) im Allgemeinen keine optimale Lösung. Jedoch hast du Recht, wenn man zum Beispiel nur einen Index braucht, kann es sein, dass std::distance() sich auszahlt. Dazu wissen wir - wie du schon sagtest - zu wenig.

Tachyon schrieb:

Aber wenn der TO mal beschreibt, wozu das überhaupt gut sein soll, könnte man evtl. einen alternativen Vorschlag machen.

Ich habe ihm einfach mal Vorschläge gebracht, die für ihn wahrscheinlich am besten geeignet sind, wenn man nur seine beiden Voraussetzungen berücksichtigt (viele Werte im Container, möglichst schnell).

Tachyon schrieb:

Und nicht zu letzt stellt sich mal wieder die Frage, ob sich dieser Abschnitt im Programmfluss beim Profiling als Flaschenhals entpuppt hat, oder ob das eine weiterer Fall von "premature Optimization" ist.

Das Argument kann man fast immer bringen, aber hier finde ich es unangebracht. Der Threadersteller hat schliesslich gefragt, was die schnellste Lösung sei, die Frage kann also rein theoretisch betrachtet werden.

Brunnenvergifter schrieb:

Vielleicht gleich ne bessere Datenstruktur zum suchen verwenden oder warum muss es vektor sein?

Man kann auch auf std::vector optimierte Algorithmen wie binäre Suche anwenden.

volkard

Tachyon schrieb:

Und nicht zu letzt stellt sich mal wieder die Frage, ob sich dieser Abschnitt im Programmfluss beim Profiling als Flaschenhals entpuppt hat, oder ob das eine weiterer Fall von "premature Optimization" ist.

demnächst lösche ich einfach ohne nachfrage die postings, die "premature optimization" enthalten.
bis dahin lies bitte 23.4.6 in "Die C++-Programmiersprache" von Stroustrup.

Nexus schrieb:

Brunnenvergifter schrieb:

Vielleicht gleich ne bessere Datenstruktur zum suchen verwenden oder warum muss es vektor sein?

Man kann auch auf std::vector optimierte Algorithmen wie binäre Suche anwenden.

Selten.

Nexus

Brunnenvergifter schrieb:

Selten.

Was selten? Kannst du dich klar ausdrücken oder willst du nur rumtrollen?

volkard schrieb:

Tachyon schrieb:

Und nicht zu letzt stellt sich mal wieder die Frage, ob sich dieser Abschnitt im Programmfluss beim Profiling als Flaschenhals entpuppt hat, oder ob das eine weiterer Fall von "premature Optimization" ist.

demnächst lösche ich einfach ohne nachfrage die postings, die "premature optimization" enthalten.
bis dahin lies bitte 23.4.6 in "Die C++-Programmiersprache" von Stroustrup.

Heulsuse. :p

Nexus schrieb:

Brunnenvergifter schrieb:

Selten.

Was selten? Kannst du dich klar ausdrücken oder willst du nur rumtrollen?

Na überleg mal, wann kann man binäre Suche bei nem vector verwenden?

Nexus

Brunnenvergifter schrieb:

Na überleg mal, wann kann man binäre Suche bei nem vector verwenden?

Und rate mal, weshalb ich etwas von Sortieren geschrieben habe...

Meistens ist bei nem vector aber die Reihenfolge wichtig, sonst könnte man ja einfach n set oder so nehmen. Kindergarten

Tachyon

volkard schrieb:

[...]demnächst lösche ich einfach ohne nachfrage die postings, die "premature optimization" enthalten.
bis dahin lies bitte 23.4.6 in "Die C++-Programmiersprache" von Stroustrup.

Jau, das hält auch die Datenbank sauber.

Nexus schrieb:

Brunnenvergifter schrieb:

Na überleg mal, wann kann man binäre Suche bei nem vector verwenden?

Und rate mal, weshalb ich etwas von Sortieren geschrieben habe...

Ne, der Brunnenvergifter hat schon recht. Irgendwie scheint den TO ja die Position eines gefundenen Eintrags zu interessieren. Das lässt (zugegeben ist das ein wenig Kaffeesatzleserei) auch vermuten, dass die Einfügereihenfolge in den Container wichtig ist. Insofern ist ein Vektor vermutlich tatsächlich das Beste.

volkard

Tachyon schrieb:

auch vermuten, dass die Einfügereihenfolge in den Container wichtig ist. Insofern ist ein Vektor vermutlich tatsächlich das Beste.

dann vielleicht den vector wegkapseln und möglichst wenige funktionen anbieten.
sowas kleines wie

int find(double d);
void set(int pos,double d);
double get(int pos);
void grow(int newSize);

und dann hat man die freie wahl, was man sich einfallen lassen möchte, ohne daß irgendwas kaputtgehen kann. am einfachsten eine map<double,int> nebst

void set(int pos,double d)
{
   theMap[d]=pos;
   theVector[pos]=d;
}

wenig aufwand, suchen geht in O(log(n)), klappt nur wenn keine doppelten werte vorkommen, was ich mal frech annnehme.

Nexus

Tachyon schrieb:

Irgendwie scheint den TO ja die Position eines gefundenen Eintrags zu interessieren. Das lässt [...] auch vermuten, dass die Einfügereihenfolge in den Container wichtig ist. Insofern ist ein Vektor vermutlich tatsächlich das Beste.

Hm, ich habe an folgende Aussage gedacht, als ich annahm, eine Sortierung sei okay...

ANGs_Pino schrieb:

Wenn ich einen Vektor (ich könnte ihn auch in eine liste/set/... ändern) nach einem Element durchsuchen will

Was die Position betrifft, die kann man auch vor dem Sortieren im Element selber (z.B. in einem std::pair<value, size_t> ) speichern.

hustbaer

Naja, es gibt auch noch Boost.Multiindex.

@volkard: was bitte steht in Die C++-Programmiersprache 23.4.6?
(ich hab das Buch nicht, und nicht vor es mir zu kaufen)

volkard

hustbaer schrieb:

Naja, es gibt auch noch Boost.Multiindex.
@volkard: was bitte steht in Die C++-Programmiersprache 23.4.6?
(ich hab das Buch nicht, und nicht vor es mir zu kaufen)

es fängt an mit
"Donald Knuth hat beobachtet, daß >>unreife Optimierung die Wurzel alles Bösen ist<<. Einige Leute haben diese Lektion zu gut gelernt und betrachten nunmehr alle Bemühungen um Effizienz als etwas Schlechtes. Im Gegentiel, Effizienz sollte während der gesamten Design- und Implementierungsbemühungen im Bewußtsein gehalten werden."
im weiteren stellt er klar, "Die beste Strategie für Effizienz besteht darin, ein klares und einfaches Design zu erzeugen." und prangert gigantismus und firlefanz an. "Optimierung sollte das Ergebnis von Analyse und Performance-Messungen und nicht von zufälligem >>Herumpfuschen<< am Code sein." ... und daß man vermeiden soll, von vorn herein lahme konstrukte zu nehmen, weil die dann doch optimiert werden müssen am ende gefrickelt wird.