Anzahl eines Zeichens im String ermitteln

[KodeZwerg]

Zitat von freimatz:

Wegen Portabilität und so: Ihr berücksichtigt keine Unicode Surrogate-Paare.

Funktioniert das was Du schreibst auch nicht mit der Variante aus Post #30 ? (AnsiChar sucht in AnsiString)

[himitsu]

Zitat von jaenicke:

Wenn es wirklich auf die Performance ankommt, blieben noch spezielle CPU Instruktionen wie repne scasb bzw. repne scasw. Die habe ich auch schon benutzt, aber das macht nur Sinn, wenn es wirklich Not tut. Eben wegen Portabilität usw.

Im Prinzip machen das StrScan, Pos usw. auch schon, um das erste Char des Suchtextes schnell zu finden ... halt mit noch bissl mehr drumrum, da dort ja ganze Zeichenketten gesucht werden.

Zitat von freimatz:

Wegen Portabilität und so: Ihr berücksichtigt keine Unicode Surrogate-Paare.

Also das ist erstmal kein Problem, denn die Surrogates haben ihren eigenen Bereich, also wenn du nach was Anderem suchst, dann findet man nicht ausversehn einen halben Surrogate.

Surrogate selber kann man aber nicht suchen, bzw. eben nur einzeln nach den beiden Hälften.

[EgonHugeist]

@Uwe

Schaut gut aus! No a bizzl kürzer:

Delphi-Quellcode:

function CharCount(const S: string; C: Char): Cardinal;
var
  P, PEnd: PChar;
begin
  Result := 0;
  P := Pointer(S);
  if P = nil then Exit;
  PEnd := P + PLongInt(NativeUInt(P) - SizeOf(LongInt))^;
  while P < PEnd do begin
    Inc(Result, Ord(P^ = C));
    Inc(P);
  end;
end;

[himitsu]

Ein gutes Beispiel für Codes, die in 64 Bit gnadenlos abrauchen.

[EgonHugeist]

Zitat von himitsu:

Ein gutes Beispiel für Codes, die in 64 Bit gnadenlos abrauchen.

Na dann klär mich mal auf! Hättest du FPC anstatt von nur "64 Bit" geschrien dann hättest du meiner bescheidenen Meinung nach recht.
Edit:

Code:

function CharCount(const S: string; C: Char): Cardinal;
var
  P, PEnd: PChar;
begin
  Result := 0;
  P := Pointer(S);
  if P = nil then Exit;
  {$IFNDEF FPC}
  PEnd := P + PLongInt(NativeUInt(P) - SizeOf(LongInt))^;
  {$ELSE}
  PEnd := P + PSizeInt(NativeUInt(P) - SizeOf(SizeInt))^;
  {$ENDIF}
  while P < PEnd do begin
    Inc(Result, Ord(P^ = C));
    Inc(P);
  end;
end;

[Neutral General]

Ich poste meine Assembler Version einfach mal.

Delphi-Quellcode:

function CharCountAsm(AStr: PChar { eax }; AChar: Char { dx }; len: Integer { ecx }): Integer;
label loop_start, loop_ende, ende; 
asm
  // Danke gammatester! - sorgt dafür dass scasw vorwärts und nicht rückwärts sucht
  cld 
  // edi + ax für scasw initialisieren
  mov edi, eax  
  mov ax, dx
  // edx = char count := 0
  xor edx, edx  
loop_start:
  repnz scasw    // bis zum nächsten Vorkommen "vorspulen"
  jcxz loop_ende // Wenn String zu Ende, aus Schleife springen
  inc edx        // Vorkommen des Chars mitzählen
  jmp loop_start
loop_ende:
  jnz ende     
  inc edx         // Falls der letzte Buchstabe noch ein Treffer war
ende:
  mov result, edx
end;

i := CharCountAsm(@Data[1], 'X', Length(Data));

Damit erreiche ich momentan den 2. Platz im Benchmark (CountCharInString gewinnt).

ACHTUNG: Da scheint auch noch irgendwo ein kleiner Denkfehler drin zu sein
In (relativ) seltenen Fällen zählt mein Code aus irgendeinem Grund falsch.
Falls jemand eine Idee hat wo der Fehler ist oder wie man den Code generell noch verbessern/verschnellern kann wäre das super!

64-Bit ginge natürlich auch, aber habe wenig Erfahrung mit 64 Bit Assembler, deswegen lasse ichs erst mal.

[Uwe Raabe]

Zitat von EgonHugeist:

Schaut gut aus! No a bizzl kürzer:

Braucht allerdings dann ca. 30% länger, weil das INC immer ausgeführt wird, auch wenn es gar nicht nötig ist. OK, wenn der String fast nur aus dem gesuchten Zeichen besteht, dann wäre das eine Option. Die Standardmethode aus dem StringHelper S.CountChar(C) ist da auch nicht viel schlechter (ca. 50% länger als mein letzter Ansatz und ca. 20% länger als dein Vorschlag).

Offenbar sind die Ansätze mit PChar und Inc(P) potentiell schneller als indizierte Zugriffe in For-Schleifen. Ob der erreichbare Geschwindigkeitsgewinn aber die schlechtere Lesbarkeit und Wartbarkeit (siehe die ganzen Probleme mit Assembler) rechtfertigt, ist wohl eher zweifelhaft.

Ich habe den Benchmark etwas modifiziert und rufe die einzelnen Probanden 10000x auf um lokale Schwankungen auszugleichen - natürlich außerhalb der IDE und im Release-Mode. Messungen im Nanosekundenbereich sind einfach nicht verlässlich genug. Da der String per Zufall generiert wird, kann man verschiedene Läufe auch nicht direkt miteinander vergleichen, nur die Rangfolge innerhalb eines Laufs. Der Zeichensatz ist ja auch etwas eingeschränkt gewählt.

[gammatester]

Zitat von Uwe Raabe:

Ich habe den Benchmark etwas modifiziert und rufe die einzelnen Probanden 10000x auf um lokale Schwankungen auszugleichen - natürlich außerhalb der IDE und im Release-Mode. Messungen im Nanosekundenbereich sind einfach nicht verlässlich genug. Da der String per Zufall generiert wird, kann man verschiedene Läufe auch nicht direkt miteinander vergleichen, nur die Rangfolge innerhalb eines Laufs. Der Zeichensatz ist ja auch etwas eingeschränkt gewählt.

Warum benutzt Du nicht eine festes Randseed pro Lauf?

[gammatester]

Zitat von Neutral General:

ACHTUNG: Da scheint auch noch irgendwo ein kleiner Denkfehler drin zu sein

Da scheint auch noch ein grundsätzlicher Fehler drin zu sein, da Du nirgends das Directionflag mit cld auf 0 setzt. Ich würde mich zumindest nicht darauf verlassen.

[Uwe Raabe]

Zitat von gammatester:

Warum benutzt Du nicht eine festes Randseed pro Lauf?

Mein Kommentar bezogt sich auf die Originalversion.