Laden...

Effizientes Zählen von bestimmten Zeichen in einem String

Erstellt von typhos vor 15 Jahren Letzter Beitrag vor 15 Jahren 3.360 Views
T
typhos Themenstarter:in
243 Beiträge seit 2006
vor 15 Jahren
Effizientes Zählen von bestimmten Zeichen in einem String

Hi,
ich habe Strings, in denen Punkte (".") vorkommen. Ich möchte wissen, wie viele Punkte im String enthalten sind, und das möglichst effizient, da das sehr oft gebraucht wird.

Meine Quick&Dirty-Methode macht Folgendes:

int count = meinString.Split('.').Length - 1

Ich denke mal, dass es wohl effizientere Möglichkeiten gibt, da hier ja erst ein Array erzeugt wird.

Ich bin mir nicht sicher, ob reguläre Ausdrücke effizienter sind oder ob es vielleicht irgendwas superschneller gibt, dass ich nur übersehen habe.

Danke für jeden Tipp!!

738 Beiträge seit 2007
vor 15 Jahren

wahrscheinlich müsstest du selbst nachmessen, was nun wirklich schneller ist, aber du könntest auch die einzelnen Character des Strings durchgehen und mitzählen:


string x = "dkfjdk.fg.df.gdf.gdf.g.";
int counter = 0;
for (int i = 0; i < x.Length; i++)
{
     if (x[i] == '.')
         counter++;
}

S
120 Beiträge seit 2005
vor 15 Jahren

Hi,

sollte am schnellsten mit einem regulären ausdruck gehen:

int count = new Regex("\.").Matches(meinString).Count;

Ciao SunboX

Actionscript ist die Möglichkeit, postmaterielles Basteln zum Lebensstil zu machen.

Künstliche Intelligenz ist leichter zu ertragen, als natürliche Dummheit!

Gelöschter Account
vor 15 Jahren

Hallo SunboX,

bei dir fehlt entweder ein @ vor dem Pattern oder ein zweites backslash. zudem ist regex in diesem speziellen fall deutlich langsamer als das simple durchgehen eines strings und zählen eines bestimmten zeichens.

die forschleife ist in diesem fall die deutlich performantere.

S
120 Beiträge seit 2005
vor 15 Jahren

Hallo JAck30lena,

stimmt! Ich habe es gerade mal getestet. RegEx ist sehr viel langsamer! 😮) Hätte ich jetzt echt nicht gedacht.

private void Form1_Load(object sender, EventArgs e)
        {
            string meinString = "Überall dieselbe alte Leier. Das Layout ist fertig, der Text lässt auf sich warten. Damit das Layout nun nicht nackt im Raume steht und sich klein und leer vorkommt, springe ich ein: der Blindtext. Genau zu diesem Zwecke erschaffen, immer im Schatten meines großen Bruders »Lorem Ipsum«, freue ich mich jedes Mal, wenn Sie ein paar Zeilen lesen. Denn esse est percipi - Sein ist wahrgenommen werden.Und weil Sie nun schon die Güte haben, mich ein paar weitere Sätze lang zu begleiten, möchte ich diese Gelegenheit nutzen, Ihnen nicht nur als Lückenfüller zu dienen, sondern auf etwas hinzuweisen, das es ebenso verdient wahrgenommen zu werden: Webstandards nämlich.        Sehen Sie, Webstandards sind das Regelwerk, auf dem Webseiten aufbauen. So gibt es Regeln für HTML, CSS, JavaScript oder auch XML; Worte, die Sie vielleicht schon einmal von Ihrem Entwickler gehört haben. Diese Standards sorgen dafür, dass alle Beteiligten aus einer Webseite den größten Nutzen ziehen. Im Gegensatz zu früheren Webseiten müssen wir zum Beispiel nicht mehr zwei verschiedene Webseiten für den Internet Explorer und einen anderen Browser programmieren. Es reicht eine Seite, die – richtig angelegt – sowohl auf verschiedenen Browsern im Netz funktioniert, aber ebenso gut für den Ausdruck oder die Darstellung auf einem Handy geeignet ist. Wohlgemerkt: Eine Seite für alle Formate. Was für eine Erleichterung.         Standards sparen Zeit bei den Entwicklungskosten und sorgen dafür, dass sich Webseiten später leichter pflegen lassen. Natürlich nur dann, wenn sich alle an diese Standards halten. Das gilt für Browser wie Firefox, Opera, Safari und den Internet Explorer ebenso wie für die Darstellung in Handys.    Und was können Sie für Standards tun? Fordern Sie von Ihren Designern und Programmieren einfach standardkonforme Webseiten. Ihr Budget wird es Ihnen auf Dauer danken.             Ebenso möchte ich Ihnen dafür danken, dass Sie mich bin zum Ende gelesen haben. Meine Mission ist erfüllt. Ich werde hier noch die Stellung halten, bis der geplante Text eintrifft. Ich wünsche Ihnen noch einen schönen Tag. Und arbeiten Sie nicht zuviel!";
            Stopwatch sw = new Stopwatch();
            sw.Start();

            long start_1 = sw.ElapsedMilliseconds;
            int count_1 = 0;
            for (int i = 0; i < 1000; i++)
            {
                count_1 += meinString.Split('.').Length - 1;
            }
            long stop_1 = sw.ElapsedMilliseconds;

            long start_2 = sw.ElapsedMilliseconds;
            int count_2 = 0;
            for (int i = 0; i < 1000; i++)
            {
                for (int j = 0; j < meinString.Length; j++)
                {
                    if (meinString[j] == '.')
                        count_2++;
                }
            }
            long stop_2 = sw.ElapsedMilliseconds;

            long start_3 = sw.ElapsedMilliseconds;
            int count_3 = 0;
            Regex reg = new Regex("[.]");
            for (int i = 0; i < 1000; i++)
            {
                count_3 += reg.Matches(meinString).Count;
            }
            long stop_3 = sw.ElapsedMilliseconds;

            sw.Stop();

            MessageBox.Show(
                "Ergebnis:\n\n"+
                "Split:\n"+
                "- gefunden: " + count_1.ToString() + "\n" +
                "- Millisekunden: " + (stop_1 - start_1).ToString() + "\n\n" +
                "Schleife:\n"+
                "- gefunden: " + count_2.ToString() + "\n" +
                "- Millisekunden: " + (stop_2 - start_2).ToString() + "\n\n" +
                "RegEx:\n"+
                "- gefunden: " + count_3.ToString() + "\n" +
                "- Millisekunden: " + (stop_3 - start_3).ToString() + "\n\n"
                );


        }

Ergebnis:

Ergebnis:

Split:
- gefunden: 22000
Millisekunden: 20

Schleife:
- gefunden: 22000
- Millisekunden: 17

RegEx:
- gefunden: 22000
- Millisekunden: 21

Ciao SunboX 😮)

Actionscript ist die Möglichkeit, postmaterielles Basteln zum Lebensstil zu machen.

Künstliche Intelligenz ist leichter zu ertragen, als natürliche Dummheit!

738 Beiträge seit 2007
vor 15 Jahren

gewonnen 😁 😁 😁

T
typhos Themenstarter:in
243 Beiträge seit 2006
vor 15 Jahren

Wow! Danke für die ausführliche Erörterung 😁

Ein toller Service hier, wie immer 👍

Nochmals Danke!!

U
1.688 Beiträge seit 2007
vor 15 Jahren

So einfach ist das nicht. Lasse ich das Programm wie oben laufen, erhalte ich:
Split:

  • gefunden: 22000
  • Millisekunden: 26

Schleife:

  • gefunden: 22000
  • Millisekunden: 23

RegEx:

  • gefunden: 22000
  • Millisekunden: 23

Laufen die Testschleifen hingegen bis 10000, also 10x länger, ergibt sich:
Split:

  • gefunden: 220000
  • Millisekunden: 194

Schleife:

  • gefunden: 220000
  • Millisekunden: 228

RegEx:

  • gefunden: 220000
  • Millisekunden: 225

Und schließlich zeigt sich bei 100000 Schleifendurchläufen:
Split:

  • gefunden: 2200000
  • Millisekunden: 1758

Schleife:

  • gefunden: 2200000
  • Millisekunden: 2272

RegEx:

  • gefunden: 2200000
  • Millisekunden: 2197

Selbst mehrfaches Ausführen zwecks Statistik zeigt dieses Muster: Schleife und RegEx sind etwa gleich schnell, Split verhält sich irgendwie anders. Allerdings ändert eine weitere Erhöhung der Schleifendurchläufe das Verhältnis nicht weiter.

Am schnellsten war in meinen Tests übrigens die folgende Variante:


        unsafe {
          fixed (char *cA=meinString.ToCharArray()) {
            char *c=cA;
            while (*c!='\0')
              if (*c++=='.')
                count_4++;
          }
        }

😁

Gelöschter Account
vor 15 Jahren

unsfe code... no comment ^^

und was die testergebnisse anbelangt, so habe ich auf meinen 2 rechnern einen deutlichen performanceunterschied zwischen regex und schleife.
(schleife um ein mehrfaches schneller)

somit ist wiedereinmal gezeigt, das man in .net nicht wirklich performance messen kann. hängt immernoch davon ab inwieweit optimiert werden kann seitens jit-compiler

4.207 Beiträge seit 2003
vor 15 Jahren

Versuch mal ein Replace von "." mit "", und dann vergleiche die Länge vorher und nachher ... keine Ahnung, wie schnell ein Replace ist, aber es wäre einen Versuch wert.

Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden

www.goloroden.de
www.des-eisbaeren-blog.de

T
typhos Themenstarter:in
243 Beiträge seit 2006
vor 15 Jahren

So, jetzt hab ich auch mal die Zeit gemessen und die Variante mit Replace und Längenvergleich von Golo noch dazugenommen:

Bei 1.000 Schleifendurchläufen

Split:

  • gefunden: 22000
  • Millisekunden: 45

Schleife:

  • gefunden: 22000
  • Millisekunden: 18

RegEx:

  • gefunden: 22000
  • Millisekunden: 60

Replace:

  • gefunden: 22000
  • Millisekunden: 33

Regex deutlich langsamer als die anderen...

Bei 10.000 Durchläufen:

Split:

  • gefunden: 220000
  • Millisekunden: 622

Schleife:

  • gefunden: 220000
  • Millisekunden: 238

RegEx:

  • gefunden: 220000
  • Millisekunden: 478

Replace:

  • gefunden: 220000
  • Millisekunden: 334

Hier ist Split erheblich langsamer, Regex bewegt sich im unteren Mittelfeld.

Bei 100.000 Durchläufen sieht es schon wieder anders aus:

Split:

  • gefunden: 2200000
  • Millisekunden: 2821

Schleife:

  • gefunden: 2200000
  • Millisekunden: 1996

RegEx:

  • gefunden: 2200000
  • Millisekunden: 4487

Replace:

  • gefunden: 2200000
  • Millisekunden: 6404

Hier ist plötzlich Replace viel langsamer und Split auf dem zweiten Platz.

Warum diese Schwankungen? Liegt es vielleicht nur an der wahrscheinlich unterschiedlichen Systemauslastung zum Zeitpunkt der Messung? Oder hat es wirklich mit der Anzahl der Durchläufe zu tun?
Jedenfalls war in meinen Tests die Schleifenvariante immer die schnellste. Die Methode mit unsicherem Code hab ich jetzt nicht probiert 😁

343 Beiträge seit 2007
vor 15 Jahren

Ich hab auch bereits festgestellt, dass Performancemessungen in C# nicht ganz so einfach sind und oft unerwartete Ergebnisse rauskommen.
Das liegt natürlich einerseits an der Systemauslastung zum Zeitpunkt der Messung, kann in manchen Fällen auch ein bisschen vom Garbage Collector beeinflusst werden.
Andererseits hängt es auch schon von den Schleifendurchläufen ab. Wie viel Hauptspeicher benötigt wird ist auch recht wesentlich, da dieser vom Betriebssystem bereit gestellt werden muss und das auch ein Grund sein kann warum es zu Abweichungen kommt.
Was mir aufgefallen ist: ein Profiler ist oft recht nützlich wenn es um solche Messungen geht.

Dass die Schleife am Schnellsten ist klingt aber irgendwie logisch für mich, denn auch bei split muss intern ja jedes Zeichen betrachtet werden UND zusätzlich noch ein Array erstellt werden.
Bei Replace muss ja auch intern jedes Zeichen betrachtet werden UND zusätzlich ein zweiter string erstellt werden.

Lg
Preli

[- www.saftware.net -](http://www.saftware.net/)
49.485 Beiträge seit 2005
vor 15 Jahren

Hallo zusammen,

also ich habe relativ konsistente Messergebnisse unabhängig von der Anzahl der Schleifendurchläufe:

for-Schleife (char []):     16  159  1567
foreach-Schleife (char[]):  16  161  1617
Array.ForEach:              24  237  2376
for-Schleife (String):      21  203  2076
forach-Schleife (String):   25  229  2307
String.Split:               19  194  1956
String.Replace:             28  284  2801
RegEx.Matches:              30  294  2940

Alle Angaben in Millisekunden bei 1.000, 10.000 und 100.000 Durchläufen.

Wie man sieht habe ich einige weitere Möglichkeiten der Zählung ausprobiert und dabei festgestellt, dass die Verwendung eines char-Arrays in den Schleifen schneller ist als die direkte Verwendung eines Strings, obwohl das char-Array erst mit ToCharArray aus dem String erzeugt wird.

Insgesamt liegt aber nur Faktor 2 zwischen der schnellsten und er langsamsten Methode. Daher sollte es in der Praxis relativ egal sein, welche man wählt. Man kann sich also guten Gewissens für die lesbarste entscheiden.

Hier der Testcode (nicht vergessen den String von oben einzusetzen):


using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

static class App
{
   public static void Main (string [] astrArg)
   {
      const int COUNT = 100000;

      string meinString = "..."; // wie oben
      Stopwatch sw = new Stopwatch();
      sw.Start();

      long start_1 = sw.ElapsedMilliseconds;
      int count_1 = 0;
      for (int i = 0; i < COUNT; i++)
      {
          char [] ach = meinString.ToCharArray ();
          for (int j = 0; j < ach.Length; j++)
          {
              if (ach[j] == '.')
                  count_1++;
          }
      }
      long stop_1 = sw.ElapsedMilliseconds;

      long start_2 = sw.ElapsedMilliseconds;
      int count_2 = 0;
      for (int i = 0; i < COUNT; i++)
      {
         char [] ach = meinString.ToCharArray ();
         foreach (char ch in ach)
         {
             if (ch == '.')
                 count_2++;
         }
      }
      long stop_2 = sw.ElapsedMilliseconds;

      long start_3 = sw.ElapsedMilliseconds;
      int count_3 = 0;
      for (int i = 0; i < COUNT; i++)
      {
          Array.ForEach (meinString.ToCharArray (),
            delegate (char ch)
            {
              if (ch == '.')
                  count_3++;
            }
         );
      }
      long stop_3 = sw.ElapsedMilliseconds;

      long start_4 = sw.ElapsedMilliseconds;
      int count_4 = 0;
      for (int i = 0; i < COUNT; i++)
      {
          for (int j = 0; j < meinString.Length; j++)
          {
              if (meinString[j] == '.')
                  count_4++;
          }
      }
      long stop_4 = sw.ElapsedMilliseconds;

      long start_5 = sw.ElapsedMilliseconds;
      int count_5 = 0;
      for (int i = 0; i < COUNT; i++)
      {
         foreach (char ch in meinString)
         {
             if (ch == '.')
                 count_5++;
         }
      }
      long stop_5 = sw.ElapsedMilliseconds;

      long start_6 = sw.ElapsedMilliseconds;
      int count_6 = 0;
      for (int i = 0; i < COUNT; i++)
      {
          count_6 += meinString.Split('.').Length - 1;
      }
      long stop_6 = sw.ElapsedMilliseconds;

      long start_7 = sw.ElapsedMilliseconds;
      int count_7 = 0;
      for (int i = 0; i < COUNT; i++)
      {
          count_7 += meinString.Length - meinString.Replace (".", "").Length;
      }
      long stop_7 = sw.ElapsedMilliseconds;

      long start_8 = sw.ElapsedMilliseconds;
      int count_8 = 0;
      Regex reg = new Regex("[.]");
      for (int i = 0; i < COUNT; i++)
      {
          count_8 += reg.Matches(meinString).Count;
      }
      long stop_8 = sw.ElapsedMilliseconds;

      sw.Stop();

      Console.WriteLine (
          "Ergebnis:\n\n"+
          "for-Schleife (char []):\n"+
          "- gefunden: " + count_1.ToString() + "\n" +
          "- Millisekunden: " + (stop_1 - start_1).ToString() + "\n\n" +
          "foreach-Schleife (char[]):\n"+
          "- gefunden: " + count_2.ToString() + "\n" +
          "- Millisekunden: " + (stop_2 - start_2).ToString() + "\n\n" +
          "Array.ForEach:\n"+
          "- gefunden: " + count_3.ToString() + "\n" +
          "- Millisekunden: " + (stop_3 - start_3).ToString() + "\n\n" +
          "for-Schleife (String):\n"+
          "- gefunden: " + count_4.ToString() + "\n" +
          "- Millisekunden: " + (stop_4 - start_4).ToString() + "\n\n" +
          "forach-Schleife (String):\n"+
          "- gefunden: " + count_5.ToString() + "\n" +
          "- Millisekunden: " + (stop_5 - start_5).ToString() + "\n\n" +
          "String.Split:\n"+
          "- gefunden: " + count_6.ToString() + "\n" +
          "- Millisekunden: " + (stop_6 - start_6).ToString() + "\n\n" +
          "String.Replace:\n"+
          "- gefunden: " + count_7.ToString() + "\n" +
          "- Millisekunden: " + (stop_7 - start_7).ToString() + "\n\n" +
          "RegEx.Matches:\n"+
          "- gefunden: " + count_8.ToString() + "\n" +
          "- Millisekunden: " + (stop_8 - start_8).ToString() + "\n\n"
          );
   }
}

herbivore

T
typhos Themenstarter:in
243 Beiträge seit 2006
vor 15 Jahren

Ich danke auch Dir, herbivore. Wenigstens hast Du konstistente Ergebnisse erhalten 🙂

Danke auch für die weiteren Varianten. Interessant, wie viele Wege (und das waren bestimmt noch nicht alle) es für so eine doch relativ simple Aufgabe gibt 👍