Die effizienteste Methode zum Entfernen von Sonderzeichen aus Zeichenfolgen

Ich möchte alle Sonderzeichen aus einer Zeichenfolge entfernen. Zulässige Zeichen sind AZ (Groß- oder Kleinbuchstaben), Zahlen (0-9), Unterstrich (_) oder das Punktzeichen (.).

Ich habe folgendes, es funktioniert, aber ich vermute (ich weiß!), Es ist nicht sehr effizient:

    public static string RemoveSpecialCharacters(string str)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.Length; i++)
        {
            if ((str[i] >= '0' && str[i] <= '9')
                || (str[i] >= 'A' && str[i] <= 'z'
                    || (str[i] == '.' || str[i] == '_')))
                {
                    sb.Append(str[i]);
                }
        }

        return sb.ToString();
    }

Was ist der effizienteste Weg, dies zu tun? Wie würde ein regulärer Ausdruck aussehen und wie ist er mit einer normalen String-Manipulation zu vergleichen?

Die zu bereinigenden Zeichenfolgen sind ziemlich kurz und normalerweise zwischen 10 und 30 Zeichen lang.

Warum ist Ihre Methode Ihrer Meinung nach nicht effizient? Es ist tatsächlich eine der effizientesten Möglichkeiten, dies zu tun.

Sie sollten das Zeichen natürlich in eine lokale Variable einlesen oder einen Enumerator verwenden, um die Anzahl der Array-Zugriffe zu verringern:

public static string RemoveSpecialCharacters(this string str) {
   StringBuilder sb = new StringBuilder();
   foreach (char c in str) {
      if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || c == '.' || c == '_') {
         sb.Append(c);
      }
   }
   return sb.ToString();
}

Eine Sache, die eine solche Methode effizient macht, ist, dass sie gut skaliert. Die Ausführungszeit ist relativ zur Länge der Zeichenfolge. Es gibt keine bösen Überraschungen, wenn Sie es auf einer großen Saite verwenden würden.

Bearbeiten:
Ich habe einen schnellen Leistungstest durchgeführt und jede Funktion millionenfach mit einer 24-stelligen Zeichenfolge ausgeführt. Dies sind die Ergebnisse:

Ursprüngliche Funktion: 54,5 ms.
Meine vorgeschlagene Änderung: 47,1 ms.
Meins mit eingestellter StringBuilder-Kapazität: 43,3 ms.
Regulärer Ausdruck: 294,4 ms.

Edit 2: Ich habe im obigen Code die Unterscheidung zwischen AZ und az hinzugefügt. (Ich habe den Leistungstest erneut durchgeführt, und es gibt keinen erkennbaren Unterschied.)

Edit 3:
Ich habe die Lookup + Char [] -Lösung getestet und sie läuft in ca. 13 ms.

Der zu zahlende Preis ist natürlich die Initialisierung der riesigen Nachschlagetabelle und deren Speicherung. Nun, es sind nicht so viele Daten, aber es ist viel für eine so triviale Funktion ...

private static bool[] _lookup;

static Program() {
   _lookup = new bool[65536];
   for (char c = '0'; c <= '9'; c++) _lookup[c] = true;
   for (char c = 'A'; c <= 'Z'; c++) _lookup[c] = true;
   for (char c = 'a'; c <= 'z'; c++) _lookup[c] = true;
   _lookup['.'] = true;
   _lookup['_'] = true;
}

public static string RemoveSpecialCharacters(string str) {
   char[] buffer = new char[str.Length];
   int index = 0;
   foreach (char c in str) {
      if (_lookup[c]) {
         buffer[index] = c;
         index++;
      }
   }
   return new string(buffer, 0, index);
}

Nun, es sei denn, Sie müssen die Leistung wirklich aus Ihrer Funktion herausholen, wählen Sie einfach das, was am einfachsten zu warten und zu verstehen ist. Ein regulärer Ausdruck würde folgendermaßen aussehen:

Für zusätzliche Leistung können Sie es entweder vorkompilieren oder einfach beim ersten Aufruf kompilieren (nachfolgende Aufrufe sind schneller).

public static string RemoveSpecialCharacters(string str)
{
    return Regex.Replace(str, "[^a-zA-Z0-9_.]+", "", RegexOptions.Compiled);
}

Ich schlage vor, eine einfache Nachschlagetabelle zu erstellen, die Sie im statischen Konstruktor initialisieren können, um eine beliebige Zeichenkombination auf gültig zu setzen. Auf diese Weise können Sie eine schnelle Einzelprüfung durchführen.

bearbeiten

Aus Gründen der Geschwindigkeit sollten Sie auch die Kapazität Ihres StringBuilder auf die Länge Ihrer Eingabezeichenfolge initialisieren. Dadurch werden Neuzuweisungen vermieden. Diese beiden Methoden zusammen bieten Ihnen Geschwindigkeit und Flexibilität.

eine andere Bearbeitung

Ich denke, der Compiler könnte es optimieren, aber aus Gründen des Stils und der Effizienz empfehle ich foreach anstelle von for.

public static string RemoveSpecialCharacters(string str)
{
    char[] buffer = new char[str.Length];
    int idx = 0;

    foreach (char c in str)
    {
        if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z')
            || (c >= 'a' && c <= 'z') || (c == '.') || (c == '_'))
        {
            buffer[idx] = c;
            idx++;
        }
    }

    return new string(buffer, 0, idx);
}

Ein regulärer Ausdruck sieht folgendermaßen aus:

public string RemoveSpecialChars(string input)
{
    return Regex.Replace(input, @"[^0-9a-zA-Z\._]", string.Empty);
}

Wenn die Leistung jedoch sehr wichtig ist, empfehle ich Ihnen, einige Benchmarks durchzuführen, bevor Sie den "Regex-Pfad" auswählen ...

Wenn Sie eine dynamische Liste von Zeichen verwenden, bietet LINQ möglicherweise eine viel schnellere und elegantere Lösung:

public static string RemoveSpecialCharacters(string value, char[] specialCharacters)
{
    return new String(value.Except(specialCharacters).ToArray());
}

Ich habe diesen Ansatz mit zwei der vorherigen "schnellen" Ansätze verglichen (Release-Kompilierung):

• Char Array Lösung von LukeH - 427 ms
• StringBuilder-Lösung - 429 ms
• LINQ (diese Antwort) - 98 ms

Beachten Sie, dass der Algorithmus leicht modifiziert ist - die Zeichen werden als Array übergeben und nicht fest codiert, was sich geringfügig auf die Dinge auswirken könnte (dh die anderen Lösungen hätten eine innere Schleife, um das Zeichenarray zu überprüfen).

Wenn ich mit einer LINQ where-Klausel zu einer fest codierten Lösung wechsle, sind die Ergebnisse:

• Char Array Lösung - 7ms
• StringBuilder-Lösung - 22ms
• LINQ - 60 ms

Es könnte sich lohnen, sich LINQ oder einen modifizierten Ansatz anzusehen, wenn Sie eine allgemeinere Lösung schreiben möchten, anstatt die Liste der Zeichen fest zu codieren. LINQ bietet Ihnen definitiv präzisen, gut lesbaren Code - noch mehr als Regex.

Ich bin nicht davon überzeugt, dass Ihr Algorithmus alles andere als effizient ist. Es ist O (n) und betrachtet jedes Zeichen nur einmal. Besser geht es nicht, wenn Sie die Werte nicht auf magische Weise kennen, bevor Sie sie überprüfen.

Ich würde jedoch die Kapazität von Ihnen initialisieren StringBuilder auf die anfängliche Größe der Zeichenfolge . Ich vermute, dass Ihr wahrgenommenes Leistungsproblem auf die Neuzuweisung von Speicher zurückzuführen ist.

Randnotiz: Überprüfen A - zist nicht sicher. Sie sind einschließlich [, \, ], ^,_ , und `...

Randnotiz 2: Um die Effizienz zu steigern, ordnen Sie die Vergleiche so an, dass die Anzahl der Vergleiche minimiert wird. (Im schlimmsten Fall sprechen Sie von 8 Vergleichen, denken Sie also nicht zu viel nach.) Dies ändert sich mit Ihrer erwarteten Eingabe, aber ein Beispiel könnte sein:

if (str[i] >= '0' && str[i] <= 'z' && 
    (str[i] >= 'a' || str[i] <= '9' ||  (str[i] >= 'A' && str[i] <= 'Z') || 
    str[i] == '_') || str[i] == '.')

Randnotiz 3: Wenn Sie dies aus irgendeinem Grund WIRKLICH benötigen, um schnell zu sein, kann eine switch-Anweisung schneller sein. Der Compiler sollte eine Sprungtabelle für Sie erstellen, die nur einen einzigen Vergleich ergibt:

switch (str[i])
{
    case '0':
    case '1':
    .
    .
    .
    case '.':
        sb.Append(str[i]);
        break;
}

StringBuilder sb = new StringBuilder();

for (int i = 0; i < fName.Length; i++)
{
   if (char.IsLetterOrDigit(fName[i]))
    {
       sb.Append(fName[i]);
    }
}

Sie können den regulären Ausdruck wie folgt verwenden:

return Regex.Replace(strIn, @"[^\w\.@-]", "", RegexOptions.None, TimeSpan.FromSeconds(1.0));

Es scheint mir gut zu sein. Die einzige Verbesserung, die ich machen würde, ist die Initialisierung StringBuildermit der Länge der Zeichenfolge.

StringBuilder sb = new StringBuilder(str.Length);

Ich stimme diesem Codebeispiel zu. Der einzige Unterschied ist, dass ich es in die Erweiterungsmethode vom Typ String mache. Damit Sie es in einer sehr einfachen Zeile oder einem Code verwenden können:

string test = "abc@#$123";
test.RemoveSpecialCharacters();

Vielen Dank an Guffa für Ihr Experiment.

public static class MethodExtensionHelper
    {
    public static string RemoveSpecialCharacters(this string str)
        {
            StringBuilder sb = new StringBuilder();
            foreach (char c in str)
            {
                if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || c == '_')
                {
                    sb.Append(c);
                }
            }
            return sb.ToString();
        }
}

Ich würde einen String-Ersatz durch einen regulären Ausdruck verwenden, der nach "Sonderzeichen" sucht und alle gefundenen Zeichen durch einen leeren String ersetzt.

Ich musste etwas Ähnliches für die Arbeit tun, aber in meinem Fall musste ich alles filtern, was kein Buchstabe, keine Zahl oder kein Leerzeichen ist (aber Sie können es leicht an Ihre Bedürfnisse anpassen). Die Filterung erfolgt clientseitig in JavaScript, aber aus Sicherheitsgründen mache ich die Filterung auch serverseitig. Da ich davon ausgehen kann, dass die meisten Zeichenfolgen sauber sind, möchte ich das Kopieren der Zeichenfolge vermeiden, es sei denn, ich muss es wirklich tun. Dies führte mich zur folgenden Implementierung, die sowohl für saubere als auch für schmutzige Zeichenfolgen eine bessere Leistung erbringen sollte.

public static string EnsureOnlyLetterDigitOrWhiteSpace(string input)
{
    StringBuilder cleanedInput = null;
    for (var i = 0; i < input.Length; ++i)
    {
        var currentChar = input[i];
        var charIsValid = char.IsLetterOrDigit(currentChar) || char.IsWhiteSpace(currentChar);

        if (charIsValid)
        {
            if(cleanedInput != null)
                cleanedInput.Append(currentChar);
        }
        else
        {
            if (cleanedInput != null) continue;
            cleanedInput = new StringBuilder();
            if (i > 0)
                cleanedInput.Append(input.Substring(0, i));
        }
    }

    return cleanedInput == null ? input : cleanedInput.ToString();
}

Für S & Gs, Linq-ified Weg:

var original = "(*^%foo)(@)&^@#><>?:\":';=-+_";
var valid = new char[] { 
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 
    'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 
    'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 
    'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '1', '2', '3', '4', '5', '6', '7', '8', 
    '9', '0', '.', '_' };
var result = string.Join("",
    (from x in original.ToCharArray() 
     where valid.Contains(x) select x.ToString())
        .ToArray());

Ich denke jedoch nicht, dass dies der effizienteste Weg sein wird.

public string RemoveSpecial(string evalstr)
{
StringBuilder finalstr = new StringBuilder();
            foreach(char c in evalstr){
            int charassci = Convert.ToInt16(c);
            if (!(charassci >= 33 && charassci <= 47))// special char ???
             finalstr.append(c);
            }
return finalstr.ToString();
}

Verwenden:

s.erase(std::remove_if(s.begin(), s.end(), my_predicate), s.end());

bool my_predicate(char c)
{
 return !(isalpha(c) || c=='_' || c==' '); // depending on you definition of special characters
}

Und du bekommst eine saubere Schnur s.

erase()entfernt alle Sonderzeichen und ist mit der my_predicate()Funktion hochgradig anpassbar .

HashSet ist O (1)
Nicht sicher, ob es schneller als der vorhandene Vergleich ist

private static HashSet<char> ValidChars = new HashSet<char>() { 'a', 'b', 'c', 'A', 'B', 'C', '1', '2', '3', '_' };
public static string RemoveSpecialCharacters(string str)
{
    StringBuilder sb = new StringBuilder(str.Length / 2);
    foreach (char c in str)
    {
        if (ValidChars.Contains(c)) sb.Append(c);
    }
    return sb.ToString();
}

Ich habe getestet und dies nicht schneller als die akzeptierte Antwort.
Ich werde es so lassen, als ob Sie einen konfigurierbaren Satz von Zeichen benötigen würden. Dies wäre eine gute Lösung.

Ich frage mich, ob ein Regex-basierter Ersatz (möglicherweise kompiliert) schneller ist. Müsste das testen jemand festgestellt hat, dass dies ~ 5 mal langsamer ist.

Ansonsten sollten Sie den StringBuilder mit einer erwarteten Länge initialisieren, damit der Zwischenstring nicht kopiert werden muss, während er wächst.

Eine gute Zahl ist die Länge der ursprünglichen Zeichenfolge oder etwas etwas niedrigeres (abhängig von der Art der Funktionseingaben).

Schließlich können Sie eine Nachschlagetabelle (im Bereich 0..127) verwenden, um herauszufinden, ob ein Zeichen akzeptiert werden soll.

Der folgende Code hat die folgende Ausgabe (Schlussfolgerung ist, dass wir auch einige Speicherressourcen sparen können, die dem Array eine kleinere Größe zuweisen):

lookup = new bool[123];

for (var c = '0'; c <= '9'; c++)
{
    lookup[c] = true; System.Diagnostics.Debug.WriteLine((int)c + ": " + (char)c);
}

for (var c = 'A'; c <= 'Z'; c++)
{
    lookup[c] = true; System.Diagnostics.Debug.WriteLine((int)c + ": " + (char)c);
}

for (var c = 'a'; c <= 'z'; c++)
{
    lookup[c] = true; System.Diagnostics.Debug.WriteLine((int)c + ": " + (char)c);
}

48: 0  
49: 1  
50: 2  
51: 3  
52: 4  
53: 5  
54: 6  
55: 7  
56: 8  
57: 9  
65: A  
66: B  
67: C  
68: D  
69: E  
70: F  
71: G  
72: H  
73: I  
74: J  
75: K  
76: L  
77: M  
78: N  
79: O  
80: P  
81: Q  
82: R  
83: S  
84: T  
85: U  
86: V  
87: W  
88: X  
89: Y  
90: Z  
97: a  
98: b  
99: c  
100: d  
101: e  
102: f  
103: g  
104: h  
105: i  
106: j  
107: k  
108: l  
109: m  
110: n  
111: o  
112: p  
113: q  
114: r  
115: s  
116: t  
117: u  
118: v  
119: w  
120: x  
121: y  
122: z  

Sie können auch die folgenden Codezeilen hinzufügen, um das russische Gebietsschema zu unterstützen (die Arraygröße beträgt 1104):

for (var c = 'А'; c <= 'Я'; c++)
{
    lookup[c] = true; System.Diagnostics.Debug.WriteLine((int)c + ": " + (char)c);
}

for (var c = 'а'; c <= 'я'; c++)
{
    lookup[c] = true; System.Diagnostics.Debug.WriteLine((int)c + ": " + (char)c);
}

Ich bin nicht sicher, ob es der effizienteste Weg ist, aber es funktioniert für mich

 Public Function RemoverTildes(stIn As String) As String
    Dim stFormD As String = stIn.Normalize(NormalizationForm.FormD)
    Dim sb As New StringBuilder()

    For ich As Integer = 0 To stFormD.Length - 1
        Dim uc As UnicodeCategory = CharUnicodeInfo.GetUnicodeCategory(stFormD(ich))
        If uc <> UnicodeCategory.NonSpacingMark Then
            sb.Append(stFormD(ich))
        End If
    Next
    Return (sb.ToString().Normalize(NormalizationForm.FormC))
End Function

Hier werden viele Lösungen vorgeschlagen, von denen einige effizienter als andere sind, aber möglicherweise nicht sehr gut lesbar. Hier ist eine, die möglicherweise nicht die effizienteste ist, aber für die meisten Situationen durchaus verwendbar ist. Sie ist recht präzise und lesbar und nutzt Linq:

string stringToclean = "This is a test.  Do not try this at home; you might get hurt. Don't believe it?";

var validPunctuation = new HashSet<char>(". -");

var cleanedVersion = new String(stringToclean.Where(x => (x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z') || validPunctuation.Contains(x)).ToArray());

var cleanedLowercaseVersion = new String(stringToclean.ToLower().Where(x => (x >= 'a' && x <= 'z') || validPunctuation.Contains(x)).ToArray());

public static string RemoveSpecialCharacters(string str){
    return str.replaceAll("[^A-Za-z0-9_\\\\.]", "");
}

public static string RemoveAllSpecialCharacters(this string text) {
  if (string.IsNullOrEmpty(text))
    return text;

  string result = Regex.Replace(text, "[:!@#$%^&*()}{|\":?><\\[\\]\\;'/.,~]", " ");
  return result;
}

Wenn Sie sich Gedanken über die Geschwindigkeit machen, verwenden Sie Zeiger, um die vorhandene Zeichenfolge zu bearbeiten. Sie könnten die Zeichenfolge anheften und einen Zeiger darauf erhalten, dann eine for-Schleife über jedes Zeichen ausführen und jedes ungültige Zeichen mit einem Ersatzzeichen überschreiben. Es wäre äußerst effizient und würde keine Zuweisung eines neuen Zeichenfolgenspeichers erfordern. Sie müssten Ihr Modul auch mit der Option "unsicher" kompilieren und den Modifikator "unsicher" zu Ihrem Methodenheader hinzufügen, um Zeiger zu verwenden.

static void Main(string[] args)
{
    string str = "string!$%with^&*invalid!!characters";
    Console.WriteLine( str ); //print original string
    FixMyString( str, ' ' );
    Console.WriteLine( str ); //print string again to verify that it has been modified
    Console.ReadLine(); //pause to leave command prompt open
}


public static unsafe void FixMyString( string str, char replacement_char )
{
    fixed (char* p_str = str)
    {
        char* c = p_str; //temp pointer, since p_str is read-only
        for (int i = 0; i < str.Length; i++, c++) //loop through each character in string, advancing the character pointer as well
            if (!IsValidChar(*c)) //check whether the current character is invalid
                (*c) = replacement_char; //overwrite character in existing string with replacement character
    }
}

public static bool IsValidChar( char c )
{
    return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c == '.' || c == '_');
    //return char.IsLetterOrDigit( c ) || c == '.' || c == '_'; //this may work as well
}