Autor Beitrag
Bergmann89
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: Mi 03.08.16 19: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:

ausblenden 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:
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8720
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Mi 03.08.16 20: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:
ausblenden 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:

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

ausblenden 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:

ausblenden volle Höhe 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.

_________________
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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8720
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Mi 03.08.16 21:06 
Wobei mir bei deinem Sample mit XOR grad noch auffällt:
ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: Do 04.08.16 09: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^^