Streufunktion

fubar

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.

fubar

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!

Meep Meep

re

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

Meep Meep

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.

Meep Meep

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.