[FRAGE] - Verbesserung nach Brent
Results 1 to 7 of 7
  1. #1
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Verbesserung nach Brent

    kann hier bitte mal wer die verbesserung nach brent verständlich erklären?

    ... wäre echt genial, die erklärung im skriptum is a scherz

    mfg,
    -z0nk-

  2. #2

    Title
    Principal
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    79
    Thanks
    0
    Thanked 0 Times in 0 Posts
    aaalso...bei der Verbesserung nach Brent wird beim Double Hashing nicht nur für den Wert der eingefügt werden soll sondern auch für den Wert der bereits an der vorgesehenen Position steht h(k,i)=(h1(k)+i.h2(k)) mod m berechnet.

    Bsp.: Hashtab mit
    7 steht bereits an Stelle 8
    20 soll eingefügt werden -> auch an Stelle 8

    also berechnet man für beide Zahlen h(k,i)=(h1(k)+i.h2(k)) mod m

    dann kann man sich aussuchen ob man jetzt die 20 an eine andere Stelle setzten möchte, oder die 7 verschiebt und die 20 an Stelle 8 einfügt.


    Sinn macht das ganze zBsp:: wenn so eine HTabelle geg. wäre
    |0|1|2|3|
    |a|b|c| | -> d soll eingefügt werden -> würde an Stelle 0 landen (schon besetzt) -> man rechnet mit normalem Double Hashing weiter -> d würde an Stelle 1 landen (auch schon besetzt) usw.

    wenn man jetzt aber Brent verwendet, und für a mit h(k,i)=(h1(k)+i.h2(k)) mod m errechnen würde das es an Stelle 3 eingefügt werden kann, erspart man sich einige Schritte, weil man d einfach an Stelle 0 einfügen kann.

    Hoffe das is jetzt nicht zu kompliziert erklärt Ich würd mir an deiner Stelle ne Mitschrift vom letzten Repetitorium besorgen da wurde das sehr gut erklärt.

    out

  3. #3
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    danke ! .. habs schon gecheckt

  4. #4
    tricipitinus's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Purkersdorf bei Wien
    Posts
    598
    Thanks
    0
    Thanked 0 Times in 0 Posts
    was ich mich immer frage, und v.a. bei Brent:
    wie kann ich solche "entscheidungen" nacher beim suchen der schlüssel nachvollziehen?!?

    der aufwand beim einfügen ma ja geringer sein, aber beim suchen muss ich dafür jedesmal beide hashwerte ausrechnen
    ash nazg durbatulûk, ash nazg gimbatul,
    ash nazg thrakatulûk, agh burzum-ishi krimpatul.

  5. #5

    Title
    Baccalaureus
    Join Date
    Mar 2005
    Location
    Wien
    Posts
    953
    Thanks
    58
    Thanked 22 Times in 13 Posts
    Nein, der Aufwand beim Suchen ist geringer. Das steht eh auch im Skriptum: "Für alle Fälle, bei denen häufiger gesucht als eingefügt wird, ist es von Vorteil, die Schlüssel beim Einfügen so zu reorganisieren, dass die Suchzeit verkürzt wird."
    Und beim Beispiel im Skriptum kann man auch schön sehen, dass man weniger oft suchen muss.

  6. #6
    ska's Avatar
    Title
    Baccalaureus
    Join Date
    Oct 2005
    Location
    1060 Wien
    Posts
    647
    Thanks
    10
    Thanked 0 Times in 0 Posts
    ähm-kommt das auch zum Übungstest am Mi?
    Die Zeit heilt alle Wunder!!!

    Fotografie hält diese Wunder fest...
    http://DI-fotografin.at

  7. #7
    tricipitinus's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Purkersdorf bei Wien
    Posts
    598
    Thanks
    0
    Thanked 0 Times in 0 Posts
    vermutlich nicht, aber zum VO test am freitag ^^
    ash nazg durbatulûk, ash nazg gimbatul,
    ash nazg thrakatulûk, agh burzum-ishi krimpatul.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •