| Autor |
Beitrag |
Bergmann89
 
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: Mi 03.08.16 20:43
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 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 _________________ Ich weiß nicht viel, lern aber dafür umso schneller^^
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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:
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. _________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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 | _________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Bergmann89 
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: 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 _________________ Ich weiß nicht viel, lern aber dafür umso schneller^^
|
|
|
