Laden...

(Schnellste) Beste Variante für mehrere String-Ersetzungen?

Erstellt von moelski vor 10 Jahren Letzter Beitrag vor 10 Jahren 3.089 Views
M
moelski Themenstarter:in
183 Beiträge seit 2011
vor 10 Jahren
(Schnellste) Beste Variante für mehrere String-Ersetzungen?

Moin !

Ich möchte in einem Terminalprogramm das RS232 und TCP Daten empfängt gerne die empfangenen Daten u.a. als String darstellen. Das führt aber logischerweise zu Problemen sobald Steuerzeichen ins Spiel kommen (Zeichen 0-31).

Nun würde ich gerne bei eintreffenden Strings diese Zeichen ersetzen. z.B. "\r" in "<CR>" oder auch "0x0D". Was ist dafür die schnellste Variante? Spontan würde ich ja erstmal die normale Replace Methode verwenden. Bin mir aber nicht sicher ob das der sinnvollste und schnellste Weg ist. Ich müsste ja dann 32 Replaces an den String hängen ... 🤔

Hat evtl. jemand eine bessere (und evtl. auch schnellere) Variante zur Hand?

Greetz Dominik

185 Beiträge seit 2005
vor 10 Jahren

Warum ignorierst du die Steuerzeichen nicht schon in deiner Empfangsroutine?

I
57 Beiträge seit 2011
vor 10 Jahren

Stringbuilder Replace sollte da beim nachträglichen Replace am schnellsten gehen.

M
moelski Themenstarter:in
183 Beiträge seit 2011
vor 10 Jahren

Moin,

Warum ignorierst du die Steuerzeichen nicht schon in deiner Empfangsroutine?

Weil ich die Daten gerne sehen und analysierenmöchte 😉

Stringbuilder Replace sollte da beim nachträglichen Replace am schnellsten gehen.

Danke. Dann werde ich das mal damit versuchen.

Greetz Dominik

1.002 Beiträge seit 2007
vor 10 Jahren

Hallo moelski,

on top of my head:

string source = "...";
string cleaned = Regex.Replace(source, @"[\u0000-\u001F]", string.Empty);

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

M
moelski Themenstarter:in
183 Beiträge seit 2011
vor 10 Jahren

Moin !

@m0rius:
Ich will ja die Sonderzeichen nicht raus filtern sondern durch was lesbares ersetzen. Insofern hilft dein Ansatz nur bedingt.

Greetz Dominik

656 Beiträge seit 2008
vor 10 Jahren

Es gibt auch Regex.Replace Overloads, die Callbacks anbieten. Ob das ganze auch performt, ist natürlich eine andere Geschichte...

1.002 Beiträge seit 2007
vor 10 Jahren

Hallo moelski,

natürlich. Sorry, muss deine Frage vorhin nur überflogen haben. Zum Ersetzen durch lesbare Strings ist meine Methode natürlich ungeeignet.

Trotzdem würde ich 32 Aufrufe von Replace vermeiden, schon aus Gründen der Übersichtlichkeit und Wartbarkeit.

var controlCharReplacements = new Dictionary<string, string>
{
    { "\u0000", "Hier deine Ersetzungen" },
    { "...", "..." }
};

string input = "";
foreach (var replacement in controlCharReplacements)
{
    input = input.Replace(replacement.Key, replacement.Value);
}

Analog kannst du die Replace-Operation natürlich auch auf einem StringBuilder ausführen.

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

49.485 Beiträge seit 2005
vor 10 Jahren

Hallo moelski,

warum suchst du nach der schnellsten Methode? Hast du Geschwindigkeitsprobleme festgestellt? Ich würde an deiner Stelle erstmal nach der lesbarsten/wartbarsten Methode suchen und erst wenn es damit spürbare Performance-Probleme gibt, nach Geschwindigkeitsoptimierungen suchen. Getreu dem Motto: premature optimization is the root of all evil.

herbivore

742 Beiträge seit 2005
vor 10 Jahren

Am schnellsten dürfte sowas sein:



public string Replace(string in) 
{
    var sb = new StringBuilder();

   foreach (char c in in)
   {
       if (c == 'SpecialChar') {
          sb.Append('A');
       } else if (c == ) {
       } else {
          sb.Append(c);
       }
   }

   return sb.ToString();
}

49.485 Beiträge seit 2005
vor 10 Jahren

Hallo malignate,

nö, ziemlich sicher nicht. Bei diesem Code sind für jedes Nicht-Steuerzeichen 32 Abfragen nötig. Ungünstigerweise also gerade für die Zeichen, die wohl am häufigsten vorkommen, die meisten Abfragen. Es ist sicher schneller, zuerst auf den Bereich der Steuerzeichen abzufragen (da char vorzeichenlos ist, ist das mit einer Abfrage c < 32 getan) und wenn das Zeichen in diesem Bereich liegt, es als Index in ein String-Array der Länge 32 zu verwenden, das die Ersetzungs-Strings enthält. Dann hat man statt 32 Abfragen eine und einen Indexzugriff. Und wenn es schon um Geschwindigkeit geht, sollte foreach durch for ersetzt werden und StringBuilder mit in.Length oder 2*in.Length initialisiert werden oder besser gleich ein char-Array verwendet werden, weil das weniger Overhead als StringBuilder hat. Aber vermutlich geht es überhaupt nicht um Geschwindigkeit, deshalb führe ich weitere solche premature optimizations hier gar nicht erst aus. 😃

herbivore

M
moelski Themenstarter:in
183 Beiträge seit 2011
vor 10 Jahren

Moin !

@herbivore:

Aber vermutlich geht es überhaupt nicht um Geschwindigkeit

Das sehe ich etwas anders. Du hast schon Recht das im Moment kein Engpass vorliegt. Aber wie ich im ersten Post schon schrieb möchte ich auch die Daten die vom Netzwerk kommen in einem Logging festhalten. Und da können sehr schnell viele Daten kommen. Und dann könnte ich mir schon vorstellen das man an dieser Konvertierung etwas optimieren kann und sollte.

Ich habe mal deine Ideen in eine Funktion gegossen. Rausgekommen ist das hier:

        public string ReplaceSpecials(string input)
        {
            string[] change =
            {
                "<NUL>", "<SOH>", "<STX>", "<ETX>", "<EOT>", "<ENQ>", "<ACK>", "<BEL>", "<BS>", "<TAB>", "<LF>", "<VT>", "<FF>",
                "<CR>", "<SO>", "<SI>", "<DLE>", "<DC1>", "<DC2>", "<DC3>", "<DC4>", "<NAK>", "<SYN>", "<ETB>", "<CAN>", "<EM>",
                "<SUB>", "<Esc>", "<FS>", "<GS>", "<RS>", "<US>"
            };

            var sb = new StringBuilder(input.Length * 3);

            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] > 31)
                {
                    sb.Append(input[i]);
                }
                else
                {
                    sb.Append(change[input[i]]);
                }
            }

            return sb.ToString();
        }

Was jetzt noch fehlt wäre die Verwendung eines Char Arrays. Das lass ich mal für eine weitere Optimierung offen 🙂

Greetz Dominik

16.807 Beiträge seit 2008
vor 10 Jahren

Ich behaupte, dass gar nicht so viel Nachrichten reinkommen können, wie Du zeitgleich verarbeiten kannst.
Ergo stimme ich herbivore zu und sage, dass das Optimieren solange sinnlos ist, bis wirklich ein Flaschenhals entstehen könnte.

M
moelski Themenstarter:in
183 Beiträge seit 2011
vor 10 Jahren

Die Lösung reicht mir auch erstmal.

Danke allen für die Infos und Ideen.

Greetz Dominik

49.485 Beiträge seit 2005
vor 10 Jahren

Hallo moelski,

ich sehe es wie Abt, dass der Flaschenhals die Datenübertragung sein sollte, insbesondere wenn wir über RS232 reden.

Trotzdem hat mich interessiert, wie groß die Laufzeitzunterschiede zwischen verschiedenen Implementierungsvarianten sind. Dabei habe ich jede zwei verschiedene Input-Strings verwendet: einen, bei dem durchschnittlich ein Steuerzeichen auf drei normale Zeichen kommt, und einen, bei dem durchschnittlich nur ein Steuerzeichen auf 96 normale Zeichen kommt. Beide Strings hatten eine Länge von 1Mio Zeichen. Erst als ich jede Implementierungsvariante 20mal pro Megabyte großem Input-String aufgerufen habe, kamen überhaupt Laufzeiten heraus, die nennenswert waren. Das unterstehende Programm habe ich dann wiederum 20mal laufen lassen, und jeweils jeweils den Median der einzelnen Messwerte verwendet, um Schwankungen und vor allem Ausreißer auszuschließen.

Hier die Aufstellung für die verschiedenen Implementierungsvarianten absteigend sortiert nach der Laufzeit in Millisekunden:

[pre]
Viele Steuerzeichen (1:3)
ReplaceNaive              : 5435
ReplaceRegex              : 2774
ReplaceIfForeach          :  825
ReplaceCaseFor            :  324
ReplaceCaseForeach        :  322
ReplaceArrayForUnsafeInit1:  319
ReplaceArrayForUnsafeInit2:  302
ReplaceArrayForInit       :  293
ReplaceArrayFor           :  291
ReplaceArrayForeach       :  288

Wenige Steuerzeichen (1:96)
ReplaceNaive              : 4178
ReplaceIfForeach          :  784
ReplaceRegex              :  626
ReplaceArrayForUnsafeInit1:  187
ReplaceArrayForUnsafeInit2:  170
ReplaceArrayForInit       :  161
ReplaceArrayFor           :  158
ReplaceArrayForeach       :  156
ReplaceCaseFor            :  156
ReplaceCaseForeach        :  155
[/pre]

Hier noch einige Anmerkungen:
*Wie man sieht, ist die von mir unter dem Gesichtspunkt der Performance vorgeschlagene Variante mit Ersetzungs-Array bei vielen Steuerzeichen am schnellsten. Bei wenigen Steuerzeichen ist die Variante mit Case noch einen Tick schneller, aber die Variante mit Ersetzungs-Array folgt fast zeitgleich auf dem zweiten Platz. Daher sollte sie in Sachen Performance die beste Wahl sein. *Dass foreach genauso schnell ist wie for (sogar minimal schneller), liegt daran, dass der Compiler bei Arrays - und anscheinend auch bei Strings - foreach nicht durch while+Enumerator ersetzt sondern durch for+Indexzugriff). Das steht sogar irgendwo in der Sprachspezifikation. Noch ein Grund mehr gegen händische Mikrooptimierungen. *Genauso wie bei der Vorinitialisierung des StringBuilders, die minimal langsamer ist. *Die Unsafe-Varianten, die ich vor dem Test als Sieger vermutet hätte, sind vermutlich deshalb langsamer, weil der String vor dem Zugriff per Pointer anscheinend einmal umkopiert wird. *Im übrigen ist es mir nicht gelungen, eine Variante mit char-Array zu schreiben, die den StringBuilder schlägt. Anscheinend gibt es auch da irgendwelche Compiler-Optimierungen, die den StringBuilder derart gut dastehen lässt. *Am kürzesten und - je nach Vorlieben auch - am lesbarsten ist die Variante mit Regex, die sich performance-mäßig nicht mal schlecht schlägt, sofern der Anteil der Sonderzeichen nicht zu groß wird. *Die Regex-Variante ist in diesem Fall sogar schneller als der Vorschlag von malignate und damit sicher einer heißer Kandidat für die insgesamt beste Variante.

Hier die Varianten inkl. Testcode als lauffähiges Programm (wegen der enthaltenen unsafe-Varianten musst der Code mit dem Schalter /unsafe übersetzt werden oder die unsafe-Varianten müssen auskommentiert werden):


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

static class App
{
   //--------------------------------------------------------------------------
   // Übersetzungstabelle (wird von mehreren Varianten benötigt)
   private static readonly string [] replace = {
      "C00", "C01", "C02", "C03", "C04", "C05", "C06", "C07",
      "C08", "C09", "C0A", "C0B", "C0C", "C0D", "C0E", "C0F",
      "C10", "C11", "C12", "C13", "C14", "C15", "C16", "C17",
      "C18", "C19", "C1A", "C1B", "C1C", "C1D", "C1E", "C1F"
   };

   //==========================================================================
   public static string ReplaceNaive (String input)
   {
      return input.Replace ("\x00", "C00")
                  .Replace ("\x01", "C01")
                  .Replace ("\x02", "C02")
                  .Replace ("\x03", "C03")
                  .Replace ("\x04", "C04")
                  .Replace ("\x05", "C05")
                  .Replace ("\x06", "C06")
                  .Replace ("\x07", "C07")
                  .Replace ("\x08", "C08")
                  .Replace ("\x09", "C09")
                  .Replace ("\x0A", "C0A")
                  .Replace ("\x0B", "C0B")
                  .Replace ("\x0C", "C0C")
                  .Replace ("\x0D", "C0D")
                  .Replace ("\x0E", "C0E")
                  .Replace ("\x0F", "C0F")
                  .Replace ("\x10", "C10")
                  .Replace ("\x11", "C11")
                  .Replace ("\x12", "C12")
                  .Replace ("\x13", "C13")
                  .Replace ("\x14", "C14")
                  .Replace ("\x15", "C15")
                  .Replace ("\x16", "C16")
                  .Replace ("\x17", "C17")
                  .Replace ("\x18", "C18")
                  .Replace ("\x19", "C19")
                  .Replace ("\x1A", "C1A")
                  .Replace ("\x1B", "C1B")
                  .Replace ("\x1C", "C1C")
                  .Replace ("\x1D", "C1D")
                  .Replace ("\x1E", "C1E")
                  .Replace ("\x1F", "C1F");
   }

   //==========================================================================
   public static string ReplaceRegex (String input)
   {
      return Regex.Replace (input, "[\x00-\x1f]", m => replace [(int)m.Value[0]]);
   }

   //==========================================================================
   public static string ReplaceIfForeach (String input)
   {
      var output = new StringBuilder ();

      foreach (char c in input) {
          if (c == '\x00')         { output.Append ("C00");
          } else if (c == '\x01' ) { output.Append ("C01");
          } else if (c == '\x02' ) { output.Append ("C02");
          } else if (c == '\x03' ) { output.Append ("C03");
          } else if (c == '\x04' ) { output.Append ("C04");
          } else if (c == '\x05' ) { output.Append ("C05");
          } else if (c == '\x06' ) { output.Append ("C06");
          } else if (c == '\x07' ) { output.Append ("C07");
          } else if (c == '\x08' ) { output.Append ("C08");
          } else if (c == '\x09' ) { output.Append ("C09");
          } else if (c == '\x0A' ) { output.Append ("C0A");
          } else if (c == '\x0B' ) { output.Append ("C0B");
          } else if (c == '\x0C' ) { output.Append ("C0C");
          } else if (c == '\x0D' ) { output.Append ("C0D");
          } else if (c == '\x0E' ) { output.Append ("C0E");
          } else if (c == '\x0F' ) { output.Append ("C0F");
          } else if (c == '\x10' ) { output.Append ("C10");
          } else if (c == '\x11' ) { output.Append ("C11");
          } else if (c == '\x12' ) { output.Append ("C12");
          } else if (c == '\x13' ) { output.Append ("C13");
          } else if (c == '\x14' ) { output.Append ("C14");
          } else if (c == '\x15' ) { output.Append ("C15");
          } else if (c == '\x16' ) { output.Append ("C16");
          } else if (c == '\x17' ) { output.Append ("C17");
          } else if (c == '\x18' ) { output.Append ("C18");
          } else if (c == '\x19' ) { output.Append ("C19");
          } else if (c == '\x1A' ) { output.Append ("C1A");
          } else if (c == '\x1B' ) { output.Append ("C1B");
          } else if (c == '\x1C' ) { output.Append ("C1C");
          } else if (c == '\x1D' ) { output.Append ("C1D");
          } else if (c == '\x1E' ) { output.Append ("C1E");
          } else if (c == '\x1F' ) { output.Append ("C1F");
          } else {                   output.Append (c);
          }
      }

      return output.ToString ();
   }

   //==========================================================================
   public static string ReplaceCaseForeach (String input)
   {
      var output = new StringBuilder ();

      foreach (char c in input) {
         switch (c) {
            case '\x00': output.Append ("C00"); break;
            case '\x01': output.Append ("C01"); break;
            case '\x02': output.Append ("C02"); break;
            case '\x03': output.Append ("C03"); break;
            case '\x04': output.Append ("C04"); break;
            case '\x05': output.Append ("C05"); break;
            case '\x06': output.Append ("C06"); break;
            case '\x07': output.Append ("C07"); break;
            case '\x08': output.Append ("C08"); break;
            case '\x09': output.Append ("C09"); break;
            case '\x0A': output.Append ("C0A"); break;
            case '\x0B': output.Append ("C0B"); break;
            case '\x0C': output.Append ("C0C"); break;
            case '\x0D': output.Append ("C0D"); break;
            case '\x0E': output.Append ("C0E"); break;
            case '\x0F': output.Append ("C0F"); break;
            case '\x10': output.Append ("C10"); break;
            case '\x11': output.Append ("C11"); break;
            case '\x12': output.Append ("C12"); break;
            case '\x13': output.Append ("C13"); break;
            case '\x14': output.Append ("C14"); break;
            case '\x15': output.Append ("C15"); break;
            case '\x16': output.Append ("C16"); break;
            case '\x17': output.Append ("C17"); break;
            case '\x18': output.Append ("C18"); break;
            case '\x19': output.Append ("C19"); break;
            case '\x1A': output.Append ("C1A"); break;
            case '\x1B': output.Append ("C1B"); break;
            case '\x1C': output.Append ("C1C"); break;
            case '\x1D': output.Append ("C1D"); break;
            case '\x1E': output.Append ("C1E"); break;
            case '\x1F': output.Append ("C1F"); break;
            default:     output.Append (c);     break;
         }
      }

      return output.ToString ();
   }

   //==========================================================================
   public static string ReplaceCaseFor (String input)
   {
      int length = input.Length;
      var output = new StringBuilder ();

      for (int i = 0; i < length; ++i) {
         char c = input [i];
         switch (c) {
            case '\x00': output.Append ("C00"); break;
            case '\x01': output.Append ("C01"); break;
            case '\x02': output.Append ("C02"); break;
            case '\x03': output.Append ("C03"); break;
            case '\x04': output.Append ("C04"); break;
            case '\x05': output.Append ("C05"); break;
            case '\x06': output.Append ("C06"); break;
            case '\x07': output.Append ("C07"); break;
            case '\x08': output.Append ("C08"); break;
            case '\x09': output.Append ("C09"); break;
            case '\x0A': output.Append ("C0A"); break;
            case '\x0B': output.Append ("C0B"); break;
            case '\x0C': output.Append ("C0C"); break;
            case '\x0D': output.Append ("C0D"); break;
            case '\x0E': output.Append ("C0E"); break;
            case '\x0F': output.Append ("C0F"); break;
            case '\x10': output.Append ("C10"); break;
            case '\x11': output.Append ("C11"); break;
            case '\x12': output.Append ("C12"); break;
            case '\x13': output.Append ("C13"); break;
            case '\x14': output.Append ("C14"); break;
            case '\x15': output.Append ("C15"); break;
            case '\x16': output.Append ("C16"); break;
            case '\x17': output.Append ("C17"); break;
            case '\x18': output.Append ("C18"); break;
            case '\x19': output.Append ("C19"); break;
            case '\x1A': output.Append ("C1A"); break;
            case '\x1B': output.Append ("C1B"); break;
            case '\x1C': output.Append ("C1C"); break;
            case '\x1D': output.Append ("C1D"); break;
            case '\x1E': output.Append ("C1E"); break;
            case '\x1F': output.Append ("C1F"); break;
            default:     output.Append (c);     break;
         }
      }

      return output.ToString ();
   }

   //==========================================================================
   public static string ReplaceArrayForeach (String input)
   {
      var output = new StringBuilder ();

      foreach (char c in input) {
         if (c < 32) {
            output.Append (replace [(int)c]);
         } else {
            output.Append (c);
         }
      }

      return output.ToString ();
   }

   //==========================================================================
   public static string ReplaceArrayFor (String input)
   {
      int length = input.Length;
      var output = new StringBuilder ();

      for (int i = 0; i < length; ++i) {
         char c = input [i];
         if (c < 32) {
            output.Append (replace [(int)c]);
         } else {
            output.Append (c);
         }
      }

      return output.ToString ();
   }

   //==========================================================================
   public static string ReplaceArrayForInit (String input)
   {
      int length = input.Length;
      var output = new StringBuilder (length);

      for (int i = 0; i < length; ++i) {
         char c = input [i];
         if (c < 32) {
            output.Append (replace [(int)c]);
         } else {
            output.Append (c);
         }
      }

      return output.ToString ();
   }

   //==========================================================================
   public static string ReplaceArrayForUnsafeInit1 (String input)
   {
      unsafe {
         int length = input.Length;
         var output = new StringBuilder (length);
         char [] i = input.ToCharArray ();

         fixed (char* start = i)
         {
            char* end = start + length;
            for (char* curr = start; curr < end; ++curr) {
               if (*curr < 32) {
                  output.Append (replace [(int)*curr]);
               } else {
                  output.Append (*curr);
               }
            }
         }

         return output.ToString ();
      }
   }

   //==========================================================================
   public static string ReplaceArrayForUnsafeInit2 (String input)
   {
      unsafe {
         int length = input.Length;
         var output = new StringBuilder (length);

         char* start = (char*)System.Runtime.InteropServices.Marshal.StringToHGlobalAuto (input);
         char* end = start + length;
         for (char* curr = start; curr < end; ++curr) {
            if (*curr < 32) {
               output.Append (replace [(int)*curr]);
            } else {
               output.Append (*curr);
            }
         }

         return output.ToString ();
      }
   }

   //==========================================================================
   public static void Main (string [] astrArg)
   {
      const int calls  = 20;
      const int length = 1000000;

      Stopwatch sw = new Stopwatch ();
      Random rand = new Random (4711);
      char [] [] inputs = new char [2] [];

      inputs [0] = new char [length];
      inputs [1] = new char [length];

      for (int i = 0; i < length; ++i) {
         inputs [0] [i] = (char)(rand.Next (128));
         inputs [1] [i] = (char)(rand.Next (128-32+1) + 31);
         if (inputs [1] [i] == 31) {
            inputs [1] [i] = (char)rand.Next (32);
         }
      }

      String [] inputStrings = new String [] {
         new String (inputs [0]),
         new String (inputs [1])
      };
      String outputString = null;
      String [] compareStrings = new String [] {
         ReplaceNaive (inputStrings [0]),
         ReplaceNaive (inputStrings [1])
      };

      for (int i = 0; i < 2; ++i) {
         if (i == 0) {
            Console.WriteLine ("Viele Steuerzeichen (1:3)");
         } else {
            Console.WriteLine ("Wenige Steuerzeichen (1:96)");
         }
         foreach (var method in typeof (App).GetMethods ()) {
            if (!method.Name.StartsWith ("Replace")) {
               continue;
            }

            sw.Reset ();
            sw.Start ();
            for (int call = 0; call < calls; ++call) {
               outputString = (String)method.Invoke (null, new Object [] { inputStrings [i] });
            }
            sw.Stop ();

            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();

            if (outputString != compareStrings [i]) {
               Console.WriteLine ("ERROR");
            }

            Console.WriteLine ("{0,-26}: {1,4}", method.Name, sw.ElapsedMilliseconds);
         }
         Console.WriteLine ();
      }
   }
}

herbivore

M
moelski Themenstarter:in
183 Beiträge seit 2011
vor 10 Jahren

Moin !

WOW 8o
Danke für diesen ausführlichen Test samt Erklärungen !

Meine Variante entspricht ja dann deinem ReplaceArrayForInit.
Ist also nicht so langsam 👍

dass der Flaschenhals die Datenübertragung sein sollte, insbesondere wenn wir über RS232 reden.

Bei RS232 bin ich da voll bei euch. Und für den TCP Traffic wird es dann wohl auch hinreichend optimiert sein 🙂

Greetz Dominik