was ist schneller?



  • hallo, ich habe eine kleine frage.
    angenommen ich habe jetzt eine liste oder eine map mit sagen wir 10000 einträgen. wenn ich jetzt einige einträge manipulieren muss, dann ergeben sich für mich zwei möglichkeiten:
    möglichkeit 1)

    1. ich muss einige einträge löschen!
    2. ich muss in der map die indexe die hinter den gelöschten kram kommen nun auch löschen und neu anlegen weil sich der index durch den algo verändert

    ==> sind im prinzip 2 operationen nach dem löschen und könnte im prinzip ziemlich aufwendig werden wenn weit vorne gelöscht wurde

    möglichkeit 2)

    1. ich muss einige einträge löschen (wie möglk. 1)
    2. ich kopiere die modifizierten werte in eine neue map

    frage: was ist jetzt vorraussichtlich schneller?



  • Warum musst du da was löschen? Sprichst du jetzt von einer std::map/std::list, oder scheibst du was eigenes?

    Bei den Standard Container kannst du ja ganz einfach mittels Iteratoren auf die Objekte zugreifen und verändern. Da musst du gar nichts löschen.



  • honeyboon schrieb:

    hallo, ich habe eine kleine frage.

    Wie schon von drakon angedeutet, ist deine Fragestellung unzureichend (wenn nicht gar missverständlich) beschrieben

    Was verstehst du unter Manipulieren: Datenmanipulation auf Datensatzbasis oder auch das Hinzufügen/Löschen ganzer Datenmengen?

    Vielleicht wäre es einfacher wenn du ganz grob beschreibst um was es geht, was in etwa dein Algorithmus macht (Wie sieht der Initialzustand vor dem Algorithmus, und wie danach aus).



  • ich werde mal probieren zu erklären:
    ich habe eine map<int, string> in welcher ich indexe und dateinamen speichere. der index ist in sofern wichtig, weil er den frame in einem filmchen kennzeichnen soll. jetzt soll man frames löschen und einfügen können. dh. dass heißt, dass sich der index verändert, aber der dateiname immer gleich bleibt.
    wenn ich zum beispiel 1000 frames an stelle 0 einfüge, dann verschiebt sich der index nach stelle 0 um 1000. beim löschen umgekehrt etc.

    für den fall das ich frames lösche ergibt sich also folgender fall:
    deleframe(von, bis)
    -ich lösche alle indexe in dem bereich: von-bis
    -da jetzt frames fehlen muss ich die indexe verändern
    -da die map-klasse leider keine modifizierung des keys zulässt, habe ich also die auswahl jetzt die vorhandenen werte zu löschen und durch neue zu ersetzen oder gleich eine neue map zu schreiben

    oder es gäbe noch die möglichkeit den key zu ändern, aber anscheinend ist der const.


  • Mod

    Wenn ich dich richtig verstanden habe, schreit dein Problem geradezu nach der Verwendung von std::list. Den Index den du jetzt immer mitspeicherst ersetzt du dabei einfach durch die Nummer des Elementes in der Liste.



  • SeppJ schrieb:

    Wenn ich dich richtig verstanden habe, schreit dein Problem geradezu nach der Verwendung von std::list. Den Index den du jetzt immer mitspeicherst ersetzt du dabei einfach durch die Nummer des Elementes in der Liste.

    Dann wohl eher std::vector.. Random Access ist in dem Fall sicher sehr wünschenswert..



  • einfach std::vector oder ggf. boost multi-index.



  • Hallo honeyboon,

    ich gehe jetzt davon aus, daß du Container aus der STL (Standard Template Library) in deinem Beispiel meinst.
    Bei den Containern aus der STL brauchst du dich nicht um die Ablage der Daten im Speicher zu kümmern. Es entsteht kein 'Loch' in deiner Datenstruktur, wenn du ein Element löschst. Wie die Daten innerhalb der STL-Container konkret abgelegt sind, ist ein für dich im allgemeinen unwichtiges Implementationsdetail der verwendeten STL-Bibliothek.

    In Deinem Artikel vom 13.11.2008 nennst du als Container für deine Daten eine 'map'. Ich gehe mal davon aus, daß du eine std::map<key,value> meinst. Das ist ein nach Schlüsseln (key) sortierter assoziativer Container und der verwaltet Paare aus Schlüsseln (key) und zugehörigen Werten (value). Der Vorteil von assoziativen Containern ist der Zugriff auf die Werte (value) über die Schlüssel (key).
    Die std::map<key,value> besitzt keinen klassischen Indexoperator. Was wie ein Indexoperator aussieht, ist die Angabe des Schlüssels (key), auf dessen zugeordneten Wert du zugreifen möchtest. Ist dieser Schlüssel (key) nicht vorhanden, wird er eingefügt.
    In einer std::map<key,value> gibt es keine Möglichkeit, einen Schlüssel direkt zu ändern, denn das würde die Sortierung des Containers zerstören. Das geht nur über das Holen und anschließendes Löschen des alten Elementes und Einfügen des geänderten Elementes. Den zu einem Schlüssel (key) gehörenden Wert kannst du frei ändern über den Zugriffsoperator '[key]' oder die Elementfunktion 'at(key)'. Im Unterschied zum Zugriffsoperator '[key]' fügt 'at(key)' keinen Schlüssel ein. Wird der angegeben Schlüssel nicht gefunden, bleibt die map unverändert und eine Ausnahme (Exception) wird geworfen.

    In einer std::map<key,value> kann ein Schlüssel genau einmal vorkommen. Möchtest du mehrere Schlüssel-Wert-Paare mit gleichem Schlüssel einfügen, mußt du eine Multimap wählen.
    Soweit zu den Containern std::map<key,value> und std::multimap<key,value>.

    Du möchtest jedoch zu einem Dateinamen Frame-IDs hinzufügen und löschen. Im Klartext heißt das aber, daß zu einem Dateinamen kein, ein oder mehrere Frame-IDs existieren können. In diesem Fall ist eine Map - ein quasi eindimensionaler Container - , wie von dir angedacht und im Beispiel verwendet, nicht die richtige Datenstruktur. Hier empfehle ich dir eine 'zweidimensionale' Datenstruktur, und zwar eine 'std::map<std::string, std::set<unsigned long> >':
    in der ersten Dimension (std::map<Dateiname, Frame-ID-Container> haben wir als Schlüssel die Dateinamen, und diesen Dateinamen zugeordnet ein Container für die Frame-IDs (keiner, einer oder beliebig viele). Jeder Dateiname kann genau einmal vorkommen (soll ein Dateiname mehrfach vorkommen, mußt du die std::multimap<Dateiname, Frame-ID-Container> wählen). In der zweiten Dimension haben wir die Frame-IDs. Der Containertyp 'set<unsigned long> stellt sicher, daß jede Frame-ID höchstens ein mal vorkommt. Soll die Frame-ID mehrfach vorkommen, so mußt du nur std::multiset<Schlüssel> als Container nehmen nehmen. Bei einem std::set<key> kannst du allerdings wie bei einer map Elemente nicht direkt ändern, sondern nur löschen und neu einfügen. Dafür kannst du die Eelemente mittels eines Iterators in auf- oder absteigender Reihenfolge durchlaufen

    Ich hoffe, das hat die erstmal geholfen. Zur STL ist in jedem Fall ein gutes Buch hilfreich (Verlage 'Addison-Wesley' oder 'Galileo Press)

    mfg Mario



  • mario_69 schrieb:

    Zur STL ist in jedem Fall ein gutes Buch hilfreich (Verlage 'Addison-Wesley' oder 'Galileo Press)

    Dann lieber Addison-Wesley. Bei dem Zweiten Verlag weiß ich beim besten Willen kein Buch im C++ Bereich das wirklich gut wäre (Wobei ich die Aussage leider inzwischen bei fast allen deutschen Fachbuchverlagen zutreffend finde).

    cu André


Log in to reply