Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Bit-Gruppen zählen
Bergmann89 - Mi 03.08.16 20:43
Titel: Bit-Gruppen zählen
Hey Leute,
ich hab in einem meiner Projekte ein kleines Perfomance Problem. Und zwar hab ich eine 13 Stellen lange Zeichenfolge mit den Zeichen [0, 1, 2]. Die Zeichen hab ich der Reihe nach mit je 2 Bit in einem uint32 abgelegt. Jetzt würde ich gern den Hamming-Abstand von 2 verschiedenen Zeichenfolgen ermitteln. Zur Zeit mach ich da ein xor und zähle dann alle BitGruppen die ungleich 0 sind.
Kleines Beispiel:
Quelltext
1:
2:
3:
4:
5:
6:
7:
| Folge 1: 0102120120120
Folge 2: 0120021201200
Bitmaske zu 1: 00 01 00 10 01 10 00 01 10 00 01 10 00
Bitmaske zu 2: 00 01 10 00 00 10 01 10 00 01 10 00 00
XOR 00 00 10 10 01 00 01 11 10 01 11 10 00
Unterschied: 9 |
Code dazu:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| var
dif: Cardinal;
i: Integer;
begin
result := 0;
dif := t1 xor t2;
for i := 0 to aGameCount-1 do
if GetTipChar(dif, i) <> 0 then
inc(result); |
Ich hatte gehofft sowas wie
hier [
http://gurmeet.net/puzzles/fast-bit-counting-routines/] zu finden, aber meine Suche war bis jetzt erfolglos. Oder kann man vieleicht das MIT HAKMEM Count auf mein Problem anpassen? Hat jmd von euch einen Rat für mich?
MfG & Thx Bergmann89
BenBE - Mi 03.08.16 21:55
Wenn Du die Werte mit je 2 Bit Platz ablegst, sollte es mit einer Addition, 1 Or, sowie 1 And als Vorbereitung für den schnellen Bitcount gehen.
Idee:
Quelltext
1:
2:
3:
4:
| ? 00 - ? 01 - ? 10 - ? 00 - ? 01 - ? 10 - ? 00 - ? 01 - ? 10
? 00 - ? 01 - ? 10 - ? 01 - ? 10 - ? 00 - ? 10 - ? 00 - ? 01
------------------------------------------------------------
? 00 - ? 00 - ? 00 - ? 01 - ? 11 - ? 10 - ? 10 - ? 01 - ? 11 |
Nehmen wir jetzt an, die ? sind alle 0, kann man folgende Verschiebung machen:
Quelltext
1:
2:
3:
4:
| 000 - 000 - 000 - 001 - 011 - 010 - 010 - 001 - 011
000 - 000 - 000 - 001 - 011 - 010 - 010 - 001 - 011
----------------------------------------------------
000 000 000 011 111 110 110 011 111 |
Und welch ein Zufall, dass jetzt das 2. Bit jeder Gruppe 1 ist, wenn die Gruppe ungleich 0 war ...
Quelltext
1:
2:
3:
4:
| 000 000 000 011 111 110 110 011 111
010 010 010 010 010 010 010 010 010
----------------------------------------------------
000 000 000 010 010 010 010 010 010 |
Das Bitcount geht dann
absolut einfach [
https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel]:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
| 000 000 000 010 010 010 010 010 010
->
???? ?000 0000 0001 0010 0100 1001 0010
-----------------------------------------
???? ?000 0000 0001 0010 0100 1001 0010
??? ??00 0000 0000 1001 0010 0100 1001
& 000 0001 0101 0101 0101 0101 0101 0101
----------------------------------------
- 000 0000 0000 0000 0001 0000 0100 0001
-----------------------------------------
???? ?000 0000 0001 0001 0100 0101 0001
?? ???0 0000 0000 0100 0101 0001 0100
& 000 0001 0011 0011 0011 0011 0011 0011
----------------------------------------
+ 000 0000 0000 0000 0000 0001 0001 0000
-----------------------------------------
???? ?000 0000 0001 0001 0001 0010 0001
???? ?000 0000 0001 0001 0001 0010
& 000 0111 0000 1111 0000 1111 0000 1111
----------------------------------------
+ 000 0000 0000 0000 0000 0001 0000 0010
-----------------------------------------
???? ?000 0000 0001 0000 0010 0000 0011
???? ?000 0000 0001 0000 0010
& 000 0000 0000 0111 0000 0000 1111 1111
----------------------------------------
+ 000 0000 0000 0000 0000 0000 0000 0010
-----------------------------------------
???? ?000 0000 0001 0000 0000 0000 0101
???? ?000 0000 0001
& 000 0000 0000 0000 1111 1111 1111 1111
----------------------------------------
+ 000 0000 0000 0000 0000 0000 0000 0001
-----------------------------------------
???? ?000 0000 0000 0000 0000 0000 0110
& 0000 0000 0000 0000 0000 0000 0011 1111
=========================================
= ???? ???? ???? ???? ???? ???? ??00 0110 |
Bei den Additionen kommt vorher noch jeweils eine Maskierung mit der gleichen Maske (ohne Verschiebung) dazu, die ich grad mal rausgelassen hab. In ASM gehackt sollte sich das aber extrem schnell hacken lassen; aktuelle CPUs haben mit POPCNT speziell ne Instruktion dafür.
Ich komm grad auf ~21 Instruktionen, wenn ich mich nicht verzählt hab.
BenBE - Mi 03.08.16 22:06
Wobei mir bei deinem Sample mit XOR grad noch auffällt:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| Bitmaske zu 1: 00 01 00 10 01 10 00 01 10 00 01 10 00
Bitmaske zu 2: 00 01 10 00 00 10 01 10 00 01 10 00 00
XOR 00 00 10 10 01 00 01 11 10 01 11 10 00
(v&0x1555555)+(v>>1)&0x1555555):
00 00 00 00 01 00 01 01 00 01 01 00 00
+00 00 01 01 00 00 00 01 01 00 01 01 00
=00 00 01 01 01 00 01 10 01 01 10 01 00
Bit Count: 9
Unterschied: 9 |
Bergmann89 - Do 04.08.16 10:05
Hey,
habs jetz auch so gemacht wie in deinem 2. Post, nur das ich ein OR und kein ADD nehme. Ne halbe Stunde nachdem ich hier gepostet hab is mir die Lösung eingefallen xD
Ausführungszeit ist 40% von der vorherigen Implementierung, also mehr als doppelt so schnell :)
MfG Bergmann
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!