3. Streufunktion

Streufunktion

  • ?

    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..

    0
  • F

    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.ä.

    0
  • ?

    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...

    0
  • ?

    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. 🙂

    0
  • F

    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]

    0
  • ?

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

    0
  • ?

    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!

    0
  • M

    re

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

    Meep Meep

    0
  • M

    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

    0
  • ?

    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. 🙂

    0
  • M

    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

    0
  • ?

    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.

    0
Anmelden zum Antworten