Datenstrukturen zum Thema Voxel, Hashing, Komprimierung, einfach-verkettete Liste



  • Hallo!

    Es ist zwar immer blöd HA's von anderen lösen zu lassen, aber ich seh hier nicht richtig durch 😞 Es wäre cool, wenn mir jemand nen Tipp geben könnte, oder ne WebSite die das Problem betrifft oder irgendwelche Ansätze der Programmierung, das wäre sehr gut. Also hier erst mal die Aufgaben:

    (a) Gegeben sei Ihnen ein dreidimensionales Binärbild der Auflösung N×N×N. Darin seien durchschnittlich nur O(N2) Voxel gesetzt, die genaue Anzahl kann jedoch auch größer oder kleiner sein und soll sich zur Laufzeit ändern können (Setzen oder Löschen von Voxeln). Wie kann man das 3D-Bild unter Ausnutzung von Hashing komprimieren, aber gleichzeitig noch in konstanter Zeit einen wahlfreien Zugriff gewährleisten, z. B. um zu klären, ob ein Voxel gefüllt ist oder nicht? Es reicht also nicht, die Vordergrundvoxel der Reihe nach in eine Liste zu schreiben! Gehen Sie insbesondere auf die Größe der Hashtabelle, die Art des Hashverfahrens, die Schlüsselproblematik und den Komprimierungsfaktor ein!

    (b) Implementieren Sie eine Funktion CSingleList::Search(keytype key), die nach einer erfolgreichen Suche in einer einfach verketteten selbstorganisierenden Liste das gefundene Element auskettet und an den Listenanfang schreibt. Gemeint ist nicht der Tausch mit dem Kopfelement! Die Funktion soll außerdem einen Zeiger auf das gefundene Element zurückgeben bzw. NULL, wenn es nicht enthalten war.

    Ich finde die Aufgaben bissl schwierig und kann diese nicht so recht mit meinen Kenntnissen lösen, wäre echt toll, wenn mir da jemand weiterhelfen könnte.

    Viele Grüße und Dank!



  • für (a) musst du dir eigentlich eine hashing methode ausdenken, die einen kollisionsfreien schlüssel für jeweils 3 zahlen berechnet. mit kollisionen ist kein konstanter zugriff mehr möglich.

    für (b) musst du logischerweise erstmal eine einfach verkettete liste implementieren. einfache verkettung heisst, dass jedes element auf seinen nachfolger zeigt. als einstiegspunkt gibt es ein sog. head element, das immer auf das erste element zeigt. hast du also das gesuchte element gefunden, lässt du das head element auf dieses element zeigen, das gefundene element auf das ursprünglich erste und den vorgänger des gefundenen elements auf dessen nachfolger.
    so eine methode Seach zu nennen ist übrigens ein schwerwiegender vertragsbruch in sachen ehrlicher code.



  • zu (b):

    - also ma ne frage, was meinen die mit selbstorganisierenden Liste?
    - also das element ausketten und vorn beim kopf einfügen oder wie? und dann die lücke schließen also zeiger vor ausgekettetem element auf das danach zeigen lassen und wie füge ich das element vorn ein ohne tausch des kopfelement?

    ma ne skizze (so wie ich das versteh):

    head->[3]->[6]->[8]->[9]->NULL (erfundenes Bsp.)
    head->[8]->[3]->[6]->[9]->NULL ("8" ausgekettet und vor eingefügt)

    is das so gemeint?

    und wie realisiere ich das ohne das ich ein element verliere, oder irgendetwas zwischenspeichern muss?

    zu (a):

    wie kann man den mittels hashing das 3d-bild komprimieren? wie realisiere ich das ich solche Voxel oder binärbild erzeuge, heißt das das ich nen schlüssel hab und dann drei koordinaten dort setzen kann, also 3 koordinaten sind in nem Feld als Wert?

    sorry, aber ich habe keine ahnung, wie ich einen schlüssel für 3 zahlen kollisionsfrei berechnen soll

    Kann mir eventuell noch jemand dabei helfen?



  • Gemeint ist nicht der Tausch mit dem Kopfelement!

    der satz sagt, dass nicht [3] und [8] getauscht werden sollen, sondern, wie du es richtig hast, dass [8] vor [3] eingefügt wird. den head pointer musst du natürlich anpassen. [8] ist dann der neue head bzw. das erste element der liste.
    was selbstorganisierend heißt, kann ich dir nicht sagen. klingt mir eher nach einem buzzword.

    komprimiert wird das 3d bild dadurch, dass du nur die gesetzten bits speicherst (im durchschnitt also nur mehr ein n-tel). der schlüssel für die hashtabelle ist möglicherweise die kombination aller drei koordinaten. konstant wird der zugriff aber sicher nicht für alle elemente sein. der schlüssel in die hashtabelle könnte möglicherweise so berechnet werden:

    s = x + (y * N) + (z * N²)
    

    das ergibt für jede koordinate einen eindeutigen schlüssel. das N² kann vorausberechnet werden. du musst hier allerdings auf einen überlauf achten. die hashfunktion muss dann diese werte auf indizes der hashtabelle abbilden. wie man (bzw. ob man) einen kollisionsfreien algorithmus dafür vorausberechnen kann, weiß ich nicht. ich bezweifel aber, dass sowas möglich ist.



  • noch etwas ist mir eingefallen:

    selbst wenn es eine methode gibt, aus einer gegebenen menge an schlüsseln einen algorithmus zu berechnen, der eindeutige indizes erzeugt, so hast du in deinem beispiel diese gegebene menge nicht. es sind alle werte von 0 bis (N - 1) * (1 + N + N²) möglich.



  • selbstorganisierend heisst bei einer liste schlicht, dass sie sich selbst darum kümmert, bei bedarf mehr speicher zu allozieren (und wieder freizugeben).



  • besserwisser schrieb:

    noch etwas ist mir eingefallen:

    selbst wenn es eine methode gibt, aus einer gegebenen menge an schlüsseln einen algorithmus zu berechnen, der eindeutige indizes erzeugt, so hast du in deinem beispiel diese gegebene menge nicht. es sind alle werte von 0 bis (N - 1) * (1 + N + N²) möglich.

    konstanten zugriff bekommst du nur dann hin, wenn der schlüssel sich auf einen eindeutigen index abbilden lässt. eindeutiger index bedeutet in allen mir bekannten sprachen, dass dieser index entweder der index in einem array sein muss oder direkt eine speicheradresse. in beiden fällen lässt sich das nur schwerlich mit der forderung an spärliche besetzung vereinbaren. eine sinnvolle struktur kann zwangsläufig nur logarithmische zugriffszeiten garantieren.



  • Ok, danke erstmal.

    Noch einige Fragen:

    - bei der Schlüsselberechnung beim allgemeinen Hashing gibts folgende Formel: Slotnummer(Hashtabellengröße) = Schlüsselwert % Slotanzahl. Heißt das jetzt das nach der Berechnung von

    s = x + (y * N) + (z * N²)
    

    das s für Schlüsselwert eingesetzt wird? Man sollte doch bei Slotanzahl möglichst eine Primzahl nutzen?

    - komprimiert wird durch speicherung der gesetzten bits, heißt das jetzt das ich die x, y, z bits auch mit nem zeiger implementieren muss? weil wenn ich ein feld mit den x, y, z Koordinaten anlege dann wird ja nicht komprimiert.
    also ich stelle mir das im folgenden vor:

    struct CXYZElement
    {
         keytype key;
         datatype data;
    }
    

    jetzt muss ich doch das data quasi auf x, y, z "pointern" oder? Je nachdem, ob ich x oder y oder z benötige? Wenn das so ist, wie realisiere ich das dann als Code?

    In der Aufgabe steht: "Gehen Sie insbesondere auf die Größe der Hashtabelle, die Art des Hashverfahrens, die Schlüsselproblematik und den Komprimierungsfaktor ein!"

    (a) Größe der Hashtabelle -> wie groß soll denn diese sein?
    (b) Art des Hashverfahrens, was für eine ist denn sinnvoll zu nehmen?
    (c) was denkt ihr meinen die mit Schlüsselproblematik?
    (d) und Komprimierungsfaktor?

    Freu mich auf Antworten 🙂



  • gehen wir mal von dem fall aus, dass du das bild vollständig in einem ideal belegten array von 32 bit integer speicherst. d.h. pro element kannst du 32 bits unterbringen. für ein bild der größe NxNxN benötigst du also genau N^3 bit.

    willst du die daten komprimieren, musst du dir die koordinate eines voxels merken. ist der erlaubte wertebereich pro koordinate wiederrum ein 32 bit integer, brauchst du pro pixel also mind. 96 bit. um konstanten zugriff zu gewährleisten brauchst du pro koordinate aber nochmal maximal 96 bit für die verwaltung. mit einer wirklich guten hashing funktion, die kollisionen minimiert, könnte man mit weniger auskommen. aufgrund der durchschnittlichen belegung eines bildes lässt sich da sicherlich was gutes finden, aber eine garantie auf kollisionsfreiheit erhält man halt nur mit 96 bit: also 192 bit pro voxel.

    so, du kannst das bild also vollständig in N^3 bit speichern. sind nur N^2 voxel belegt, benötigst du mit der "komplizierten" methode 192 * N^2 bit, um dieses zu speichern. jetzt kannst du dir ausrechnen ab welcher größe des bildes die vollständige speicherung mehr platz belegt, als die komplizierte.

    (um es kurz zu machen: ab einer kantenlänge von 193 belegt die komplizierte weniger platz ;))


Anmelden zum Antworten