Assoziatives Array



  • Hallo an alle!

    Vorweg - ich suche schon seit Stunden; wenn es bereits einen Thread darüber gibt, dann freue ich mich über jeden Link!
    Wahrscheinlich wird es für euch eh recht einfach sein ..hoffe ich 🙂

    Im Prinzip benötige ich eine Datenstruktur, die in PHP z.B. so ausschaut:

    Array
    (
        [22] => Array
            (
                [76] => Array
                    (
                        [0] => 1269501450
                        [1] => *unix timestamp*
                        [2] => *unix timestamp*
                        [..] => ..
                    )
            )
        [12] => Array
            (
                [18] => Array
                    (
                        [0] => *unix timestamp*
                        [1] => *unix timestamp*
                        [..] => ..
                    )
            )
    )
    

    Also in erster und zweiter Dimension einen numerischen Key, der nicht fortlaufend ab 0 losgeht und in der dritten Dimension eine x beliebige Anzahl von unix timestamps.
    Wie ihr euch denken könnt sind die Keys in der ersten und zweiten Dimension Datenbank-Ids und die Unix-Timestamps sollen die Vorkommnisse protokollieren.

    Das Ganze sollte natürlich gut mit dem Speicher umgehen, also dynamisch sein.

    Ich kam bereits auf die Idee das mit structs zu machen:

    struct idTwo_data{
        int iId;
        int *iOccurrenceTimestamps;
    };
    
    struct idOne_data{
        int iId;
        struct idTwo_data *idTwoStructs;
    };
    

    Mein Problem hier war, dass ich bei der Umsetzung keinen Fuss auf den Boden bekommen hab.
    Also dynamisch das Ganze prüfen und speichern - nichtsdestotrotz bin ich momentan natürlich immer noch dabei es zu lösen 😉

    Könnt ihr mir vielleicht ein paar Tipps geben, wie man so etwas machen kann bzw. ob es da andere Wege gibt?! Vielen Dank schonmal!



  • Eine Implementierung eines Binären Baumes (Oder Abwandlung wie Rot-Schwarz-Baum) eignet sich hierfür, wobei du zwei Implementierungen brauchst (für die zweit unterschiedlichen Tiefen). Dazu gibt es zahlreiche Tutorials.

    Allerdings ist C hier definitiv nicht die beste Wahl. Kannst du keine andere Sprache nutzen?



  • Janjan schrieb:

    Eine Implementierung eines Binären Baumes (Oder Abwandlung wie Rot-Schwarz-Baum) eignet sich hierfür, wobei du zwei Implementierungen brauchst (für die zweit unterschiedlichen Tiefen). Dazu gibt es zahlreiche Tutorials.

    Ah ok, also ein Baum, der die erste Ebene mit IDs abdeckt und in den NILs dann Ressourcen auf eine weiteren Baum mit der 2. Ebene beinhaltet (dessen NILs dann natürlich wieder die timestamps haben)? Macht Sinn 🙂

    Janjan schrieb:

    Allerdings ist C hier definitiv nicht die beste Wahl. Kannst du keine andere Sprache nutzen?

    Leider nein. Der Teil ist für ein sonst fertiges Programm, das ich bis morgen fertig haben will - das Beste kam, wie immer, zum Schluss 🙄 😉


  • Mod

    taris schrieb:

    Janjan schrieb:

    Allerdings ist C hier definitiv nicht die beste Wahl. Kannst du keine andere Sprache nutzen?

    Leider nein. Der Teil ist für ein sonst fertiges Programm, das ich bis morgen fertig haben will - das Beste kam, wie immer, zum Schluss 🙄 😉

    Würde es in Frage kommen, den Teil mit dem assoziativem Array in C++ zu machen? Dein C-Programm dürfte zu C++ kompatibel sein und dann kannst du einfach die assoziative Liste aus der C++-Standardbibliothek einbauen.

    Falls nicht: Viel Glück das an einem Tag zu programmieren. Klingt eher nach einem Projekt für eine halbe Woche.



  • SeppJ schrieb:

    Würde es in Frage kommen, den Teil mit dem assoziativem Array in C++ zu machen? Dein C-Programm dürfte zu C++ kompatibel sein und dann kannst du einfach die assoziative Liste aus der C++-Standardbibliothek einbauen.

    Falls nicht: Viel Glück das an einem Tag zu programmieren. Klingt eher nach einem Projekt für eine halbe Woche.

    Nun, wenn ich den übrigen Code verwenden kann soll es mir erstmal recht sein 🙂
    Ist Standard-C mit ein paar POSIX-Sachen.

    Die "map"s schauen in der Tat schon sehr gut aus - werd dann mal versuchen meinen Code erstmal durch einen c++ compiler zu jagen 🙂
    Vielen Dank euch zwei schonmal! Ich vermelde die Ergebnisse 😉



  • evtl. lässt sich auch damit was anfangen 😕
    http://piumarta.com/software/tree/tree-1.0/tree.h
    bzw.
    http://piumarta.com/software/tree/tree-1.0/
    damit solltest auf jeden fall schon mal in ebene 2 kommen;)

    lg lolo



  • taris schrieb:

    dritten Dimension eine x beliebige Anzahl von unix timestamps

    da könntest dir den speicher auch mit malloc besorgen und bei bedarf mit realloc vergrößern dann sparst dir die linked list 😉



  • Sofern es akzeptabel ist, dürfte zum Selberimplementieren wohl eine einfache Hashtabelle mit separate chaining das einfachste sein, am besten indem du die ersten beiden Ebenen zusammenwirfst und aus jeweils beiden Keys einen einzigen Hashwert berechnest.

    Ansonsten gibt es auch jede Menge Bibliotheken für AVL-Bäume u.ä.



  • Nein, C erlaubt es nicht externe Bibliotheken zu benutzen!



  • Tim schrieb:

    Nein, C erlaubt es nicht externe Bibliotheken zu benutzen!

    Wie jetzt? (Der Orakelspruch lässt grüssen)

    Nein, C erlaubt es, nicht externe Bibliotheken zu benutzen?
    oder
    Nein, C erlaubt es nicht, externe Bibliotheken zu benutzen?

    Ich nehm's ja sonst nicht so genau, aber das macht schon einen Unterschied.
    🙂



  • mngbd schrieb:

    Wie jetzt? (Der Orakelspruch lässt grüssen)

    Nein, C erlaubt es, nicht externe Bibliotheken zu benutzen?
    oder
    Nein, C erlaubt es nicht, externe Bibliotheken zu benutzen?

    Ich nehm's ja sonst nicht so genau, aber das macht schon einen Unterschied.
    🙂

    Hihi, das war ein echter Tim 🤡 .
    Der schaut alle paar Wochen vorbei, schmeißt ein paar kryptische Brocken in ein, zwei Unterthemen und ist wieder weg.
    Ich vermute, er meinte Letzteres, was es aber nicht verständlicher macht.
    Ich glaube, die meisten von uns haben es schon geschafft, eine Lib statisch zu linken, deren Source wir nicht haben bzw. mir fällt jetzt auch nicht ein, wie C es mir verbieten sollte, eine DLL zur Laufzeit zu laden.
    Irgendwas wird er schon gemeint haben ... whatsoever 😕 ... egal! 🙂



  • pointercrash() schrieb:

    mngbd schrieb:

    Wie jetzt? (Der Orakelspruch lässt grüssen)

    Nein, C erlaubt es, nicht externe Bibliotheken zu benutzen?
    oder
    Nein, C erlaubt es nicht, externe Bibliotheken zu benutzen?

    Ich nehm's ja sonst nicht so genau, aber das macht schon einen Unterschied.
    🙂

    Hihi, das war ein echter Tim 🤡 .
    Der schaut alle paar Wochen vorbei, schmeißt ein paar kryptische Brocken in ein, zwei Unterthemen und ist wieder weg.
    Ich vermute, er meinte Letzteres, was es aber nicht verständlicher macht.
    Ich glaube, die meisten von uns haben es schon geschafft, eine Lib statisch zu linken, deren Source wir nicht haben bzw. mir fällt jetzt auch nicht ein, wie C es mir verbieten sollte, eine DLL zur Laufzeit zu laden.
    Irgendwas wird er schon gemeint haben ... whatsoever 😕 ... egal! 🙂

    Er mein, er soll eine fertige hash map oder tree Implementation für C nehmen. Z.B. den Code hier http://www.thequest03.de/DBPre_src/hashmap.c.html (obwohl ich nicht weiß welche Lizenz es ist).



  • Vielen Dank für die ganzen Tipps und Antworten!

    Ich bin jetzt doch nochmal an meine Structs gegangen und habe das Problem folgendermaßen gelöst:

    struct idTwo_data{
        int iId;
        int *iOccurrenceTimestamps;
    };
    
    struct idOne_data{
        int iId;
        struct idTwo_data *idTwoStructs;
    };
    

    Ich habe einen Pointer auf das Struct "idOne_data" ("struct idOne_data *idOneStructs") das ich für jede neue Id dynamisch wachsen lasse. Die ID selbst schreibe ich in das "iId" Feld und der Index ist einfach fortlaufend.
    Sobald ich die dazugehörige ID für die 2. Ebene bekomme mache ich dasselbe innerhalb des Structs mit dem "idTwoStructs" Pointer. Dazu gibt es ein paar Funktionen, die mir anhand der ID das passende Struct raussuchen (jeweils für die 1. und 2. Ebene)

    Auch im 2. Struct wird der "iOccurrenceTimestamps" Pointer dynamisch erweitert und bekommt seine Timestamps.

    Also sieht meine ursprüngliche Struktur so aus:

    Array
    (
        [22] => Array
            (
                [76] => Array
                    (
                        [0] => 1269501450
                        [1] => *unix timestamp*
                        [2] => *unix timestamp*
                        [..] => ..
                    )
            )
        [12] => Array
            (
                [18] => Array
                    (
                        [0] => *unix timestamp*
                        [1] => *unix timestamp*
                        [..] => ..
                    )
            )
    )
    

    und das Endergebnis ungefähr so:

    *idOneStructs[0]
        ->iId = 22;
        ->*idTwoStructs[0]->
            ->iId = 76;
            ->*iOccurrenceTimestamps[0] = 1269501450;
            ->*iOccurrenceTimestamps[1] = *unix timestamp*;
            ->*iOccurrenceTimestamps[2] = *unix timestamp*;
            ->*iOccurrenceTimestamps[..] = ..;
        ->*idTwoStructs[1]->..
        ->*idTwoStructs[..]->..
    
    *idOneStructs[1]
        ->iId = 12;
        ->*idTwoStructs[0]->
            ->iId = 18;
            ->*iOccurrenceTimestamps[0] = *unix timestamp*;
            ->*iOccurrenceTimestamps[1] = *unix timestamp*;
            ->*iOccurrenceTimestamps[..] = ..;
    

    Das Ganze läuft super und hat soweit keine Leaks - also bestens erfüllt 🙂
    Eure Links hab ich mir mal weggespeichert - werd ich bestimmt noch brauchen.

    Vielen Dank nochmal!


Anmelden zum Antworten