Diese Seite ist unverschlüsselt! Um sicherzustellen, das Ihr Passwort nicht ausgelesen werden kann, sollten Sie auf die verschlüsselte Seite wechseln!

    Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (GNU/Linux, *NIX, *BSD und Co) » map ohne reserve?
Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ]
000
31.01.2007, 15:54 Uhr
flappinski



 Hallo Leute,
ich habe folgendes Problem: Ich lese ein Art Info-Datei in eine Map ein, wo der Schlüssel des Paares immer das erste Feld der Zeile, ist, ungefähr so:

C++:
while(getline(In, line)){
  line_map[string_to_map(line,ptgt_divisor)]=line;
}


line_map ist eine map<string,string> und die Funktion string_to_map holt das erste Feld raus. Diese Funktion ist natürlich als inline eingebunden und kostet nur Bruchteile der Zeit. Womit wir schon bem Thema wären:

Bei 12 Mio. Zeilen dauert das ziemlich lange ( 1min.) im Gegensatz zum reinen einlesen (10 sec). Folgendes ist genauso langsam


C++:
line_map[line]=line;


Das hier allerdings kommt der reinen Einlesegeschwindigkeit schon sehr nahe:


C++:
line_map["test"]=line;


Ich denke, also, dass die meiste Zeit damit vergeht, diese Paare zu bilden, bzw. den Speicherplatz dafür zu allozieren. Bei Vektor gab es doch dafür sowas wie std::vector::reserve. Gibt es irgendwas vergleichbares bei einer Map? Habt ihr sonstige Tips?
Vielen Dank,
Stephan
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
31.01.2007, 16:07 Uhr
Blubber2063



 Das dürfte von der Implementation abhängen, aber anzunehmen ist das meist ein AVL Baum dafür genommen wird, und da wird für jeden Knoten neuer Speicher alloziert, da muss nichts umkopiert werden. Allerdings braucht man für das Auffinden von Daten im Schnitt eben O(log n) und der erste Wert den du in der Map eingetragen hast, muss nicht die Wurzel sein, also kein O(1) Aufwand dafür.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
31.01.2007, 16:21 Uhr
flappinski



 Hi Blubber,
tut mir Leid, aber ich verstehe das nicht ganz, kannst Du mir das nochmal genauer erläutern? Ich kann nur anmerken, dass ich gar nicht vom auffinden sprach, sondern bisher nur vom anlegen der Map. Oder muss ich dafür auch Auffinden?
Ich kenne mich da noch nicht so aus, aber vielen Dank für die rasche Antwort.
Grüsse,
Stephan
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
31.01.2007, 16:24 Uhr
FloSoft
Medialer Over-Flow
(Administrator)


Hi,
naja das erste anlegen geht direkt, danach muss er eben die Stelle auffinden an der er das Element in den Baum einfügen muss -> das dauert.
--
class God : public ChuckNorris { };
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
31.01.2007, 16:26 Uhr
Blubber2063



 Ja auch für das einfügen, zumindest solange es als Balancierter Binärbaum implementiert ist(bei Hashing nicht, aber das nennt man dann normalerweise meist auch Hashmap). Falls du dir das mal genauer zu Gemüte führen willst solltest du mal nach Literatur zu AVL und Rotschwarz Bäumen konsultieren.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
31.01.2007, 16:40 Uhr
flappinski



 Oh vielen Dank, aber ich möchte mir das nicht genauer zu Gemüte führen.
Nun ist meine Problem ganz konkret: Ich will in diesem Info_Datei (mit den 12 Mio. Zeilen ) die Information von ca. 500000 Objekten haben. Also nur ein recht kleiner Teil davon. Ich habe bisher mit deutlich kleineren Zahlen gearbeitet und mit der Map eben dieses gut lösen können. Mit den grossen Datenmengen wird es eben so langsam. Geht es denn auch anders, dieses Problem zu lösen (manchmal sieht man ja das Problem einfach nicht...)
Grüsse,
Stephan
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
31.01.2007, 16:45 Uhr
Blubber2063



 Naja dafür müssten wir wissen was du mit den Daten anstellen willst, irgendwie sieht es recht Sinnfrei aus das du ein Schlüsselpaar erstellst, das als Schlüssel den selben Wert hat wie die zugehörigen Daten.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
31.01.2007, 16:58 Uhr
flappinski



 O.K. ich versuche es genauer.
Ich erstelle natürlich kein Schlüsselpaar mit
line_map[line]=line;
Das war natürlich nur zur Anschauung, das die Funktion, die das erste Feld rauszieht, nicht für den Geschwindigkeitsverlust verantwortlich ist. Aber das wusstet ihr sowieso schon. Also mal von vorne, mal ohne Map.


folgende Beipielinfo-Datei:
fred str1 arzt
hans str5 rechtsanwalt
hans2 str8 programmierer
....
(12 Mi. Einträge)

Alle Namen sind eindeutig.

jetzt habe ich 600000 Namen, brauche ihre Strasse und ihren Beruf um mit diese Information in meinen Programm weiter mit den Namen mitlaufen zu lassen. Natürlich weiss ich nicht vorher, welche Namen. Sobald ich die Information habe, brauche ich auch die Info-Datei nicht mehr, also habe ich ca. 11,5 Mio. Einträge "umsonst" eingelesen. Das hat mich bei kleineren Mengen wied gesagt nicht gestört....

Habe ich das jetzt einigermassen klar verfasst?

Viele Grüsse,
Stephan
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
31.01.2007, 17:41 Uhr
Blubber2063



 Wenn dich sowieso nur ein Eintrag brauchst, oder nur ein Paar, dann pack doch auch nur die in die Map, du kannst doch nen Vergleich auf die eingelesenen Strings machen.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
31.01.2007, 17:46 Uhr
flappinski



 ich glaube, ich bekomme einen Gefühl, für Deine Idee. Also erst die Map mit den 600000 Einträgen und diese dann mit der Information auffüllen. Das könnte deutlich verbessern, muss ich mal probieren. Melde mich dann.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ]     [ C / C++ (GNU/Linux, *NIX, *BSD und Co) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: