Самый быстрый способ заменить несколько строк в огромной строке

Ответ 1

Поскольку я был слегка заинтересован в этой проблеме, я разработал несколько решений. С хардкорными оптимизациями он может пойти еще больше.

Чтобы получить последний источник: https://github.com/ChrisEelmaa/StackOverflow/blob/master/FastReplacer.cs

И вывод

-------------------------------------------------------
| Implementation       | Average | Separate runs      |
|----------------------+---------+--------------------|
| Simple               |    3485 | 9002, 4497, 443, 0 |
| SimpleParallel       |    1298 | 3440, 1606, 146, 0 |
| ParallelSubstring    |     470 | 1259, 558, 64, 0   |
| Fredou unsafe        |     356 | 953, 431, 41, 0    |
| Unsafe+unmanaged_mem |      92 | 229, 114, 18, 8    |
-------------------------------------------------------

Вы, вероятно, не будете бить ребята из .NET, создавая свой собственный метод замещения, скорее всего, уже используя небезопасные. Я верю, что вы можете получить его в два раза, если вы полностью напишете его на C.

Мои реализации могут быть ошибочными, но вы можете получить общую идею.

Ответ 2

Используя unsafe и скомпилированный как x64

результат:

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

возьмите код Erti-Chris Eelmaa и замените мой предыдущий.

Я не думаю, что сделаю еще одну итерацию, но я узнал кое-что с небезопасным, что хорошо: -)

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

Ответ 3

Похоже, вы токенизируете строку? Я бы посмотрел на создание буфера и индексацию ваших жетонов. Или используя шаблонный двигатель

В качестве наивного примера вы можете использовать генерацию кода для создания следующего метода

public string Produce(string tokenValue){

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

    return builder.ToString();

}

Если вы выполняете итерации достаточно времени, время для создания шаблона будет самоокупаться. Затем вы можете также вызвать этот метод параллельно без побочных эффектов. Также посмотрите на интернирование строк

Ответ 4

Я сделал вариант кода Fredou, который требует меньше сравнений, поскольку он работает на int* вместо char*. Он по-прежнему требует n итераций для строки длиной n, просто нужно сделать меньше сравнения. Вы могли бы иметь итерации n/2, если строка будет аккуратно выровнена на 2 (поэтому заменяемая строка может появляться только в индексах 0, 2, 4, 6, 8 и т.д.) Или даже n/4, если она выровнена на 4 (вы 'd use long*). Я не очень хорошо разбираюсь в этом, так что кто-то может найти явный недостаток в моем коде, который может быть более эффективным. Я проверил, что результат моего варианта совпадает с результатом простого string.Replace.

Кроме того, я ожидаю, что в 500x string.Copy можно получить некоторые выигрыши, но это еще не изучено.

Мои результаты (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

Итак, примерно 2/3 времени (x86, но x64 примерно одинаков).

Для этого кода:

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

Строка с фиксированным буфером здесь не является строго необходимой и может быть заменена простым полем int, но развернуть char[2] до char[3], и этот код можно заставить работать с тремя буквами, как ну, что было бы невозможно, если бы это было поле int.

Это потребовало внесения некоторых изменений в Program.cs, так что здесь полный текст:

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

EDIT: Я не уверен, почему моя ParallelSubstring настолько медленная. Я запускаю .NET 4 в режиме Release, без отладчика в x86 или x64.

Ответ 5

Поскольку ваша строка ввода может достигать 2 Мб, я не предвижу проблемы с распределением памяти. Вы можете загружать все в память и заменять свои данные.

Если из BC вы ВСЕГДА должны быть заменены на AA, a String.Replace будет в порядке. Но если вам нужно больше контроля, вы можете использовать Regex.Replace:

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

Ответ 6

Вероятно, вы не получите ничего быстрее, чем String.Replace(если вы не нажмете native), потому что iirc String.Replace реализован в самой CLR для максимальной производительности. Если вы хотите 100% -ную производительность, вы можете удобно взаимодействовать с собственным кодом ASM через С++/CLI и идти оттуда.

Ответ 7

Мой подход немного похож на шаблоны - он берет входную строку и вытаскивает (удаляет) подстроки, которые нужно заменить. Затем он берет остальные части строки (шаблон) и объединяет их с новыми заменяющими подстроками. Это выполняется в параллельной операции (шаблон + каждая строка замены), которая строит выходные строки.

Я думаю, что то, что я объясняю выше, может быть более четким с кодом. Это использует ваши входы образца сверху:

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

Вывод:

AAADAAAAAADAAAAAADAAAAAADAAAD
ABBDABBABBDABBABBDABBABBDABBD
ACCDACCACCDACCACCDACCACCDACCD
ADDDADDADDDADDADDDADDADDDADDD
AEEDAEEAEEDAEEAEEDAEEAEEDAEED

Итак, вы можете сделать сравнение, вот полный метод, который можно использовать в тестовом коде Erti-Chris Eelmaa:

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

Ответ 8

У меня была аналогичная проблема с проектом, и я реализовал решение Regex для выполнения нескольких изменений и, нечувствительных к регистру, в файле.

Для целей эффективности я устанавливаю критерии для прохождения исходной строки только один раз.

Я опубликовал простое консольное приложение для тестирования некоторых стратегий на https://github.com/nmcc/Spikes/tree/master/StringMultipleReplacements

Код для решения Regex аналогичен:

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

EDIT: Время выполнения тестового приложения на моем компьютере:

• Циклирование через вызывающую строку replace.Substring() (CASE SENSITIVE): 2ms
• Один проход с использованием регулярного выражения с несколькими заменами сразу (нечувствительный к регистру): 8 мс
• Заполнение с помощью ReplaceIgnoreCase Расширение (нечувствительное к регистру): 55 мс