Streufunktion



  • Ich hab mir eine Streufunktion überlegt, die Elemente anhand ihrer ID gleichmäßig verstreut. Der Zielort sei jetzt mal ein Bereich von 0 bis 1, wobei 1 wieder 0 entspricht, ist also zyklisch. (In Wirklichkeit hat er einen anderen Wertebereich).
    Das erste Element (id = 0) steht bei 0 (bzw. 1), das zweite bei 0.5, das dritte bei 0.25, das vierte bei 0.75, dann 0.125, 0.375, 0.625, usw.

    Ich denke, das System wird sofort klar, wenn man sich die ersten Punkte aufzeichnet. Ich habe aber bisher keinen Algorithmus dazu gefunden, der mir das n-te Element in konstanter Zeit liefert. Irgendwas mit (in Abhängigkeit von n)-mal durch 2 teilen (rechts shiften) wird wohl drin sein, wobei ich mir schon nicht sicher bin, ob das überhaupt noch konstant ist. Wie ich aber auf die genaue Position komme, ist mir ein Rätsel. Wenn es sauschnell ist, reicht es mir auch noch. Mein größtes n ist um die 10.000 rum, also wäre konstante Zeit schon wirklich das feinste.

    Wenn das nicht möglich ist, was gibt es noch für Streu-Algorithmen, die wirklich sehr gleichmäßig verteilen und gleiche Codes weit auseinanderlegen? Im Java API hab ich noch ne Funktion gefunden, die vorhandene Hashcodes weiter verteilen soll, die ist auch effizient zu berechnen, aber verteilt irgendwie nicht so gleichmäßig.



  • hoi optimizer

    vielleicht hilft dir das ja ein bisschen weiter

    als beispiel die zahl 23:
    hoechstes bit berechnen:

    unsigned int HighestBit(register unsigned int x)
       {
          x |= (x >> 1);
          x |= (x >> 2);
          x |= (x >> 4);
          x |= (x >> 8);
          x |= (x >> 16);
          return x & ~(x >> 1);
       }
    

    kommt in unserem fall kommt 16 raus.
    1 / 16 = 0.0625; <- eine einheit;
    deine position von 23 waere dann 0.0625 * (23 - 16) = 0.4375

    ob das nun gaaaaaanz genau stimt weiß ich grad net. aber so ungefaehr koennte es hinkommen.

    Meep Meep



  • Ich hätte auch einen Vorschlag:

    f := proc(i::posint) local k,l;
     k := 2^floor(log[2](i));
     l := (i mod k)+1/2;
     l/k; 
    end proc;
    

    Dann liefert

    L := NULL:
    for i from 1 to 20 
    do
     L := L, f(i);
    od:
    L;
    

    1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, 1/16, 3/16, 5/16, 7/16, 9/16, 11/16, 13/16, 15/16, 1/32, 3/32, 5/32, 7/32, 9/32

    HTH



  • Danke euch beiden.

    @Meep Meep: Von der Idee her eigentlich cool, aber es kommt leider nicht so ganz das richtige raus. 😞 Ich hab natürlich schon aufgepasst, dass durch die Integer-Arithmetik nichts kaputt geht.

    timeHash(1000, 0) 'timeHash(1000, 0)' threw an exception of type 'System.DivideByZeroException' long {System.DivideByZeroException}
    timeHash(1000, 1) 0 long
    timeHash(1000, 2) 0 long
    timeHash(1000, 3) 500 long
    timeHash(1000, 4) 0 long
    timeHash(1000, 5) 250 long
    timeHash(1000, 6) 500 long
    timeHash(1000, 7) 750 long

    Das id - HighestBit ergibt bei jeder 2er Potenz 0. Vielleicht habe ich dich nicht richtig verstanden?

    @fubar: Falls ich jetzt nichts übersehen habe, fürchte ich, dass der log[2] zu böse ist. Trotzdem danke.

    Ich fang langsam an, daran zu zweifeln, dass man das überhaupt in konstanter Zeit machen kann..



  • Warum ist log[2] zu böse?
    Aber k := 2^floor(log[2](i)) kann man natürlich noch wegoptimieren. Z.B. mit k := 2^HighestBit o.ä.



  • Stimmt. Ich denk mir, dann ist es nicht mehr viel von Meep Meep's Lösung verschieden, die Ergebnisse sind anscheinend auch gleich. War das so in deinem Sinne? area ist hier der Wertebereich also im Beispiel 1000.

    public long timeHash(long area, long id)
    		{
    			long k = HighestBit(id);
    			long l = (id % k)+1/2;
    			return l*area / k;
    		}
    

    Alles in allem schon weiter, als ich selber gekommen bin, aber leider wiederholen sich die Werte zu oft (z.B. 500 kommt immer wieder vor), weil die immer wieder abgegrast werden und nicht übersprungen. Und die 0 bei 2er-Potenzen natürlich...



  • Im Notfall werd ich die Streufunktion aus dem Java API nehmen, so schlecht verteilt sie eigentlich doch nicht. Ich brauch halt dann nen Modulo für meinen Wertebereich, ne Division haben wir hier aber auch schon. Führt halt definitiv ab und zu zu Kollisionen, was ich vermeiden wollte, aber ein Weltuntergang ist es nicht.
    Wenn ihr aber noch eine Idee hättet, wie man die oben genannte Vorgehensweise oder eine ähnliche umsetzen könnte, interessiert es mich immer noch. 🙂



  • Deine highestBit-Funktion scheint fehlerhaft zu sein. Bei mir liefert die Funktion 0 1 2 2 4 4 4 4 8 8 8 8 8 8 8 8 16 16 16 16 ...
    Edit:
    [cpp]
    long l = (id % k)+1/2; // hier könnte auch der Fehler liegen
    [/cpp]



  • Bei mir auch, ich hab nen Fehler beim Übersetzen nach C# gemacht. Moment...



  • Genau das hab ich auch grad gesehen. 😃 War ja mal wieder richtig peinlich. 🙄

    Das Ergebnis schaut sehr gut aus, um nicht zu sagen, das ist es. Vielen Dank euch beiden!



  • re

    das funktioniert sogar ohne division oder modulo. bin grad am testen. stell dann noch den source rein

    Meep Meep



  • re

    neue version:
    als bereich hab ich mal 1000´000´000 genommen, wegen den kommastellen

    inline unsigned int HighestBit(register unsigned int x)
       {
          x |= (x >> 1);
          x |= (x >> 2);
          x |= (x >> 4);
          x |= (x >> 8);
          x |= (x >> 16);
          return x & ~(x >> 1);
       }
    
       inline unsigned int HighestBitCount(register unsigned int x)
       {
    
          const unsigned int b[] = {0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 
                                    0xFFFF0000};
          register unsigned int c = (x & b[0]) != 0;
    
          c |= ((x & b[4]) != 0) << 4;
          c |= ((x & b[3]) != 0) << 3;
          c |= ((x & b[2]) != 0) << 2;
          c |= ((x & b[1]) != 0) << 1;
    
          return c;
       }
    
    unsigned int calc_pos(unsigned int value)
    {
       const unsigned int range(1000000000);
       unsigned int k = HighestBit(value);
       unsigned int einheit = range >> HighestBitCount(k);
       return (einheit >> 1) + (einheit * (i - k));
    }
    

    habs mal bei mir ausgemessen. braucht rund 65 ticks fuer die berechnung einer position. kann man bestimmt noch paar ticks einsparen.

    Meep Meep

    PS: wenn ich

    unsigned int einheit = range >> HighestBitCount(k);
    

    gegen eine normae division eintausche, braucht der algo nur noch 60 Ticks. also is die HighestBitCount funktion doch nur mist



  • Das muss ich mir Morgen nochmal ansehen. Evtl. muss der Algorithmus auch noch mal verbessert werden (also nicht die Implementierung). Die Idee find ich nach wie vor nicht schlecht, weil für einen Wertebereich >= n keine Kollisionen auftreten. Aber die Streuung ist noch nicht so wirklich geil. Besser wäre es, die Zwischenwerte dann nicht in der Reihenfolge ihrer Werte zu nehmen. Das wär dann etwas, wo ich nochmal darüber nachdenken müsste. Vielleicht find ich auch noch was brauchbares im Internet. Für feste Wertebereiche und vor allem feste Eingabewerte gibt es bestimmt spezielle Streufunktionen.

    Aber jetzt ist es schon spät und ich werde alt. Danke, nochmal. 🙂



  • hola

    wofuer brauchst du die funktion eigendlich ?
    ist die anzahl der werte von anfang an bekannt, oder erhoehen die sich im laufe der zeit. kann man bei erhoehung der werte eventuell die gesammt streuung neuberechnen ? in dem fall koennte man zu mindest eine symetrischere streuung zusammen bekommen.

    Meep Meep



  • Ich muss mehrere aufwändige Berechnungen immer wieder durchführen. Wenn ich sie in der Reihenfolge, in der sie reinkommen durchführe, hab ich einmal nen Riesenbatzen Arbeit und einmal fast nichts zu tun und durch das Streuen versuche ich, das möglichst gleichmäßig zu verteilen.
    Die zu streuenden Werte ändern sich mit der Zeit, aber nicht in einer Weise, die man voraussagen könnte. Deshalb bin ich jetzt langsam gar nicht mehr überzeugt, dass es gut ist, so gleichmäßig zu streuen. Irgendwas völlig chaotisches ist glaub ich besser. Sorry, dass ich dir Mühe gemacht habe, aber ich werde jetzt wahrscheinlich einfach die Funktion hier nehmen:

    value += ~(value << 9);
    			value ^=  (value >> 14);
    			value +=  (value << 4);
    			value ^=  (value >> 10);
    			return value;
    

    Die streut schon ganz geil und hat relativ wenig Kollisionen für meine Anwendung.


Log in to reply