Lösungsstrategie für foo #4

h_ar
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 16. Apr 2015 19:56

Lösungsstrategie für foo #4

Beitrag von h_ar »

Hat jemand bei diesem schweren foo-Testat eine Strategie?
Ich und sicherlich viele andere wären dankbar über jeden Tipp.

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

Re: Lösungsstrategie für foo #4

Beitrag von KaeferZuechter »

Ich hatte gerade das Testat.

a) Double-Hashing ist sehr einfach (lösbar unter 1 Minute)
1. Bei jeder Gelegenheit modulo rechnen um die Zahlen klein zu halten
2. Zahlen nahe n kann man auch durch ihre kleinen negativen Gegenstücke ersetzen
3. Die zweite Hashfunktion ist hier immer \(2\cdot k \mod n\)

b) BTree delete ist schwieriger, jedoch ebenfalls nicht sondernlich aufwendig (lösbar in etwa 2-3 Minuten selbst bei "schwierigen" Fällen)
1. Wenn das Kind auf das man hinabsteigen will nur M (sprich: 1) Schlüssel hat:
1.1 Versuche mit rechtem Nachbarn zu rotieren/shiften
1.2 Sonst versuche mit rechtem Nachbarn zu mergen
1.3 Sonst versuche mit linkem Nachbarn zu rotieren/shiften
1.4 Sonst versuche mit linkem Nachbarn zu mergen
2. Wenn der zu löschende Schlüssel gefunden ist, ersetze durch Vorgänger und lösche Vorgänger (1 Wert überschreiben)
3. Wenn der zu löschende Schlüssel in einem Blatt ist, entferne ihn einfach (1 Wert löschen)

Rotieren (Nachbar muss mehr als M Schlüssel besitzen):
1. Verschiebe den Elterschlüssel in das minimale Kind A (1 Wert eintragen und löschen)
2. Verschiebe den Nachbarschlüssel aus dem anderen Kind B in das Elter (1 Wert eintragen und löschen)
3. Verschiebe das mittlere Enkel von B nach A (1 Kante ID und Index ändern)
4. Korrigiere Indizes in B (bis zu 3 Indizes ändern)

Mergen:
1. Ziehe Kinderschlüssel in das Elter (2 Werte eintragen)
2. Lösche Kinderknoten und Verknüpfungen zu selbigen (2 Knoten und 2 Kanten löschen)
3. Verknüpfe frühere Enkel direkt mit Elter (in 4 Kanten ID und Index ändern)

Foo erklärt bei der BTree-Korrektur eigentlich perfekt, was zu tun ist.
Man muss beim Löschen übrigens niemals Knoten oder Kanten erstellen.
Zuletzt geändert von KaeferZuechter am 26. Jun 2015 14:00, insgesamt 1-mal geändert.
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Lösungsstrategie für foo #4

Beitrag von Nullmann »

KaeferZuechter hat geschrieben: a) Double-Hashing ist sehr einfach (lösbar unter 1 Minute)
1. Bei jeder Gelegenheit modulo rechnen um die Zahlen klein zu halten
Immer benutzen, egal wann!

Mir hat es geholfen, die ersten 5 Multiplikationen zuerst hinzuschreiben, um so einfacher die Modulo-Rechnungen durchführen zu könnnen.
Bsp:
Bei n = 12 habe ich mir aufgeschrieben:
12|24|36|48|60

Selbst bei "großen" Zahlen wie 56 lässt sich so einfach ablesen, dass 58 mod 12 = 56-48 = 8 ist. Die 48 wurde hier genommen, weil sie die größte Zahl in der Reihe, aber nicht größer ist.

B-Tree:

Generell gilt: Wenn man den zu löschenden Key sucht oder diesen mit dem direkten Vorgänger (erst eins nach links, dann immer nach rechts herabsteigen) tauschen möchte, darf man nur hinabsteigen, wenn der jeweilige Knoten mehr als einen Key besitzt. Ansonsten muss Merge oder Rotate eingesetzt werden.
KaeferZuechter hat geschrieben: 1.1 Versuche mit rechtem Nachbarn zu rotieren/shiften
1.2 Sonst versuche mit linkem Nachbarn zu rotieren/shiften
1.3 Sonst versuche mit rechtem Nachbarn zu mergen
1.4 Sonst versuche mit linkem Nachbarn zu mergen
Dieser Reihenfolge kann ich so nicht zustimmen. Es wird immer erst versucht, mit dem rechten Nachbarn zu mergen (falls Anzahl keys = 1) oder zu rotaten (falls Anzahl keys > 1). Nur, wenn kein rechter Nachbar existiert, wird der linke Nachbar genommen. Sodass sich ergibt:

Zusätzlich: Bei so ziemlich jeder Aufgabe muss die Höhe verringert werden, also findet ein Merge an der Wurzel statt. Dies ist der Fall, wenn Sowohl die Wurzel als auch beide Knoten nur einen Key besitzen.
KaeferZuechter hat geschrieben:Foo erklärt bei der BTree-Korrektur eigentlich perfekt, was zu tun ist.
Dem kann ich so vollkommen zustimmen.

"Spezialfälle" von Rotate und Merge sind diese, welche eine "Zwischenebene" darstellen, also sowohl Eltern als auch Kinder besitzen. Bei diesen muss man aufpassen, dass man sowohl die Referenzen auf diese Knoten von den Eltern, als auch die Referenzen von diesen Knoten zu ihren Kindern ändert.

Mfg,
Nullmann

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

Re: Lösungsstrategie für foo #4

Beitrag von KaeferZuechter »

Nullmann hat geschrieben:B-Tree:

Generell gilt: Wenn man den zu löschenden Key sucht oder diesen mit dem direkten Vorgänger (erst eins nach links, dann immer nach rechts herabsteigen) tauschen möchte, darf man nur hinabsteigen, wenn der jeweilige Knoten mehr als einen Key besitzt. Ansonsten muss Merge oder Rotate eingesetzt werden.
KaeferZuechter hat geschrieben: 1.1 Versuche mit rechtem Nachbarn zu rotieren/shiften
1.2 Sonst versuche mit linkem Nachbarn zu rotieren/shiften
1.3 Sonst versuche mit rechtem Nachbarn zu mergen
1.4 Sonst versuche mit linkem Nachbarn zu mergen
Dieser Reihenfolge kann ich so nicht zustimmen. Es wird immer erst versucht, mit dem rechten Nachbarn zu mergen (falls Anzahl keys = 1) oder zu rotaten (falls Anzahl keys > 1). Nur, wenn kein rechter Nachbar existiert, wird der linke Nachbar genommen. Sodass sich ergibt:
Danke! Da habe ich Unsinn geschrieben und es jetzt oben korrigiert.
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

h_ar
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 16. Apr 2015 19:56

Re: Lösungsstrategie für foo #4

Beitrag von h_ar »

Danke! :)

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

Re: Lösungsstrategie für foo #4

Beitrag von Smith »

KaeferZuechter hat geschrieben:1. Wenn das Kind auf das man hinabsteigen will nur M (sprich: 1) Schlüssel hat:
1.1 Versuche mit rechtem Nachbarn zu rotieren/shiften
1.2 Sonst versuche mit rechtem Nachbarn zu mergen
1.3 Sonst versuche mit linkem Nachbarn zu rotieren/shiften
1.4 Sonst versuche mit linkem Nachbarn zu mergen
2. Wenn der zu löschende Schlüssel gefunden ist, ersetze durch Vorgänger und lösche Vorgänger (1 Wert überschreiben)
3. Wenn der zu löschende Schlüssel in einem Blatt ist, entferne ihn einfach (1 Wert löschen)
Aus den Lernvideos geht meiner Meinung nach hervor, dass ein Merge einem Shift vorzuziehen ist.
Wäre denn nicht diese Reihenfolge die korrekte?:

1.1 Versuche mit rechtem Nachbarn zu mergen
1.2 Sonst versuche mit rechtem Nachbarn zu rotieren/shiften
1.3 Sonst versuche mit linkem Nachbarn zu mergen
1.4 Sonst versuche mit linkem Nachbarn zu rotieren/shiften
2. Wenn der zu löschende Schlüssel gefunden ist, ersetze durch Vorgänger und lösche Vorgänger (1 Wert überschreiben)
3. Wenn der zu löschende Schlüssel in einem Blatt ist, entferne ihn einfach (1 Wert löschen)

Übersehe/missverstehe ich hier etwas?
Phil

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

Re: Lösungsstrategie für foo #4

Beitrag von KaeferZuechter »

Merge funktioniert nur, wenn der Nachbar höchstens M Schlüssel enthält und Shift in die gleiche Richtung funktioniert nur für mehr als M Schlüssel.
Die Fälle schließen sich aus und damit ist deren Reihenfolge egal (sofern man wie in Foo arbeitet und nicht wie im oben zitierten, unkorrigierten Post).
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

Re: Lösungsstrategie für foo #4

Beitrag von Smith »

Danke, das macht Sinn : )
Phil

Antworten

Zurück zu „Archiv“