Wie man viele kleine Änderungen in großen Saiten am schnellsten macht. Visual C++

Question

Ich habe versucht, dieses Problem im Laufe des Monats zu behandeln. Ich muss viele Ersetzungen (über 10 Millionen) in einer großen Zeichenfolge (String ^) durchführen. Auch ich muss es schnell machen. Mein Weg war richtig, aber das Programm lief über 30 Minuten.

Problem: Ich habe eine Tabelle mit Änderungen zu tun: [strWas1, strWillBe1, strWas2, strWillBe2, ..., strWas10^7, strWillBe10^7]. Auch ich habe eine große Schnur, die einige von strWasN enthalten kann, aber es kann auch something-elsestrWas1 enthalten und ich will es nicht ändern, weil "something-elsestrWas1" nicht "strWas1" ist.

Zum Beispiel String ist:

"ich zwei Hunde, drei notdogs, auch dogsikong, 5dogs, -Dogs DOGS, Hunde, Hunde, 33DoGs00."

Jetzt brauche ich alle isolierten "Hunde" von Buchstaben ("Hunde" ist strWas1) zu "Katzen" ("Katzen" ist strWillBe1) zu ändern. Ergebnis sein sollte:

"Ich habe zwei Katzen, drei notdogs, auch dogsikong, 5cats, -cats Katzen, Katzen, Katzen, 33cats00."

Mein letzter Versuch war:

array<String^>^ strArray = gcnew array<String^>(9999999); 
strArray[0] = gcnew String("dogs"); 
strArray[1] = gcnew String("cats"); 
//... 
strArray[9999998] = gcnew String("whatReplace"); 
strArray[9999999] = gcnew String("newText"); 
bool found = false; 
int index; 
bool doThis = true; 
String^notAllowed = u8"aąbcćdeęfghijklłmnńoópqrsśtuvwxyzźżAĄBCĆDEĘFGHIJKLŁMNŃOÓPQRSŚTUVWXYZŹŻёйцукенгшщзхъфывапролджэячсмитьбюЁЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ"; 
String^text = u8"I have two dogs, three notdogs, also dogsikong, 5dogs, -dogs. DOGS, Dogs, DoGs, 33DoGs00"; 
for (int i = 0; i < 9999999; i+=2) { 
    while (found = text->Contains(strArray[i])) { 
     index = text->IndexOf(strArray[i]); 
     MessageBox::Show(index.ToString()); 
     doThis = true; 
     if (index == 0) { 
      for (int j = 0; j < notAllowed->Length; j++) { 
       if (text->Substring(strArray[i]->Length, 1) == notAllowed->Substring(j, 1)) doThis = false; 
      } 
     } 
     else if (text->Length - index - strArray[i]->Length) { 
      for (int j = 0; j < notAllowed->Length; j++) { 
       if (text->Substring(index-1, 1) == notAllowed->Substring(j, 1)) doThis = false; 
      } 
     } 
     else { 
      for (int j = 0; j < notAllowed->Length; j++) { 
       if ((text->Substring(index - 1, 1) == notAllowed->Substring(j, 1)) || (text->Substring(index+strArray[i]->Length,1)== notAllowed->Substring(j, 1))) doThis = false; 
      } 
     } 
     if (doThis) { 
     text = text->Substring(0, index) + strArray[i + 1] + text->Substring(index + strArray[i]->Length, text->Length - index - strArray[i]->Length); 
    } 
    } 
} 

Aber das funktioniert für endlos

Neue Version (dank Vlad Feinstein):

array<String^>^ strArray = gcnew array<String^>(10); 
strArray[0] = gcnew String("dogs"); 
strArray[1] = gcnew String("cats"); 
strArray[2] = gcnew String("dogs"); 
strArray[3] = gcnew String("cats"); 
strArray[4] = gcnew String("dogs"); 
strArray[5] = gcnew String("cats"); 
strArray[6] = gcnew String("dogs"); 
strArray[7] = gcnew String("cats"); 
strArray[8] = gcnew String("dogs"); 
strArray[9] = gcnew String("cats"); 
bool found = false; 
int index; 
bool doThis = true; 
String^text = u8"I have two dogs, three notdogs, also dogsikong, 5dogs, -dogs. DOGS, Dogs, DoGs, 33DoGs00"; 
for (int i = 0; i < 10; i += 2) 
{ 
    int index = 0; 
    while ((index = text->ToLower()->IndexOf(strArray[i]->ToLower(), index)) != -1) 
    { 
     doThis = true; 
     // is there one more char? 
     if (index + strArray[i]->Length < text->Length) 
     { 
      if (Char::IsLetter(text[index+strArray[i]->Length])) 
       doThis = false; 
     } 
     // is there previous char? 
     if (index > 0) 
     { 
      if (Char::IsLetter(text[index - 1])) 
       doThis = false; 
     } 
     if (doThis) 
      text = text->Substring(0, index) + strArray[i + 1] + 
      text->Substring(index + strArray[i]->Length); 
     Debug::WriteLine(text); 
     index++; 
    } 
} 

Natürlich ist es immer noch nicht so schnelle Version. Schnelle Version schrieb David Yaw.

Answer 1

Es gibt einen viel besseren Weg, dies zu tun, als blind jede einzelne von einer Million Ersatzzeichenfolgen zu überprüfen. Lassen Sie .Net die Zeichenfolgen hashen, und lassen Sie es so überprüfen.

Wenn wir die Suche & Zeichenfolgen als ein Dictionary ersetzen, können wir die Hash-Lookups von .Net verwenden, um die Zeichenfolgen zu finden, die wir ersetzen müssen.

Wenn wir durch jedes Zeichen in der Zeichenfolge gehen, könnte es der Beginn einer 5-Zeichen 'Suche nach' Zeichenfolge, oder der Beginn einer 4-Zeichen 'Suche nach' Zeichenfolge, etc, oder es könnte nicht sein Sei überhaupt Teil eines "Suche nach" Zeichens, in diesem Fall wird es direkt in die Ausgabe kopiert. Wenn wir eine 'Suche nach' Zeichenfolge finden, schreiben wir die Ersetzung in die Ausgabe und markieren die entsprechende Anzahl der eingegebenen Zeichen als verbraucht.

Basierend auf Ihrer Beschreibung scheint es, dass Sie bei der Suche nach Zeichenfolgen einen Vergleich ohne Berücksichtigung der Groß- und Kleinschreibung vornehmen möchten. Sie können Groß-/Kleinschreibung oder -unempfindlich verwenden, geben Sie einfach an, was Sie möchten, wenn Sie die Dictionary konstruieren.

String^ BigFindReplace(
    String^ originalString, 
    Dictionary<String^, String^>^ replacementPairs) 
{ 
    // First, get the lengths of all the 'search for' strings in the replacement pairs. 
    SortedSet<int> searchForLengths; 
    for each (String^ searchFor in replacementPairs->Keys) 
    { 
     searchForLengths.Add(searchFor->Length); 
    } 

    // Searching for an empty string isn't valid: remove length zero, if it's there. 
    searchForLengths.Remove(0); 

    StringBuilder result; 

    // Step through the input string. For each character: 
    // A) See if the character is the beginning of one of the 'search for' strings. 
    // If so, then insert the 'replace with' string into the output buffer. 
    // Skip over this character and the rest of the 'search for' string that we found. 
    // B) If it's not the beginning of a 'search for' string, copy it to the output buffer. 

    for(int i = 0; i < originalString->Length; i++) 
    { 
     bool foundSomething = false; 
     int foundSomethingLength = 0; 
     for each (int len in searchForLengths.Reverse()) 
     { 
      if (i > (originalString->Length - len)) 
      { 
       // If we're on the last 4 characters of the string, we can ignore 
       // all the 'search for' strings that are 5 characters or longer. 
       continue; 
      } 

      String^ substr = originalString->Substring(i, len); 

      String^ replaceWith; 
      if (replacementPairs->TryGetValue(substr, replaceWith)) 
      { 
       // We found the section of the input string that we're looking at in our 
       // 'search for' list! Inser the 'replace with' into the output buffer. 
       result.Append(replaceWith); 
       foundSomething = true; 
       foundSomethingLength = len; 
       break; // don't try to find more 'search for' strings. 
      } 
     } 

     if(foundSomething) 
     { 
      // We found & already inserted the replacement text. Just increment 
      // the loop counter to skip over the rest of the characters of the 
      // found 'search for' text. 

      i += (foundSomethingLength - 1); // "-1" because the for loop has its own "+1". 
     } 
     else 
     { 
      // We didn't find any of the 'search for' strings, 
      // so this is a character that just gets copied. 
      result.Append(originalString[i]); 
     } 
    } 

    return result.ToString(); 
} 

Mein Test-App:

int main(array<System::String ^> ^args) 
{ 
    String^ text = "I have two dogs, three notdogs, also dogsikong, 5dogs, -dogs. DOGS, Dogs, DoGs, 33DoGs00"; 

    Dictionary<String^, String^>^ replacementPairs = 
     gcnew Dictionary<String^, String^>(StringComparer::CurrentCultureIgnoreCase); 

    replacementPairs->Add("dogs", "cats"); 
    replacementPairs->Add("pigs", "cats"); 
    replacementPairs->Add("mice", "cats"); 
    replacementPairs->Add("rats", "cats"); 
    replacementPairs->Add("horses", "cats"); 

    String^ outText = BigFindReplace(text, replacementPairs); 

    Debug::WriteLine(outText); 

    String^ text2 = "I have two dogs, three notpigs, also miceikong, 5rats, -dogs. RATS, Horses, DoGs, 33DoGs00"; 
    String^ outText2 = BigFindReplace(text, replacementPairs); 

    Debug::WriteLine(outText2); 

    return 0; 
} 

Ausgang:

 
I have two cats, three notcats, also catsikong, 5cats, -cats. cats, cats, cats, 33cats00 
I have two cats, three notcats, also catsikong, 5cats, -cats. cats, cats, cats, 33cats00 

Edit: Nur ganze Wörter

OK, so brauchen wir nur ganze Wörter zu ersetzen. Um dies zu tun, schrieb ich eine Hilfsmethode, um eine Zeichenfolge in Wörter & Nonwords aufzuteilen. (Dies unterscheidet sich von der integrierten String :: Split-Methode: String :: Split gibt die Begrenzer nicht zurück, und wir brauchen sie hier.)

Sobald wir ein Array von Strings haben, wo jeder String ist ein Wort oder ein Bündel von Nicht-Wort-Zeichen (z. B. Trennzeichen, Leerzeichen usw.), dann können wir jedes davon über das Wörterbuch ausführen. Weil wir ein ganzes Wort nach dem anderen machen, nicht nur einen Buchstaben nach dem anderen, ist dies effizienter.

array<String^>^ SplitIntoWords(String^ input) 
{ 
    List<String^> result; 
    StringBuilder currentWord; 
    bool currentIsWord = false; 

    for each (System::Char c in input) 
    { 
     // Words are made up of letters. Word separators are made up of 
     // everything else (numbers, whitespace, punctuation, etc.) 
     bool nextCharIsWord = Char::IsLetter(c); 

     if(nextCharIsWord != currentIsWord) 
     { 
      if(currentWord.Length > 0) 
      { 
       result.Add(currentWord.ToString()); 
       currentWord.Clear(); 
      } 
      currentIsWord = nextCharIsWord; 
     } 

     currentWord.Append(c); 
    } 

    if(currentWord.Length > 0) 
    { 
     result.Add(currentWord.ToString()); 
     currentWord.Clear(); 
    } 

    return result.ToArray(); 
} 

String^ BigFindReplaceWords(
    String^ originalString, 
    Dictionary<String^, String^>^ replacementPairs) 
{ 
    StringBuilder result; 

    // First, separate the input string into an array of words & non-words. 
    array<String^>^ asWords = SplitIntoWords(originalString); 

    // Go through each word & non-word that came out of the split. If a word or 
    // non-word is in the replacement list, add the replacement to the output. 
    // Otherwise, add the word/nonword to the output. 

    for each (String^ word in asWords) 
    { 
     String^ replaceWith; 
     if (replacementPairs->TryGetValue(word, replaceWith)) 
     { 
      result.Append(replaceWith); 
     } 
     else 
     { 
      result.Append(word); 
     } 
    } 

    return result.ToString(); 
} 

Mein Test-App:

int main(array<System::String ^> ^args) 
{ 
    String^ text = "I have two dogs, three notdogs, also dogsikong, 5dogs, -dogs. DOGS, Dogs, DoGs, 33DoGs00"; 

    array<String^>^ words = SplitIntoWords(text); 
    for (int i = 0; i < words->Length; i++) 
    { 
     Debug::WriteLine("words[{0}] = '{1}'", i, words[i]); 
    } 

    Dictionary<String^, String^>^ replacementPairs = 
     gcnew Dictionary<String^, String^>(StringComparer::CurrentCultureIgnoreCase); 

    replacementPairs->Add("dogs", "cats"); 
    replacementPairs->Add("pigs", "cats"); 
    replacementPairs->Add("mice", "cats"); 
    replacementPairs->Add("rats", "cats"); 
    replacementPairs->Add("horses", "cats"); 

    String^ outText = BigFindReplaceWords(text, replacementPairs); 

    Debug::WriteLine(outText); 

    String^ text2 = "I have two dogs, three notpigs, also miceikong, 5rats, -dogs. RATS, Horses, DoGs, 33DoGs00"; 
    String^ outText2 = BigFindReplaceWords(text2, replacementPairs); 

    Debug::WriteLine(outText2); 

    return 0; 
} 

Ergebnisse:

 
words[0] = 'I' 
words[1] = ' ' 
words[2] = 'have' 
words[3] = ' ' 
words[4] = 'two' 
words[5] = ' ' 
words[6] = 'dogs' 
words[7] = ', ' 
words[8] = 'three' 
words[9] = ' ' 
words[10] = 'notdogs' 
words[11] = ', ' 
words[12] = 'also' 
words[13] = ' ' 
words[14] = 'dogsikong' 
words[15] = ', 5' 
words[16] = 'dogs' 
words[17] = ', -' 
words[18] = 'dogs' 
words[19] = '. ' 
words[20] = 'DOGS' 
words[21] = ', ' 
words[22] = 'Dogs' 
words[23] = ', ' 
words[24] = 'DoGs' 
words[25] = ', 33' 
words[26] = 'DoGs' 
words[27] = '00' 
I have two cats, three notdogs, also dogsikong, 5cats, -cats. cats, cats, cats, 33cats00 
I have two cats, three notpigs, also miceikong, 5cats, -cats. cats, cats, cats, 33cats00 

Answer 2

Es gibt viele Probleme in Ihrem Code der Probleme verursachen kann, aber Haupt logischen Fehler:

while (found = text->Contains(strArray[i]))

while (found == text->Contains(strArray[i]))

Da == der Vergleichsoperator, während sie sein soll = ist ein Zuweisungsoperator. Sie ordnen also immer Ihre While-Schleife in einer Endlosschleife zu.

Answer 3

Hm ... Nein?

while (found == text->Contains(strArray[i])) 

ist zum Vergleich. Aber ich habe vorher nicht berechnet. Also berechne ich in while und prüfe, ob es wahr ist. Es ist erlaubt.

while (found = text->Contains(strArray[i])) 

ist genau das, was:

found = text->Contains(strArray[i]) 
while (found==true) 

zumindest in normaler C++ es funktioniert. Hier habe ich auch kein Problem damit.

Answer 4

Пётр Васильевич, ein paar Vorschläge:

1. ersetzen Substring (x, 1) mit Char [ x].
2. Werfen Sie Ihr notAllowed String weg und verwendet .NET Char.IsLetter Method oder zumindest bricht aus Ihrem for() Schleifen, wenn Sie doThis = false;
3. gesetzt Wenn Sie einen Teil von index bis zum Ende der Zeichenfolge benötigen, brauchen Sie nicht zu berechnen die Länge; Verwenden Sie einfach ein Formular mit einem Parameter: public string Substring(int startIndex)
4. Verwenden Sie nicht text->Contains(); Sie müssen text->IndexOf() trotzdem anrufen, vergleichen Sie einfach diesen Index mit -1.
5. 10 Millionen Wörter ??? Es gibt nicht viele auf Englisch und Russisch kombiniert!

6. Verwenden Sie die Zweiparameterform von String.IndexOf Method (Char, Int32), um anzugeben, wo die Suche beginnen soll (ausgehend von der Position des zuvor gefundenen Wortes), um zu vermeiden, den Anfang der Zeichenfolge immer wieder zu suchen. So etwas Ähnliches:

   for (int i = 0; i < 9999999; i += 2) 
   { 
       int index = 0; 
       while ((index = text->IndexOf(strArray[i], index)) != -1) 
       { 
        doThis = true; 
        // is there one more char? 
        if (index + strArray[i]->Length < text->Length) 
        { 
         if(Char.IsLetter(text->Char[strArray[i]->Length])) 
          doThis = false; 
        } 
        // is there previous char? 
        if (index > 0) 
        { 
         if (Char.IsLetter(text->Char[index - 1])) 
          doThis = false; 
        } 
        if (doThis) 
         text = text->Substring(0, index) + strArray[i + 1] + 
           text->Substring(index + strArray[i]->Length); 
       } 
   } 
   

7. In Ihrer while() Schleife, sammeln die Indizes der gefundenen Strings in ein Array, dann tut alle Ersatz des gleichen Wortes in einem Durchgang. Dies ist besonders nützlich, wenn das gleiche Wort mehrere Male in text auftritt.