Ein Array schnell auf 0 Werte prüfen

[Tyrael Y.]

Hallo zusammen,

ich lese aus einem Datenstrom Daten in ein Array.
Es kann vorkommen das ein sehr großes Array nur aus Nullen besteht.
Wenn dieses Array nur aus Nullen besteht, muss ich es nicht weiterverabeiten.

Wie kann ich ein großes Array (array of byte, array of word, array of integer) schnell auf nur Nullen untersuchen?

Delphi-Quellcode:

type TIntArray = array of integer;

function IsEmptyArray(AArray: TIntArray): Boolean
begin
 //for i := Low(AArray) to High(AArray) do
 //begin
end;

[Klaus01]

Guten Morgen,

beim Einlesen der Daten besteht da keine Möglichkeit die Daten zu Prüfen?
Wenn Du nur das Array prüfen kannst, dann würde ich nicht mit einer
for to Schleife arbeiten, denn Du kannst ja bei dem ersten Wert der <> null ist
schon die Schleife verlassen.

Wie groß ist denn die Chance eine Array nur mit Nullen vorzufinden?

Grüße
Klaus

[marabu]

Hallo,

am schnellsten dürfte der Einsatz einer kurzen ASM-Funktion auf der Basis von SCASB sein.

Delphi-Quellcode:

function CheckZeroMem(p: PByte; size: Word): Boolean;
var
  b: Byte;
begin
  b := 0;
  while (size > 0) and (b = 0) do
  begin
    b := b or p^;
    Dec(size);
    Inc(p);
  end;
  Result := b = 0;
end;

Grüße vom marabu

[Reinhard Kern]

Zitat von Tyrael Y.:

Hallo zusammen,

ich lese aus einem Datenstrom Daten in ein Array.
Es kann vorkommen das ein sehr großes Array nur aus Nullen besteht.
Wenn dieses Array nur aus Nullen besteht, muss ich es nicht weiterverabeiten.

Wie kann ich ein großes Array (array of byte, array of word, array of integer) schnell auf nur Nullen untersuchen?

Hallo,

für die Arithmetik ist Null so gut wie irgendeine andere Zahl, ich glaube nicht, dass der Compiler für den Fall Null besondere Optimierungen durchführt. Mit Assembler liesse sich was machen: Anfangs- und End-Adresse des Arrays bestimmen und dann einfach alle Worte im Akku verodern - nur wenn alle 0 sind, ist es das Ergebnis auch, bei nicht 0 kann man die Schleife abbrechen. Oder man verwendet den einzeiligen Befehl REPZ SCAS.

Gruss Reinhard

[sirius]

Delphi-Quellcode:

function IsEmptyArray(AArray: TIntArray): Boolean 
asm
  push edi
  mov edi,eax
  mov ecx,[eax-4]
  xor eax,eax
  repe scasd
  jnz @end
  inc al
@end:
  pop edi
end;

Edit: (etwas allgemeiner)

Delphi-Quellcode:

function IsZeroMemory(const mem;size:integer):boolean;
asm
  push edi
  mov edi,eax
  mov ecx,edx
  shr ecx,2
  xor eax,eax
  repe scasd
  jnz @False
  mov ecx,edx
  and ecx,3
  repe scasb
  jnz @FALSE
  inc eax
@FALSE:
  pop edi
end;

...
var x:array of integer;
...
isZeroMemory(x[0],sizeof(Integer)*length(x))

[3_of_8]

Inline Assembler ist aber alles andere als portabel. Ich würde einfach ganz normal die Standardfunktionen verwenden. Der Flaschenhals entsteht hier ja nicht durch die Taktfrequenz, also die Anzahl der Befehle, sondern eher dadurch, dass die Eingabewerte recht langsam zum Prozessor kommen.

[sirius]

Zitat von 3_of_8:

Inline Assembler ist aber alles andere als portabel. Ich würde einfach ganz normal die Standardfunktionen verwenden. Der Flaschenhals entsteht hier ja nicht durch die Taktfrequenz, also die Anzahl der Befehle, sondern eher dadurch, dass die Eingabewerte recht langsam zum Prozessor kommen.

Was meinst du mit "nicht portabel"? Funktioniert doch auf jedem Prozessor der sich mit der IA-32 auskennt.
Und schneller ist es auch. Eingabewerte können auch in den Cache, wenn man es dem Prozessor rechtzeitig sagt.
Wann jemand auf ASM zurückgreift, muss er für sich selber entscheiden.

[Laufi]

Hallo

Da du ein Integer array hast kannst du es auch als vektor betrachten. Dann kannst du eine beliebige Norm wählen z.B. euklid und von deinem Vektor berechnen. Wenn die norm 0 ist sind alle werte in deinem Array 0

Liebe Grüsse
Laufi

[3_of_8]

Zitat von sirius:

Was meinst du mit "nicht portabel"? Funktioniert doch auf jedem Prozessor der sich mit der IA-32 auskennt.
Und schneller ist es auch. Eingabewerte können auch in den Cache, wenn man es dem Prozessor rechtzeitig sagt.
Wann jemand auf ASM zurückgreift, muss er für sich selber entscheiden.

Natürlich, und es gibt ja keine anderen Maschinensprachen als IA-32.

Natürlich können Eingabewerte in den Cache, aber der Flaschenhals in diesem Fall ist nunmal wirklich die Verbindung Prozessor-Hauptspeicher, bei sehr hoher Datenmenge eventuell sogar Hauptspeicher-Festplatte. Die Optimierung auf der Assembler-Ebene bringt daher hier wirklich wenig, von daher würde ich vorschlagen, darauf zu verzichten.

[sirius]

Zitat von 3_of_8:

Natürlich, und es gibt ja keine anderen Maschinensprachen als IA-32.

Zumindest wirds auf anderen Architekturen auch für Windows und Linux extrem schwer.

Zitat von 3_of_8:

Die Optimierung auf der Assembler-Ebene bringt daher hier wirklich wenig.

Meistens bringt Assembler nicht viel. Da stimme ich dir zu. Aber die Optimierung bei solchen Vorgängen bringt ausnahmsweise sogar mal sehr viel. Sobald du einen ASM-Befehl für Repeat (REPE; REPNZ) einsetzen kannst, bekommst du diese Vorteile. Kannst ja mal messen.