Eindeutige Integerzahl
-
Beim Programmstart lade ich von Textfile 9000000 strings(IDs)in einem container -->SET und tue double check.
Es dauert jedesmal 15 Min bis die strings oder IDS hochgeladen im Programm und Auch verbraucht zuviel Arbeitsspeicer.
mit integers Dauert 30% von Zeit und Arbeitsspeicher.Also beides wird nicht gehen Schneller Rechnen und weniger Arbeitsspeicher ist bei solchen Algorithmen meist nicht drin, zumal Du mit dem Integer noch einen Informationsverlust hast.
Da Du bisher ein Set (ist als Binänbaum abgelegt) mit 9Mio Werten ca. (ln(9000000)~16) 16 Vergleiche pro Zugriff verwendest und große set's auch beim Einfügen neuer Werte oft ne Menge arbeiten müssen, wär vielleicht eine 2-stufigen Lösung möglich?
Als erste Ebene ein Hash mit vielleicht 50000 Werten.
Hinter jedem dieser Hashwerte steht ein Set wie Du es bisher auch verwendest.
Nur kommt jetzt in jedes Set nur ca (9Mio/50000) 180 Werte.
d.h. Du hast pro Zugriff nur einen Hashzugriff und einen Set Zugriff mit (ln(180)) 5 Vergleichen anstatt 16 Vergleiche.Das könnte deine Zugriffszeiten beschleunigen aber auch deinen Speicherbedarf erhöhen.
An dem Hashwert kann man dann drehen und ein Optimum (irgendwas zwischen 100 und 8000000) von Speicherbedarf und Geschwindigkeit ermitteln.
Babbage
-
ich habe was gefunden -->map
dadurch kann ich meine strings
123/12 in 2 Teile beide integer teilen.ich weiss nicht , ob map zuverlässig?
kann map höhe zahl von werte laden.Wieviel? und auch wieviel kann set laden als maximum?
wenn ich ein set von type (123/12) string und ein map von type(123,12) (int,int )
wer von beiden schneller .
über hash habe was gelesen und werde mich demnäscht rumschauen.
-
Die maximale Größe von map<> und set<> ist jeweils nur vom verfügbaren Speicherplatz abhängig, also kannst du im Extremfall deinen RAM mit einer einzigen map<> vollschaufeln, wenn du es drauf anlegst. Und die Suche in map's ist auch vergleichbar mit set's (die arbeiten intern auf der selben Datenstruktur, nur daß map noch einen zusätzlichen Wert zu jedem Schlüssel mitschleppt).
ABER: Die Elemente der map werden nur nach ihrem Schlüssel verglichen (das kann von Vorteil sein, aber es gefährdet die Eindeutigkeit deiner IDs noch stärker als die bisher vorgeschlagenen Hash-Funktionen - für die map sind die Elemente (123/13) und (123/47) identisch). Als Kompromiss wäre es auch möglich, ein set<pair<int,int> > zu verwenden - das dürfte schneller vergleichen als set<string> und im Gegensatz zu deiner map berücksichtigt es den kompletten Schlüssel.
-
danke du hast mir viele zeit erspart.
kannst du vielleicht ein kleines Beispiel tippen um zu zeigen
1-wie definiere ich set<pair<int,int> >
2-wie füge ich paar elemente
3-wie kann ich ein wert raus finden ob vorhanden oder nicht
brauch ich extra includs als # include <set>
-
1. genauso wie's da steht:
set<pair<int,int> > daten;
2./3. wie bei einem normalen set<int> auch (nur daß du statt einzelnen Zahlen mit Zahlenpaaren arbeiten mußt) - aus zwei Zahlen kannst du per make_pair() ein Paar erzeugen - und daraus über p.first und p.second wieder die einzelnen Werte auslesen
4. Du brauchst noch#include <utility>für das pair<>
-
Muß denn zwischen
123/12
und
0123/12
unterscheiden werden?Ein set<pair<int,int> > macht die Opration nur um den Faktor schneller, den ein Integervergleich schneller ist als ein Stringvergleich (und schnellere Kopieraktionen)
Aber die Anzahl der Vergleiche bleibt, ebenso wie die Verwaltungsarbeit des großen Binärbaums (egal ob set oder map)
Da ein Stringvergleich bei unterscheidlichen ersten Zeichen ziemlich schnell ist glaube ich nicht das der Effekt riesig groß sein wird.
-
Hab die ganze Sache mal mit nem Hash-Table realisiert und 10Mio Strings reingeschrieben.
Die Sache geht solange gut (bis ca. 3-5 Mio) bis eine Temp-Datei auf die Festplatte ausgelagert wird und nix geht mehr.Ohne dies Problem würde die Aktion wohl bei mir in ner Minute durchlaufen.
-
Hast Du das Problem immer noch oder ist die Sache abgechlossen?
Ich brauch mit Quicksort inzwischen ca. 20sek für 10Mio strings.Babbage