You are not logged in.

Obi-Wan Kenobi

Praktikant

  • "Obi-Wan Kenobi" started this thread

Posts: 26

Date of registration: May 2nd 2002

1

Friday, December 13th 2002, 12:27pm

D&A, Übung 8

zu Aufgabe 1 a)

Tabelle: 00 01 02 03 04 05 06 07 08 09 10 11 12 13
Tebelle: 14.07.....28 15 36 22 21 08.........11 05 27

kann mir jemand sagen, ob das so richtig ist. ich bin mir nämlich nicht sicher, wann die zweite funktion zu verwenden ist. ist dazu das ergebnis der ersten zu addierenn? was mach ich bei überlauf?
fragen über fragen...

obi-wan ?(

cowhen

Muuuh!

  • "cowhen" is male

Posts: 1,374

Date of registration: Dec 13th 2001

2

Friday, December 13th 2002, 12:43pm

hallo,

ich habe das so verstanden:

die zweite funktion bestimmt die schrittweite. double hashing ist also nur eine variante des linaren hashings, bei dem du bei einer kollision nicht einen schritt weiter gehst, sondern soviel schritte, wie dir die zweite funktion angibt. wenn es also eine kollision gibt.

bsp: du willst ein element an platz 8 einordnen, dieses ist aber schon belegt, dann berechnest du den wert der zweiten fuktion dieser sei jetz mal 3. und dann gehtst du von platz 8 aus 3 schritte weiter.
wenn es dort wieder zu einer kollision kommt denn wieder 3 schritte weiter, bis du auf einen freien platz stößt.

bei mir sieht 1a dann so aus:
0...........................................................13
14 7 - 28 15 36 - 21 8 5 22 11 - 27

hoffe das stimmt so

cowhen
plenty of time to relax when you are dead

Obi-Wan Kenobi

Praktikant

  • "Obi-Wan Kenobi" started this thread

Posts: 26

Date of registration: May 2nd 2002

3

Friday, December 13th 2002, 1:24pm

danke, das ist hilfreich.
und was mach ich beim überlauf? einfach bei position 0 weitermachen? wohl ja...

cowhen

Muuuh!

  • "cowhen" is male

Posts: 1,374

Date of registration: Dec 13th 2001

4

Friday, December 13th 2002, 2:08pm

Quoted

von obiwan: einfach bei position 0 weitermachen? wohl ja...
genau.




nun hab ich auchnoch eine frage: wie berechne ich denn die mittleren zugriffszahlen? das durchschaue ich irgendwie noch nicht


thx

cowhen
plenty of time to relax when you are dead

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

5

Friday, December 13th 2002, 4:50pm

erfolgreiche Suche

Für die erfolgreiche Suche habe ich herausgefunden, dass man die Anzahl der Vergleiche durch die Anzahl der Elemente dividieren muss. Also, wenn man eine Tabelle erstellt, dann daneben am besten noch einen Strich für den Tabellenzugriff machen, dann alle Striche aufaddieren und hier durch 11 teilen. Dann habe ich bei Aufgabe 1a 21 Tabellenzugriffe(vergleiche), durch 11 dividieren, erhält man 1,90909.... für die erfolgreiche Suche.
Wie man aber die nicht erfolgreiche Suche berechnet, weiß ich auch nicht.
mfg
MAX

Diktator

Senior Schreiberling

  • "Diktator" is male

Posts: 605

Date of registration: Feb 12th 2002

Location: Region Hannover

Occupation: Gartenbau

6

Friday, December 13th 2002, 5:02pm

error
Diktator
Holzhacken ist deshalb so beliebt, weil man bei dieser Tätigkeit den Erfolg sofort sieht. - Albert Einstein

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

7

Friday, December 13th 2002, 5:12pm

ich schaue und schaue...

...und schaue, aber kann nichts finden!!! Wir haben hier nicht mit Wahrscheinlichkeiten zu tun! Ich finde im Skript keine geeignete Formel dazu.
Aber durch Ausprobieren kam ich auf folgendes:
Nicht erfolgreiche Suche:=(h1(M-1)+M*h2(M-1)+Anzahl der Elemente)/Anzahl der Elemente
Ich kam dabei auf 3,454545....
Kann das jemand bestätigen/widerlegen???
mfg
MAX

Zypressen Hügel

Junior Schreiberling

Posts: 244

Date of registration: Dec 22nd 2001

8

Friday, December 13th 2002, 6:50pm

die genaue zahl lässt sich nur berechnen, indem man jede mögliche nicht erfolgreiche suche ausprobiert, also im wesentlichen ab jedem (besetzten) tabellenplatz jede mögliche zweite hashfunktion (also schrittweiten von 2 bis 13) durchprobiert, bis man periodisch wieder am ausgangsplatz ankommt. das ganze mitgezählt und alles aufsummiert ergibt den entsprechenden aufwand. lässt sich wahrscheinlich am ehesten durch ein kleines programm durchspielen, bevor man das zu fuß probiert...
Man kann auch ohne Spass Alkohol haben 8)

cowhen

Muuuh!

  • "cowhen" is male

Posts: 1,374

Date of registration: Dec 13th 2001

9

Friday, December 13th 2002, 6:54pm

also ich habe jetz für die erfolgreiche suche folgendes rausbekommen:
a) 1,90
b)1,63
c)1,45

hat das irgendwer auch so?

mfg

cowhen
plenty of time to relax when you are dead

compost

Trainee

  • "compost" is male

Posts: 74

Date of registration: Dec 11th 2001

Location: Linden

10

Friday, December 13th 2002, 8:10pm

@cowhen

also 1,9 bei aufgabe 1a habe ich auch. bei teil b weiss ich nicht genau wie ich das berechnen soll. hatte da zwischenzeitlich mal 1,41 heraus. wie hast du das denn gemacht?


gruss Jens

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

11

Friday, December 13th 2002, 8:19pm

hmm...

@cowhen
Habe auch so
@Zypressen Hügel
Ich verstehe nicht ganz, was du meinst. Kannst du etwas ausführlicher erklären?
mfg
MAX

BlaueMotte

Trainee

  • "BlaueMotte" is female

Posts: 76

Date of registration: Apr 9th 2002

Location: vom platten Land mit Nordseeluft

Occupation: hä? Studi...

12

Monday, December 16th 2002, 4:27pm

Erfolgreiche Suche ist ja noch okay, aber erfolglose? Hat da schon jemand ein Ergebnis? Oder ein Programm?

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

13

Monday, December 16th 2002, 4:40pm

Die Idee hinter der Berechnung des mittleren Aufwandes für die erfolglose Suche ist folgende:

Die Anzahl der Tabellenzugriffe, die man benötigt, um festzustellen, daß ein bestimmtes Element, von dem der Wert der primären und sekundären Hashfunktion bekannt ist, nicht in der Tabelle enthalten ist, sollte einfach zu ermitteln sein (Tabelle solange durchgehen bis man entweder einen leeren Tabellenplatz findet oder am Ausgangspunkt der Suche angekommen ist).

Nun interessiert uns aber der *durchschnittliche* Aufwand, den man benötigt, um festzustellen, daß ein Element nicht in der Tabelle enthalten ist. Dazu müßte man prinzipiell *alle* (sind leider unendlich viele) nicht enthaltenen Elemente durchprobieren und für jedes den o. g. Aufwand ermitteln. Die Gesamtsumme der Tabellenzugriffe teilt man dann durch die Anzahl der geprüften Elemente und hat damit den gesuchten Mittelwert.

Da man aber nicht unendlich viele Elemente durchprobieren kann, nutzt man aus, daß bei diesen unendlich vielen Elementen jede Kombination von Starttabellenplatz und Schrittweite (also Ergebnis der primären und sekundären Hashfunktion) gleichwahrscheinlich ist (ergibt sich aus den Anforderungen, die wir an die Hashfunktionen gestellt haben). Also kann man einfach den Aufwand für alle möglichen Kombinationen von Starttabellenplatz und Schrittweite berechnen (sind in diesem Fall 14 * 13 Möglichkeiten) und die Gesamtsumme durch die Anzahl der Summanden teilen -- auf diese Weise erhält man dann den gesuchten Mittelwert. Da man bei 14 * 13 = 182 Möglichkeiten per Hand natürlich recht langer beschäftigt wäre, bietet sich hier natürlich ein selbstgeschriebenes Programm an (ist nicht kompliziert, drei verschachtelte Schleifen und ein bißchen Zählerei sollten genügen).

Ich komme auf folgende Zahlen:
a) 3,85
b) 3,50
c) 3,81

(Achtung: Ich habe die Zahlen leicht verändert (Abweichung +- 0,02), um nicht die Ergebnisse vorher zu verraten. Das Programm müßt ihr also schon selber schreiben ;) )
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

spehler62

Praktikant

Posts: 17

Date of registration: Aug 6th 2002

14

Monday, December 16th 2002, 8:57pm

@Joachim

hast du jetzt für die nicht_erfolgreiche suche drei verschiedene ergebnisse ??

habe nämlich nachgerechnet und habe verschiedene ergebnisse - es soll aber immer das gleiche rauskommen
"Ein Mann, der Kinder und Hunde hasst, kann nicht durch und durch schlecht sein." W.C.Fields

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

15

Monday, December 16th 2002, 8:59pm

Quoted

Original von spehler62
es soll aber immer das gleiche rauskommen
Wer sagt das?
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

spehler62

Praktikant

Posts: 17

Date of registration: Aug 6th 2002

16

Monday, December 16th 2002, 9:07pm

Über sieben-ecken gehört :)
hat sich jemand von Niklas erklären lassen und der meinte überall kommt dasselbe raus
"Ein Mann, der Kinder und Hunde hasst, kann nicht durch und durch schlecht sein." W.C.Fields

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

17

Monday, December 16th 2002, 9:37pm

Quoted

Original von spehler62
Über sieben-ecken gehört :)
hat sich jemand von Niklas erklären lassen und der meinte überall kommt dasselbe raus
Kann ich nicht bestätigen. Ich habe eben mein Programm nochmal genau überprüft und auch eine alternative Implementierung verwendet, komme jedoch auf die selben Ergebnisse wie vorher.

Im allgemeinen ist der mittlere Aufwand bei der nicht erfolgreichen Suche jedenfalls nicht bei allen Anordnungen der Elemente derselbe (wenn man von konstanter Tabellengröße und konstanter Elementzahl ausgeht). Ich habe nämlich zwei einfache Fälle gefunden (Tabellengröße sechs), die ich per Hand auszählen konnte und die einen unterschiedlichen mittleren Aufwand haben.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

spehler62

Praktikant

Posts: 17

Date of registration: Aug 6th 2002

18

Monday, December 16th 2002, 10:38pm

okay,danke für deine mühe.
Hätte ja auch sein können, dass du einen kleinen fehler in deinem programm hattest. Mal schauen was die musterlösung sagt.
"Ein Mann, der Kinder und Hunde hasst, kann nicht durch und durch schlecht sein." W.C.Fields

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

19

Tuesday, December 17th 2002, 12:02pm

Quoted

Original von spehler62
Über sieben-ecken gehört :)
hat sich jemand von Niklas erklären lassen und der meinte überall kommt dasselbe raus


So so, über sieben Ecken... Gemahnt an "Stille Post" ;)
Wenn ich das gesagt wirklich habe, kann ich mich jetzt nicht mehr daran erinnern. Ist auch falsch: Bei der gegebenen Tabelle kommen definitiv verschiedene Werte heraus. Vielleicht kam das Mißverständnis zustande, weil es im letzten Jahr anders war.

spehler62

Praktikant

Posts: 17

Date of registration: Aug 6th 2002

20

Tuesday, December 17th 2002, 9:02pm

@np
naja, ich geb' ja zu die sieben Ecken sind eher eine Gerade :D
Zu ihm meintes du, dass bei allen drei Tabellen dasselbe Ergebnis für die nicht_erfolgreiche_Suche rauskommen soll und ich glaube nicht, dass er dich so sehr mißverstanden hat.
"Ein Mann, der Kinder und Hunde hasst, kann nicht durch und durch schlecht sein." W.C.Fields