Anzahl eines Zeichens im String ermitteln

[EgonHugeist]

Zitat von Uwe Raabe:

Zitat von EgonHugeist:

Um etwas zu lernen, hilft es mir es zu verstehen. Schnell im Pure-Pascal ist etwas, was ich mag.

Wenn ich mir die Implementation von StringReplace in D2009 und Tokyo ansehe, dann sind die doch schon sehr verschieden. Die Implementation in D2009 (34 Zeilen) macht einen Haufen Copy und Result := Result + NewStr, während Tokyo (212 Zeilen) zunächst die Anzahl der Fundstellen ermittelt und damit die Länge von result ermittelt und bereitstellt. Danach wird einfach nur mehrfach ein Move in Result gemacht. Das ist unterm Strich offenbar deutlich schneller. Der Code in 2009 ist dafür leichter zu verstehen und straight forward. In der Tokyo Version möchte ich keinen Fehler suchen.

So was habe ich mir schon gedacht.. für das Abändern der function! Ich kenne sehr viele implementationen von StringReplace, alle jedoch reservieren Speicher für das Resultat. Hier kommt noch eine Sache zum Tragen: der Char ist kein String, somit sollte abermals Speicher (WideChar->UnicodeString) reserviert werden, wenn da nicht inzwischen ein overload existiert. Gehen wir davon aus, die neue Variante wurstelt erst mal die Anzahl der vorgekommenen SubStr's raus, hat einen statischen Pool von Markern vorreserviert, und braucht nur noch in das Result schreiben(wenn Result string refcount 1 ist). SysFreeMem und SysGetMem setzen/flushen nur (dank Idee von Pierre le Richie -> verzögertes freigeben ) noch das Flag für den Speicherbereich(oder hält der Compiler das Result auf alle Ewigkeit im Speicher?). Kling alles sehr gut!

Dennoch stehen die Calls(50Cycles/Call) auf StringReplace, ?WChar2UStr?, GetMem, FreeMem und 240 Zeilen StringReplace im Raum (Length ist seit D2005 inlined und macht das gleiche, wie mein NativeCode oder es in den ASM varianten zu sehen ist) und 2x Code für die Stringlänge, wogegen jede andere function ohne all dem auskommt. Ich meine man sollte da schon einen merklichen Nachteil erkennen können. Darum die Hypothese. Und die An,erkung über den Test Selber, das der String in seiner Größe und Inhalt permanent wechseln sollte. Wäre dem so(IMHO usual case), würde sich die StringReplace Variante auch auf dem neuen Compiler deutlich mehr abheben und die Nachteile erleutern (der Lerneffekt für andere Benutzer sollte ja gegeben sein, oder?).

Ich bin dennoch sehr beeindruckt, wie weit der Compiler Fortschritte für Optimierungen all der Schritte inzwischen gemacht hat. Würde mir ein Chart wünschen, welches solche Effeckte je nach Compiler-Entwicklungsforschritt(alt vs. neu) mal darstellt. Gibt es ein solches? Es gäbe mit Sicherheit eine Ziehlgruppe, die solche Darstellungen eher zum Kauf/Update bewegen würden als FMX,Generics,NEXTGEN &Co.

Zitat von Harry Stahl:

Zitat von EgonHugeist:

Aber danke auch an Dich für den Hinweis mit der blockweisen Bearbeitung, da kommen mir Ideen für andere Funktionen (z.B. in der Bitmap-Bearbeitung)...

Gern geschehen. Auch die 2. ASM Variante von Andreas zeigt die Technik auf (viel genialer umgesetzt dank seiner ASM Kenntnisse). Der Effeck einer Blockweisen Abarbeitung innerhalb einer Big-Loop wird deutlich größer, desto mehr insgesammt verarbeitet wird. Das Thema hier ist da von der Aufgabenstellung her zu maginal für meine Pure-Pascal Version um den Effekt aufzuzeigen zu können. Es entsteht jedoch deutlich mehr Code der gepflegt werden muß, also macht die Technik auch nicht überall Sinn, könnte sich sogar negativ auswirken. Hinzu kommt das viele den Sinn nicht erkennen können. Da gibt es Leute, die fangen mit 'nem Thread-Pool/TParallel an, wo diese Technink schon ausreichend oder effizienter wäre.

[KodeZwerg]

Also das mit dem Replace und wie der Delphi 2009 Kompiler damit umgeht versteh ich nicht.

Zitat:

0000303114 - Statistic: [Binary Data] [303114 Avg] [302392 Min] [303835 Max] [606227 Full] @ KodeZwerg TestStringBuilder()
0000620229 - Statistic: [ASCII Data] [620229 Avg] [4518 Min] [1235939 Max] [1240458 Full] @ KodeZwerg TestStringBuilder()
0002884451 - Statistic: [Binary Data] [2884451 Avg] [2853455 Min] [2915447 Max] [5768902 Full] @ Ydobon
0005993589 - Statistic: [ASCII Data] [5993589 Avg] [4226 Min] [11982953 Max] [11987178 Full] @ Ydobon

Delphi-Quellcode:

// Ydobon =     i := Length(Data) - Length(StringReplace(Data, Ch, '', [rfReplaceAll]));

function TCharInString.TestStringBuilder(const aString: string; const Ch: Char): Integer;
var
  sb: TStringBuilder;
begin
  sb := TStringBuilder.Create;
  sb.Append(aString);
  sb.Replace(Ch, '');
  Result := Length(aString) - sb.Capacity;
  FreeAndNil(sb);
end;

Ich mache doch theoretisch genau das selbe wie Ydobon aber ein enormer Geschwindigkeitszuwachs. (Nach wie vor auf letzten Platz)
Eine neue Version mit noch mehr nützlichen Optionen ist bereits fertig, auch Egons fehlende Methoden sind enthalten.

Wenn ich meine StrScan() Methode korrigiere, kommt Uwes Variante bei raus also habe ich nun eine Sicherheits-CheckBox die CountCharInString(), CharInStringA() und CharCount() vom Test ausschließt.
CharInStringA() weist noch einen bösen Fehler auf, Char <> AnsiChar Konvertierung schlägt sporadisch fehl, ich vermute ab Char 7F wird es knallen.

So wie Uwe es gemacht hat, mit einer Werte-Kontrolle kann ich bei mir so nicht einbauen da doppelter overhead produziert werden würde (ist dem Random(Char) zu verdanken ^_^)

[Uwe Raabe]

Zitat von KodeZwerg:

Also das mit dem Replace und wie der Delphi 2009 Kompiler damit umgeht versteh ich nicht.

Das StringReplace in D2009 verwendet ja auch keinen StringBuilder und das dortige Replace, sondern in etwa folgenden Algorithmus:

Code:

1. Initialisiere Result mit einem Leerstring und setze die Position auf den Anfang des Strings
2. Suche das nächste Vorkommen des Such-Patterns
3. Hänge den String vom Start bis zur Startposition des Such-Patterns bzw. Ende des Strings (wenn nicht gefunden) an den Result an
4. Brich ab, wenn das Such-Pattern nicht gefunden wurde
5. Hänge das Ersetzen-Pattern dran
6. Rücke vor bis zum Ende des Such-Patterns
7. Wiederhole ab Schritt 2

Der Result-String wird also bei jedem gefundenen Zeichen zweimal verlängert, wobei in vielen Fällen wohl ein komplettes Umkopieren von Result nötig ist. Das StringReplace ist in D2009 eben extrem unperformant und speicherhungrig implementiert, dafür aber deutlich leichter zu lesen und zu verstehen.

Es ist noch anzumerken, daß diese StringReplace-Optimierung erst in Delphi 10.1 Berlin eingeführt wurde.

[KodeZwerg]

Zitat von Uwe Raabe:

Es ist noch anzumerken, daß diese StringReplace-Optimierung erst in Delphi 10.1 Berlin eingeführt wurde.

Ja, so etwas habe ich mir beim Ausführen der von Euch hochgeladenen .exes gedacht.
Wenn Du heute mal Zeit hast würde mich ein Ergebnis Tokyo Ydobon vs TestStringBuilder() Interessieren, ob da der StringBuilder auch noch die Nase vorne hat?

[KodeZwerg]

Hab noch etwas gebastelt aber ist auch nicht sehr effektiv.

Delphi-Quellcode:

// versuche 4 compares pro loop abzufertigen
function TCharInString.MultiCountChar(const s: string; const c: Char): Integer;
var
  i, ii, iii, iiii: Integer;
begin
  Result := 0;
  ii := Length(s);
  iii := (ii div 2);
  iiii := iii+1;
  for i := 1 to (Length(s) div 2) do
  begin
    if s[i] = c then Inc(Result, 1); // suche vom Anfang in Richtung Mitte
    if s[ii] = c then Inc(Result, 1); // suche vom Ende in Richtung Mitte
    if s[iii] = c then Inc(Result, 1); // suche von Mitte in Richtung Anfang
    if s[iiii] = c then Inc(Result, 1); // suche von Mitte in Richtung Ende
    Dec(ii);
    Dec(iii);
    Inc(iiii);
    if i = iii then Break;
  end;
end;

[himitsu]

Sinnlos auf unnötig viele Vaiablen zugreifen und im Speicher kreuzundquer? Da kann dann nichtmal ein ordentliches Pageging/Caching gut arbeiten.
Eventuell werden Chars doppelt, dreifach oder gar vierfach gezählt und anstatt die Schleife gleich im richtigen Bereich laufen zu lassen noch eine zusätzliche Abbruchprüfung.

Eine Schleife mit nur einer Zähler- und Ende-Variable und zugriff auf nur eine Page nach der Anderen, anstatt kreuzundquer.

Oder, 4 oder 8 zusammenhängende und ausgerichtete (align) Bytes in ein Register (lokale temporäre Variable innerhalb der Schleife) einlesen und direkt im Register prüfen.