C #: вставка строк в другую строку - проблема производительности - PullRequest
Новая
       4

C #: вставка строк в другую строку - проблема производительности

3 голосов
/ 28 августа 2011

У меня есть длинная строка и отсортированный словарь индексов и значений. Я должен перейти по элементам в словаре и вставить значение в указанный индекс в строке. Я написал следующий код, который работает нормально, но очень медленно: 

private string restoreText(string text){
  StringBuilder sb = new StringBuilder(text);
  foreach(KeyValuePair<int, string> pair in _tags){
    sb.Insert(pair.Key, pair.Value);
  }
  return sb.ToString();
}

Словарь может быть очень большим и содержать 500 000 элементов. Я думаю, что то, что делает эту функцию медленной, это метод Insert (). Для словаря из 100 000 элементов это заняло почти 5 секунд.

Есть ли более эффективный способ написания этого метода?

Спасибо

Maya

Ответы [ 4 ]

2 голосов
/ 28 августа 2011

Ваш исходный код даст разные результаты в зависимости от порядка, в котором элементы возвращаются из _tags;Я очень подозреваю, что это не ваше намерение.

Вместо этого сортируйте теги по порядку, а затем добавляйте их в построитель строк в правильной последовательности: 

private string restoreText(string text)
{
    StringBuilder sb = new StringBuilder();
    foreach( KeyValuePair<int, string> pair in _tags.OrderBy(t => t.Key))
    {
        sb.Append(pair.Value);
    }

    return sb.ToString();
}

Если вы действительно хотитесделайте это как можно быстрее, инициализируйте емкость StringBuilder впереди: 

    StringBuilder sb = new StringBuilder(_tags.Sum(k => k.Value.Length));

Обновление

Я пропустил первоначально использованный параметр textинициализировать StringBuilder.

Чтобы избежать перемешивания текста в памяти (как это вызвано StringBuilder.Insert()), мы хотим придерживаться использования StringBuilder.Append().

Мы можем сделать это путем преобразования исходного текста в другую последовательность KeyValuePair экземпляров, объединения их с исходным списком и обработки по порядку.

Это будет выглядеть примерно так ( note : adhoc code): 

private string restoreText(string text)
{
    var textPairs 
        = text.Select( (c,i) => new KeyValuePair<int,string>(i, (string)c));
    var fullSequence
        = textPairs.Union(_tags).OrderBy(t => t.Key);
    StringBuilder sb = new StringBuilder();
    foreach( KeyValuePair<int, string> pair in fullSequence)
    {
        sb.Append(pair.Value);
    }

    return sb.ToString();
}

Примечание. Я сделал целую кучу предположений относительно вашего контекста, поэтому это может не сработать для вас.Особенно следует помнить, что .Union() удалит дубликаты, хотя для этого есть простые обходные пути.

2 голосов
/ 28 августа 2011

Лучше было бы отсортировать элементы для вставки, а затем добавлять их один за другим.

Поскольку вы не прокомментировали перекрытие, может быть, у вас есть элементы, отсортированные в первую очередь?

1 голос
/ 28 августа 2011

что я не получу, если вы настроили свои индексы так, чтобы вставка не изменила другие, но, как ваш код говорит "да", я тоже приму это.

Можете ли вы проверить этоодин: 

private string RestoreText(string text)
{
    var sb = new StringBuilder();
    var totalLen = 0;
    var orgIndex = 0;
    foreach (var pair in _tags.OrderBy(t => t.Key))
    {
        var toAdd = text.Substring(orgIndex, pair.Key - totalLen);
        sb.Append(toAdd);
        orgIndex += toAdd.Length;
        totalLen += toAdd.Length;

        sb.Append(pair.Value);
        totalLen += pair.Value.Length;
    }
    if (orgIndex < text.Length) sb.Append(text.Substring(orgIndex));
    return sb.ToString();
}

он использует только append, будучи таким же, как ваш исходный код

1 голос
/ 28 августа 2011

Я не знаю, как насчет ваших данных.

но в моем тесте он работает быстро (564мс). 

        Dictionary<int, string> _tags = new Dictionary<int, string>();
        for (int i = 0; i < 1000000; i++)
        {
            _tags.Add(i, i.ToString().Length + "");
        }

        string text = new String('a' , 50000000);
        Console.WriteLine("****************************************");

        System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();

        StringBuilder sb = new StringBuilder(text);
        foreach (KeyValuePair<int, string> pair in _tags)
        {
            sb.Insert(pair.Key, pair.Value);
        }

        sw.Stop();

        Console.WriteLine("sw:" + sw.ElapsedMilliseconds);
        Console.ReadKey();

если вы можете использовать append () вместо insert (), это займет всего 35 мс ...

...