webentwicklung-frage-antwort-db.com.de

Die schnellste Möglichkeit, mehrere Zeichenfolgen in einer großen Zeichenfolge zu ersetzen

Ich suche den schnellsten Weg, um mehrere (~ 500) Teilzeichenfolgen einer großen (~ 1mb) Zeichenfolge zu ersetzen. Was auch immer ich ausprobiert habe, es scheint, dass String.Replace der schnellste Weg ist, es zu tun.

Ich interessiere mich nur für den schnellsten Weg. Nicht lesbarer Code, Wartbarkeit usw. Es ist mir egal, ob ich unsicheren Code verwenden oder die ursprüngliche Zeichenfolge vorverarbeiten muss.

EDIT: Nach den Kommentaren habe ich noch ein paar Details hinzugefügt:

Jede Ersetzungsiteration ersetzt ABC in der Zeichenfolge durch eine andere Zeichenfolge (je Ersetzungsiteration unterschiedlich). Die zu ersetzende Zeichenfolge ist IMMER gleich - ABC ist immer ABC. Nie ABD. Wenn also 400.000 tausende Iterationen ersetzen. Dieselbe Zeichenfolge - ABC - wird jedes Mal durch eine andere (andere) Zeichenfolge ersetzt. 

Ich kann die Kontrolle darüber haben, was ABC ist. Ich kann es super kurz oder super lang machen, solange es die Ergebnisse nicht beeinflusst. Offensichtlich kann ABC nicht hello sein, da hallo in den meisten Eingangsstrings als Word vorhanden ist.

Beispieleingabe: ABCDABCABCDABCABCDABCABCDABCD

Beispiel Ersetzen von String: BC

Beispiel durch Strings ersetzen: AA, BB, CC, DD, EE (5 iterations)

Beispielausgaben:

AAADAAAAAADAAAAAADAAAAAADAAAD
ABBDABBABBDABBABBDABBABBDABBD
ACCDACCACCDACCACCDACCACCDACCD
ADDDADDADDDADDADDDADDADDDADDD
AEEDAEEAEEDAEEAEEDAEEAEEDAEED

Durchschnittlicher Fall: Die Eingabezeichenfolge beträgt 100-200 kb mit 40.000 Iterationen zum Ersetzen . Schlechtester Fall: Die Eingabezeichenfolge ist 1-2 MB mit 400.000 Ersetzungseiterationen.

Ich kann alles tun. Tun Sie es parallel, machen Sie es unsicher usw. Es ist egal, wie ich es mache. Was zählt ist, dass es so schnell sein muss, wie es nur geht.

Vielen Dank

26
Yannis

Da mich dieses Problem leicht interessierte, habe ich nur wenige Lösungen gefunden. Mit Hardcore-Optimierungen können Sie noch mehr erreichen.

Um die neueste Quelle zu erhalten: https://github.com/ChrisEelmaa/StackOverflow/blob/master/FastReplacer.cs

Und die Ausgabe

------------------------------------------- --------
 | Umsetzung | Durchschnitt | Getrennte Läufe | 
 | ---------------------- + --------- + ---------- ---------- | 
 | Einfach | 3485 | 9002, 4497, 443, 0 | 
 | SimpleParallel | 1298 | 3440, 1606, 146, 0 | 
 | ParallelSubstring | 470 | 1259, 558, 64, 0 | 
 | Fredou unsicher | 356 | 953, 431, 41, 0 | 
 | Unsicher + unmanaged_mem | 92 | 229, 114, 18, 8 | 
------------------------------------- ----------------

Sie werden die .NET-Jungs bei der Erstellung Ihrer eigenen Ersetzungsmethode wahrscheinlich nicht schlagen können, da sie höchstwahrscheinlich bereits unsicher sind. Ich glaube, Sie können es um den Faktor zwei herunterfahren, wenn Sie es vollständig in C schreiben.

Meine Implementierungen sind möglicherweise fehlerhaft, aber Sie können eine allgemeine Vorstellung davon bekommen.

24

Verwendung von unsafe und als x64 kompiliert

ergebnis:

Implementation       | Exec   | GC
#1 Simple            | 4706ms |  0ms
#2 Simple parallel   | 2265ms |  0ms
#3 ParallelSubstring |  800ms | 21ms
#4 Fredou unsafe     |  432ms | 15ms

nimm den Code von Erti-Chris Eelmaa und ersetze meinen vorherigen durch diesen.

Ich glaube nicht, dass ich eine weitere Iteration machen werde, aber ich habe ein paar Dinge mit unsicherem gelernt, was eine gute Sache ist :-)

    private unsafe static void FredouImplementation(string input, int inputLength, string replace, string[] replaceBy)
    {
        var indexes = new List<int>();

        //input = "ABCDABCABCDABCABCDABCABCDABCD";
        //inputLength = input.Length;
        //replaceBy = new string[] { "AA", "BB", "CC", "DD", "EE" };

        //my own string.indexof to save a few ms
        int len = inputLength;

        fixed (char* i = input, r = replace)
        {
            int replaceValAsInt = *((int*)r);

            while (--len > -1)
            {
                if (replaceValAsInt == *((int*)&i[len]))
                {
                    indexes.Add(len--);
                }
            }                
        }

        var idx = indexes.ToArray();
        len = indexes.Count;

        Parallel.For(0, replaceBy.Length, l =>
            Process(input, inputLength, replaceBy[l], idx, len)
        );
    }

    private unsafe static void Process(string input, int len, string replaceBy, int[] idx, int idxLen)
    {
        var output = new char[len];

        fixed (char* o = output, i = input, r = replaceBy)
        {
            int replaceByValAsInt = *((int*)r);

            //direct copy, simulate string.copy
            while (--len > -1)
            {
                o[len] = i[len];
            }

            while (--idxLen > -1)
            {
                ((int*)&o[idx[idxLen]])[0] = replaceByValAsInt;
            }
        }

        //Console.WriteLine(output);
    }
4
Fredou

Es klingt, als würden Sie die Zeichenkette mit einem Token versehen? Ich würde einen Puffer erzeugen und Ihre Token indizieren

Als naives Beispiel können Sie die Codegenerierung verwenden, um die folgende Methode zu erstellen

public string Produce(string tokenValue){

    var builder = new StringBuilder();
    builder.Append("A");
    builder.Append(tokenValue);
    builder.Append("D");

    return builder.ToString();

}

Wenn Sie die Iterationen ausreichend oft ausführen, wird sich die Zeit zum Erstellen der Vorlage für Sie bezahlt machen. Sie können diese Methode dann auch parallel ohne Nebeneffekte aufrufen. Sehen Sie sich auch die Internierung Ihrer Strings an

1
Adam Mills

Ich habe eine Variation von Fredous Code vorgenommen, der weniger Vergleiche erfordert, da er auf int* statt auf char* funktioniert. Es erfordert immer noch n-Iterationen für einen String mit n-Länge, es muss nur weniger Vergleiche anstellen. Sie könnten n/2-Iterationen haben, wenn die Zeichenfolge sauber nach 2 ausgerichtet ist (die zu ersetzende Zeichenfolge kann nur bei den Indizes 0, 2, 4, 6, 8 usw. vorkommen) oder sogar n/4, wenn die Zeichenfolge durch 4 (Sie würden long* ). Ich kann nicht so gut fummeln, so dass jemand in der Lage ist, einen offensichtlichen Fehler in meinem Code zu finden, der effizienter sein könnte. Ich habe bestätigt, dass das Ergebnis meiner Variation dasselbe ist wie das des einfachen string.Replace.

Darüber hinaus erwarte ich, dass beim 500x string.Copy einige Gewinne erzielt werden können, was aber noch nicht untersucht wurde.

Meine Ergebnisse (Fredou II):

IMPLEMENTATION       |  EXEC MS | GC MS
#1 Simple            |     6816 |     0
#2 Simple parallel   |     4202 |     0
#3 ParallelSubstring |    27839 |     4
#4 Fredou I          |     2103 |   106
#5 Fredou II         |     1334 |    91

Also ungefähr 2/3 der Zeit (x86, aber x64 war ungefähr gleich).

Für diesen Code:

private unsafe struct TwoCharStringChunk
{
  public fixed char chars[2];
}

private unsafe static void FredouImplementation_Variation1(string input, int inputLength, string replace, TwoCharStringChunk[] replaceBy)
{
  var output = new string[replaceBy.Length];

  for (var i = 0; i < replaceBy.Length; ++i)
    output[i] = string.Copy(input);

  var r = new TwoCharStringChunk();
  r.chars[0] = replace[0];
  r.chars[1] = replace[1];

  _staticToReplace = r;

  Parallel.For(0, replaceBy.Length, l => Process_Variation1(output[l], input, inputLength, replaceBy[l]));
}

private static TwoCharStringChunk _staticToReplace ;

private static unsafe void Process_Variation1(string output, string input, int len, TwoCharStringChunk replaceBy)
{
  int n = 0;
  int m = len - 1;

  fixed (char* i = input, o = output, chars = _staticToReplace .chars)
  {
    var replaceValAsInt = *((int*)chars);
    var replaceByValAsInt = *((int*)replaceBy.chars);

    while (n < m)
    {
      var compareInput = *((int*)&i[n]);

      if (compareInput == replaceValAsInt)
      {
        ((int*)&o[n])[0] = replaceByValAsInt;
        n += 2;
      }
      else
      {
        ++n;
      }
    }
  }
}

Die struct mit dem festen Puffer ist hier nicht unbedingt erforderlich und könnte durch ein einfaches int-Feld ersetzt werden. Erweitern Sie jedoch char[2] zu char[3]. Dieser Code kann auch mit drei Buchstabenzeichenfolgen verwendet werden, was jedoch nicht möglich wäre es war ein int Feld.

Es gab auch einige Änderungen an den Program.cs, also hier der vollständige Gist:

https://Gist.github.com/JulianR/7763857

EDIT: Ich bin nicht sicher, warum mein ParallelSubstring so langsam ist. Ich verwende .NET 4 im Release-Modus, keinen Debugger, entweder in x86 oder in x64.

1
JulianR

Ich hatte ein ähnliches Problem in einem Projekt und habe eine Regex-Lösung implementiert, um mehrere Fälle mit und für eine Datei zu ersetzen.

Aus Gründen der Effizienz setze ich Kriterien, um die ursprüngliche Zeichenfolge nur einmal zu durchlaufen.

Ich habe eine einfache Konsolen-App veröffentlicht, um einige Strategien auf https://github.com/nmcc/Spikes/tree/master/StringMultipleReplacements zu testen. _

Der Code für die Regex-Lösung sieht folgendermaßen aus:

Dictionary<string, string> replacements = new Dictionary<string, string>(StringComparer.OrdinalIgnoreCase);
    // Fill the dictionary with the proper replacements:

        StringBuilder patternBuilder = new StringBuilder();
                patternBuilder.Append('(');

                bool firstReplacement = true;

                foreach (var replacement in replacements.Keys)
                {
                    if (!firstReplacement)
                        patternBuilder.Append('|');
                    else
                        firstReplacement = false;

                    patternBuilder.Append('(');
                    patternBuilder.Append(Regex.Escape(replacement));
                    patternBuilder.Append(')');
                }
                patternBuilder.Append(')');

                var regex = new Regex(patternBuilder.ToString(), RegexOptions.IgnoreCase);

                return regex.Replace(sourceContent, new MatchEvaluator(match => replacements[match.Groups[1].Value]));

BEARBEITEN: Die Ausführungszeiten der Testanwendung auf meinem Computer lauten wie folgt:

  • Durchlaufen der Ersetzungen, die string aufrufen.Substring () (CASE SENSITIVE): 2ms
  • Einfacher Durchgang mit Regex mit mehreren Ersetzungen auf einmal (Groß- und Kleinschreibung wird nicht berücksichtigt): 8 ms
  • Durchlaufen von Ersetzungen mithilfe einer Erweiterung von ReplaceIgnoreCase (Groß-/Kleinschreibung wird nicht berücksichtigt): 55 ms
0
nunoc

Da Ihre Eingabezeichenfolge so lang wie 2 MB sein kann, sehe ich kein Speicherzuordnungsproblem vor. Sie können alles in den Speicher laden und Ihre Daten ersetzen.

Wenn Sie BC IMMER für AA ersetzen müssen, ist ein String.Replace in Ordnung. Wenn Sie jedoch mehr Kontrolle benötigen, können Sie einen Regex.Replace verwenden:

var input  = "ABCDABCABCDABCABCDABCABCDABCD";
var output = Regex.Replace(input, "BC", (match) =>
{
    // here you can add some juice, like counters, etc
    return "AA";
});
0
Rubens Farias

Mein Ansatz ist ein bisschen wie das Schablonieren - er nimmt die Eingabezeichenfolge und zieht (entfernt) die zu ersetzenden Teilzeichenfolgen. Dann nimmt es die restlichen Teile des Strings (die Vorlage) und kombiniert sie mit den neuen Ersetzungs-Teilstrings. Dies geschieht in einem parallelen Vorgang (Vorlage + jeder Ersetzungsstring), der die Ausgabestrings erstellt.

Ich denke, was ich oben erkläre, könnte mit Code klarer sein. Dies verwendet Ihre Beispieleingaben von oben:

const char splitter = '\t';   // use a char that will not appear in your string

string input = "ABCDABCABCDABCABCDABCABCDABCD";
string oldString = "BC";
string[] newStrings = { "AA", "BB", "CC", "DD", "EE" };

// In input, replace oldString with tabs, so that we can do String.Split later
var inputTabbed = input.Replace(oldString, splitter.ToString());
// ABCDABCABCDABCABCDABCABCDABCD --> A\tDA\tA\tDA\tA\tDA\tA\tDA\tD

var inputs = inputTabbed.Split(splitter);
/* inputs (the template) now contains:
[0] "A" 
[1] "DA"
[2] "A" 
[3] "DA"
[4] "A" 
[5] "DA"
[6] "A" 
[7] "DA"
[8] "D" 
*/

// In parallel, build the output using the template (inputs)
// and the replacement strings (newStrings)
var outputs = new List<string>();
Parallel.ForEach(newStrings, iteration =>
    {
        var output = string.Join(iteration, inputs);
        // only lock the list operation
        lock (outputs) { outputs.Add(output); }
    });

foreach (var output in outputs)
    Console.WriteLine(output);

Ausgabe:

AAADAAAAAADAAAAAADAAAAAADAAAD
ABBDABBABBDABBABBDABBABBDABBD
ACCDACCACCDACCACCDACCACCDACCD
ADDDADDADDDADDADDDADDADDDADDD
AEEDAEEAEEDAEEAEEDAEEAEEDAEED

So können Sie einen Vergleich durchführen, hier ist eine vollständige Methode, die im Testcode von Erti-Chris Eelmaa verwendet werden kann:

private static void TemplatingImp(string input, string replaceWhat, IEnumerable<string> replaceIterations)
{
    const char splitter = '\t';   // use a char that will not appear in your string

    var inputTabbed = input.Replace(replaceWhat, splitter.ToString());
    var inputs = inputTabbed.Split(splitter);

    // In parallel, build the output using the split parts (inputs)
    // and the replacement strings (newStrings)
    //var outputs = new List<string>();
    Parallel.ForEach(replaceIterations, iteration =>
    {
        var output = string.Join(iteration, inputs);
    });
}
0
chue x

Sie werden wahrscheinlich nichts schneller als String.Replace erhalten (es sei denn, Sie werden nativ), da iirc String.Replace in CLR für maximale Leistung implementiert ist. Wenn Sie 100% Leistung wünschen, können Sie bequem über C++/CLI mit dem nativen ASM-Code kommunizieren und von dort aus fortfahren.

0
Nemo