Najbardziej wydajny sposób usuwania znaków specjalnych z łańcucha

Chcę usunąć wszystkie znaki specjalne z ciągu. Dozwolone znaki to AZ (wielkie lub małe), cyfry (0–9), podkreślenie (_) lub znak kropki (.).

Mam następujące, działa, ale podejrzewam (wiem!), Że to nie jest bardzo wydajne:

    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();
    }

Jaki jest najbardziej efektywny sposób to zrobić? Jak wyglądałoby wyrażenie regularne i jak się ma do normalnej manipulacji ciągiem?

Ciągi, które będą czyszczone, będą raczej krótkie, zwykle o długości od 10 do 30 znaków.

Dlaczego uważasz, że twoja metoda nie jest wydajna? To w rzeczywistości jeden z najbardziej wydajnych sposobów, w jaki możesz to zrobić.

Oczywiście powinieneś odczytać znak do zmiennej lokalnej lub użyć modułu wyliczającego, aby zmniejszyć liczbę dostępów do tablicy:

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();
}

Jedną z rzeczy, która sprawia, że ​​taka metoda jest skuteczna, jest jej dobre skalowanie. Czas wykonania będzie zależny od długości łańcucha. Nie ma nieprzyjemnych niespodzianek, jeśli użyjesz go na dużym sznurku.

Edytować:
Zrobiłem szybki test wydajności, uruchamiając każdą funkcję milion razy z ciągiem 24 znaków. Oto wyniki:

Oryginalna funkcja: 54,5 ms.
Moja sugerowana zmiana: 47,1 ms.
Kopalnia z ustawieniem Pojemność StringBuilder: 43,3 ms.
Wyrażenie regularne: 294,4 ms.

Edycja 2: Dodałem rozróżnienie między AZ i az w powyższym kodzie. (Zmieniłem test wydajności i nie ma zauważalnej różnicy).

Edycja 3:
Przetestowałem rozwiązanie lookup + char [] i działa ono w około 13 ms.

Cena do zapłaty to oczywiście inicjalizacja ogromnej tabeli odnośników i zachowanie jej w pamięci. Cóż, to nie jest tak dużo danych, ale dużo za tak banalną funkcję ...

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);
}

Cóż, chyba że naprawdę musisz wycisnąć wydajność z funkcji, po prostu wybierz to, co najłatwiejsze do utrzymania i zrozumienia. Wyrażenie regularne wyglądałoby tak:

Aby zwiększyć wydajność, możesz albo go wstępnie skompilować, albo po prostu poprosić o kompilację przy pierwszym wywołaniu (kolejne połączenia będą szybsze).

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

Sugeruję utworzenie prostej tabeli odnośników, którą można zainicjować w konstruktorze statycznym, aby ustawić prawidłową kombinację znaków. Umożliwia to szybką, pojedynczą kontrolę.

edytować

Ponadto, dla szybkości, będziesz chciał zainicjować pojemność swojego StringBuilder do długości łańcucha wejściowego. Pozwoli to uniknąć realokacji. Te dwie metody razem zapewnią zarówno szybkość, jak i elastyczność.

kolejna edycja

Myślę, że kompilator może go zoptymalizować, ale ze względu na styl, a także wydajność, polecam foreach zamiast 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);
}

Wyrażenie regularne będzie wyglądać następująco:

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

Ale jeśli wydajność jest bardzo ważna, zalecamy wykonanie testów porównawczych przed wybraniem „ścieżki wyrażeń regularnych” ...

Jeśli używasz dynamicznej listy znaków, LINQ może zaoferować znacznie szybsze i pełne wdzięku rozwiązanie:

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

Porównałem to podejście z dwoma poprzednimi „szybkimi” podejściami (kompilacja wydania):

• Rozwiązanie tablicy Char według Łukasza - 427 ms
• Rozwiązanie StringBuilder - 429 ms
• LINQ (ta odpowiedź) - 98 ms

Zauważ, że algorytm jest nieco zmodyfikowany - znaki są przekazywane jako tablica, a nie na stałe, co może mieć niewielki wpływ na rzeczy (tj. / Inne rozwiązania miałyby wewnętrzną pętlę Foor do sprawdzania tablicy znaków).

Jeśli przejdę na rozwiązanie zakodowane na stałe za pomocą klauzuli LINQ where, wyniki są następujące:

• Rozwiązanie tablicy Char - 7ms
• Rozwiązanie StringBuilder - 22ms
• LINQ - 60 ms

Być może warto przyjrzeć się LINQ lub zmodyfikowanemu podejściu, jeśli planujesz napisać bardziej ogólne rozwiązanie, niż na sztywno kodować listę znaków. LINQ zdecydowanie zapewnia zwięzły, czytelny kod - nawet bardziej niż Regex.

Nie jestem przekonany, że twój algorytm jest skuteczny. To O (n) i patrzy na każdą postać tylko raz. Nie uzyskasz nic lepszego, chyba że magicznie poznasz wartości przed ich sprawdzeniem.

Zainicjowałbym jednak pojemność twojego StringBuilderrozmiaru początkowego. Zgaduję, że twój postrzegany problem z wydajnością wynika z realokacji pamięci.

Uwaga dodatkowa: Sprawdzanie A- znie jest bezpieczne. W tym[ , \, ], ^, _, i `...

Uwaga dodatkowa 2: Aby uzyskać dodatkową wydajność, należy ustawić porównania w celu zminimalizowania liczby porównań. (W najgorszym przypadku mówimy o 8 porównaniach, więc nie myśl zbyt mocno.) To zmienia się wraz z oczekiwanymi danymi wejściowymi, ale jednym z przykładów może być:

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

Uwaga dodatkowa 3: Jeśli z jakiegokolwiek powodu NAPRAWDĘ potrzebujesz tego, aby był szybki, instrukcja zmiany może być szybsza. Kompilator powinien utworzyć dla ciebie tabelę skoków, co da tylko jedno porównanie:

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]);
    }
}

Możesz użyć zwykłej ekspresji w następujący sposób:

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

Wydaje mi się to dobre. Jedyne ulepszenie, którego dokonałbym, to zainicjowanie StringBuilderdługością łańcucha.

StringBuilder sb = new StringBuilder(str.Length);

Zgadzam się z tym przykładem kodu. Jedyne, co robię, robię to w metodzie rozszerzenia typu ciągu. Abyś mógł używać go w bardzo prostej linii lub kodzie:

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

Dziękuję Guffa za eksperyment.

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();
        }
}

Chciałbym użyć ciągu Zamień na wyrażenie regularne, szukając „znaków specjalnych”, zastępując wszystkie znalezione znaki pustym ciągiem.

Musiałem zrobić coś podobnego do pracy, ale w moim przypadku musiałem odfiltrować wszystko, co nie jest literą, cyfrą lub białą spacją (ale możesz łatwo zmodyfikować to do swoich potrzeb). Filtrowanie odbywa się po stronie klienta w JavaScript, ale ze względów bezpieczeństwa zajmuję się również filtrowaniem po stronie serwera. Ponieważ mogę oczekiwać, że większość ciągów będzie czysta, chciałbym unikać kopiowania ciągów, chyba że naprawdę muszę. To pozwoliło mi na implementację poniżej, która powinna działać lepiej zarówno dla czystych, jak i brudnych łańcuchów.

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();
}

W przypadku S & G, Linq-ified sposób:

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());

Jednak nie sądzę, że będzie to najbardziej efektywny sposób.

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();
}

Posługiwać się:

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
}

I dostaniesz czysty sznurek s.

erase()usunie go ze wszystkich znaków specjalnych i jest wysoce konfigurowalny dzięki tej my_predicate()funkcji.

HashSet to O (1)
Nie jestem pewien, czy jest szybszy niż istniejące porównanie

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();
}

Testowałem i to nie szybciej niż zaakceptowana odpowiedź.
Zostawię to tak, jakbyś potrzebował konfigurowalnego zestawu znaków, byłoby to dobre rozwiązanie.

Zastanawiam się, czy zastąpienie oparte na Regex (być może skompilowane) jest szybsze. Musiałbym sprawdzić, czy ktoś stwierdził, że jest to ~ 5 razy wolniej.

Poza tym należy zainicjować StringBuilder o oczekiwanej długości, aby łańcuch pośredni nie musiał być kopiowany podczas jego wzrostu.

Dobra liczba to długość oryginalnego ciągu lub coś nieco mniejszego (w zależności od charakteru danych wejściowych funkcji).

Na koniec możesz użyć tabeli odnośników (w zakresie 0..127), aby dowiedzieć się, czy znak ma zostać zaakceptowany.

Poniższy kod ma następujące dane wyjściowe (wniosek jest taki, że możemy również zaoszczędzić niektóre zasoby pamięci przydzielając tablicę mniejszą wielkość):

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  

Możesz także dodać następujące wiersze kodu w celu obsługi rosyjskich ustawień regionalnych (rozmiar tablicy to 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);
}

Nie jestem pewien, czy jest to najbardziej efektywny sposób, ale działa dla mnie

 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

Istnieje wiele proponowanych rozwiązań, niektóre bardziej wydajne niż inne, ale być może niezbyt czytelne. Oto jeden, który może nie być najbardziej wydajny, ale z pewnością przydatny w większości sytuacji, i jest dość zwięzły i czytelny, wykorzystując 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;
}

Jeśli martwisz się szybkością, użyj wskaźników, aby edytować istniejący ciąg. Możesz przypiąć ciąg i uzyskać do niego wskaźnik, a następnie uruchomić pętlę for nad każdym znakiem, zastępując każdy nieprawidłowy znak znakiem zastępującym. Byłby niezwykle wydajny i nie wymagałby przydzielania nowej pamięci ciągów. Będziesz także musiał skompilować moduł z opcją niebezpieczną i dodać „niebezpieczny” modyfikator do nagłówka metody, aby użyć wskaźników.

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
}