Performance: index-mengen
-
Hallo,
ich möchte etwas Meinungen einholen bzw. sehen was es alles für möglichkeiten gibt. Ich möchte Mathematische Index-Mengen Operationen möglichst effizient (meint zeitliche Performanz) schreiben.
Die wahl von int-arrays mit operationen wie schnitt, vereinigung, differenz, komplement etc. scheint mir nicht gerade effizient und auch einiges an aufwand.
Gäbe es eine Möglichkeit alles auf bitsets zu schreiben oder gibt es eine performante STL Implementierung?
Es muss doch eine Möglihckeit geben über shifts und andere Bit-Operatoren dies möglihcst effizient schaffen. ?
Stand jemand schonmal vor einem solchen Problem?
-
hängt von der verteilung der indizes ab. bitsets taugen nur, wenn sie sehr dicht liegen.
sortiere doch einfach alle indexmengen.
dann gehen alle operationen in O(n), wenn ich recht über den daumen peile, und es wird auch kein speicher verschwendet (außer interner fragmentierung von vector/queue/list).
-
Wie waere es mit std::set<int>?
-
bitsets taugen nur, wenn sie sehr dicht liegen.
was heißt sehr dicht liegen?
Wie waere es mit std::set<int>?
ist das intern wirklich performant implementiert?
-
uffob schrieb:
bitsets taugen nur, wenn sie sehr dicht liegen.
was heißt sehr dicht liegen?
nicht gerade 100 indeswerte im bereich zwischen 0 und 100000000. willst ja nicht 100000000 bits auf 0 setzen, um dann 100 auf 1 zu setzen und zu zählen.
uffob schrieb:
Wie waere es mit std::set<int>?
ist das intern wirklich performant implementiert?
ja. aber es ist halt "nur" ein binärbaum. den solltest du nehmen.
-
und müsste ich über std::set<int> dann vereinigung und schnitt von indexmengen selbst implementieren? Im standard finde ich keinerlei vorhandene methode...
-
uffob schrieb:
und müsste ich über std::set<int> dann vereinigung und schnitt von indexmengen selbst implementieren? Im standard finde ich keinerlei vorhandene methode...
musst du (aus anderen funktionen aus <algorithm>) basteln.
hilfreich für die vereinigung sollte merge sein. oder war es set_union? uih, es gibt sogar set_symmetric_difference. das ist ja wie weihnachten.