Tweet
Die neue herausforderung:
Vorhanden: Ein Array a aus 600000 Array's mit jeweils 32 byte-werten und
ein hilfs-Array s mit einer integer-representation des ersten Arrays, wobei
die bit-masken dieser integer auskunft darüber erteilen, ob im a-Array an
der position eine 0 oder ein anderer wert vorhanden ist.
var a: array[0..600000] of array[0..31] of byte;
var s: array[0..600000] of integer;
Die anforderung an den algorithmus ist prinzipiell die gleiche, wie
in der letzten diskussion. Es geht darum, alle elemente des arrays a
untereinander zu vergleichen, um fest zu stellen, inwiefern sie sich
jeweils unterscheiden. Von interesse sind solche fundstellen, bei denen
sich die array's in einer einzigen stelle im byte-array unterscheiden,
wobei eines der beiden verglichenen array's dort eine 0 stehen haben
muss.
<pre>
// hilfsvariablen
n,d,i: integer;
e: extended;
for n:=0 to length(a)-1 do
begin
// alle elemente durchlaufen
for x:=n+1 to length(a)-1 do
begin
// differenz-maske bilden
d := s[x] XOR s[n];
if (d>0) then
begin
// stellen ermitteln, wo unterschiede vorliegen
// nur wenn sich eine einzelne stelle unterscheidet,
// ist e ganzzahlig
e:=log2(d);
if( frac(e)=0 )then
begin
d:=trunc(e);
// d enthält nun die position der einzigen abweichung
// diejenigen ausschliessen, die in den gesetzten
// bytes unterschiedliche werte haben
for i:=0 length(a[n])-1 do
if (d<>-1) // nur solange prüfen, wie wir einen potentiellen treffer haben
and (i<>d) // diesen index brauchen wir nicht prüfen
and (a[n][i]<>0) and (a[x][i]<>0) // beide arrays müssen an der zu prüfenden position einen wert
// ungleich 0 haben
and ( a[n][i]<>a[x][i] ) // die eigentliche prüfung
then d:=-1; // falls sich die arrays hier unterscheiden,
// haben wir keinen treffer
// wenn d nun noch positiv ist, wissen wir, dass sich
// die beiden array's an einer einzigen stelle (position d) unterscheiden
// und zwar in der art, das eines der beiden dort den wert 0 hat
if(d>=0)then
begin
{
... hier findet die verarbeitung statt
}
end;
end;
end;
end;
</pre>
Das aufwendige bei diesen tests ist, zu prüfen, ob die byte-arrays
bis auf die ermittelte position identisch sind - da ist meiner ansicht nach
noch ein grosses optimierungspotential verborgen. Dieser algorithmus braucht mehrere stunden (inkl. der ergebnisverarbeitung) auf einem P4/2GHz...
Vorhanden: Ein Array a aus 600000 Array's mit jeweils 32 byte-werten und
ein hilfs-Array s mit einer integer-representation des ersten Arrays, wobei
die bit-masken dieser integer auskunft darüber erteilen, ob im a-Array an
der position eine 0 oder ein anderer wert vorhanden ist.
var a: array[0..600000] of array[0..31] of byte;
var s: array[0..600000] of integer;
Die anforderung an den algorithmus ist prinzipiell die gleiche, wie
in der letzten diskussion. Es geht darum, alle elemente des arrays a
untereinander zu vergleichen, um fest zu stellen, inwiefern sie sich
jeweils unterscheiden. Von interesse sind solche fundstellen, bei denen
sich die array's in einer einzigen stelle im byte-array unterscheiden,
wobei eines der beiden verglichenen array's dort eine 0 stehen haben
muss.
<pre>
// hilfsvariablen
n,d,i: integer;
e: extended;
for n:=0 to length(a)-1 do
begin
// alle elemente durchlaufen
for x:=n+1 to length(a)-1 do
begin
// differenz-maske bilden
d := s[x] XOR s[n];
if (d>0) then
begin
// stellen ermitteln, wo unterschiede vorliegen
// nur wenn sich eine einzelne stelle unterscheidet,
// ist e ganzzahlig
e:=log2(d);
if( frac(e)=0 )then
begin
d:=trunc(e);
// d enthält nun die position der einzigen abweichung
// diejenigen ausschliessen, die in den gesetzten
// bytes unterschiedliche werte haben
for i:=0 length(a[n])-1 do
if (d<>-1) // nur solange prüfen, wie wir einen potentiellen treffer haben
and (i<>d) // diesen index brauchen wir nicht prüfen
and (a[n][i]<>0) and (a[x][i]<>0) // beide arrays müssen an der zu prüfenden position einen wert
// ungleich 0 haben
and ( a[n][i]<>a[x][i] ) // die eigentliche prüfung
then d:=-1; // falls sich die arrays hier unterscheiden,
// haben wir keinen treffer
// wenn d nun noch positiv ist, wissen wir, dass sich
// die beiden array's an einer einzigen stelle (position d) unterscheiden
// und zwar in der art, das eines der beiden dort den wert 0 hat
if(d>=0)then
begin
{
... hier findet die verarbeitung statt
}
end;
end;
end;
end;
</pre>
Das aufwendige bei diesen tests ist, zu prüfen, ob die byte-arrays
bis auf die ermittelte position identisch sind - da ist meiner ansicht nach
noch ein grosses optimierungspotential verborgen. Dieser algorithmus braucht mehrere stunden (inkl. der ergebnisverarbeitung) auf einem P4/2GHz...
Comment