Assoziatives Array

taris

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?

taris

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

SeppJ

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.

taris

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

namespace invader

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!

mngbd

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.

pointercrash**

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!

DEvent

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).

taris

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!