Лучший способ заменить много строк - запутывание в C # - PullRequest
Новая
       11

Лучший способ заменить много строк - запутывание в C #

8 голосов
/ 03 апреля 2009

Я пытаюсь запутать большое количество данных. Я создал список слов (токенов), которые я хочу заменить, и я заменяю слова одно за другим, используя класс StringBuilder, например: 

 var sb = new StringBuilder(one_MB_string);
 foreach(var token in tokens)
 {
   sb.Replace(token, "new string");
 }

Это довольно медленно! Есть ли какие-то простые вещи, которые я могу сделать, чтобы ускорить это?

токены - это список из примерно одной тысячи строк длиной от 5 до 15 символов.

Ответы [ 4 ]

13 голосов
/ 03 апреля 2009

Вместо выполнения замены в огромной строке (что означает, что вы перемещаетесь по большому количеству данных), работайте через строку и заменяйте токен за раз.

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

Я сделал простой тест, и этот метод сделал 125000 замен для строки 1000000 символов за 208 миллисекунд.

Классы Token и TokenList: 

public class Token {

    public string Text { get; private set; }
    public string Replacement { get; private set; }
    public int Index { get; set; }

    public Token(string text, string replacement) {
        Text = text;
        Replacement = replacement;
    }

}

public class TokenList : List<Token>{

    public void Add(string text, string replacement) {
        Add(new Token(text, replacement));
    }

    private Token GetFirstToken() {
        Token result = null;
        int index = int.MaxValue;
        foreach (Token token in this) {
            if (token.Index != -1 && token.Index < index) {
                index = token.Index;
                result = token;
            }
        }
        return result;
    }

    public string Replace(string text) {
        StringBuilder result = new StringBuilder();
        foreach (Token token in this) {
            token.Index = text.IndexOf(token.Text);
        }
        int index = 0;
        Token next;
        while ((next = GetFirstToken()) != null) {
            if (index < next.Index) {
                result.Append(text, index, next.Index - index);
                index = next.Index;
            }
            result.Append(next.Replacement);
            index += next.Text.Length;
            next.Index = text.IndexOf(next.Text, index);
        }
        if (index < text.Length) {
            result.Append(text, index, text.Length - index);
        }
        return result.ToString();
    }

}

Пример использования: 

string text =
    "This is a text with some words that will be replaced by tokens.";

var tokens = new TokenList();
tokens.Add("text", "TXT");
tokens.Add("words", "WRD");
tokens.Add("replaced", "RPL");

string result = tokens.Replace(text);
Console.WriteLine(result);

Выход: 

This is a TXT with some WRD that will be RPL by tokens.

Примечание: Этот код не обрабатывает перекрывающиеся токены. Например, если у вас есть токены «Ананас» и «Яблоко», код не работает должным образом.

Edit:
Чтобы код работал с перекрывающимися токенами, замените эту строку: 

next.Index = text.IndexOf(next.Text, index);

с этим кодом: 

foreach (Token token in this) {
    if (token.Index != -1 && token.Index < index) {
        token.Index = text.IndexOf(token.Text, index);
    }
}
5 голосов
/ 03 апреля 2009

Хорошо, вы понимаете, почему это занимает много времени, верно?

У вас есть строки размером 1 МБ, и для каждого токена замена выполняет итерацию по 1 МБ и создание новой копии объемом 1 МБ. Ну, не точная копия, поскольку любой найденный токен заменяется новым значением токена. Но для каждого токена вы читаете 1 МБ, обновляете 1 МБ памяти и пишете 1 МБ.

Теперь, мы можем придумать лучший способ сделать это? Как насчет того, чтобы вместо итерации 1 МБ строки для каждого токена, мы вместо этого пройдемся по ней один раз.

Прежде чем идти по нему, мы создадим пустую строку вывода.

Когда мы проходим по исходной строке, если мы найдем токен, мы прыгнем вперед token.length() символов и выпишем запутанный токен. В противном случае мы перейдем к следующему символу.

По сути, мы выворачиваем процесс наизнанку, делаем цикл for для длинной строки и в каждой точке ищем токен. Чтобы сделать это быстрым, нам понадобится быстрая петля для токенов, поэтому мы помещаем их в некий ассоциативный массив (набор).

Я понимаю, почему так долго, но не уверен в исправлении. За каждый 1 МБ Строка, на которой я исполняю замены у меня от 1 до 2 тысяч токаны я хочу заменить. Так гуляет персонаж за персонажем ищет любой тысячи токенов не кажется быстрее

В общем, что занимает больше всего времени в программировании? Новая память.

Теперь, когда мы создаем StringBuffer, вероятно, что происходит выделение некоторого объема пространства (скажем, 64 байта), и что всякий раз, когда мы добавляем больше его текущей емкости, он, вероятно, удваивает его пространство. И затем копирует старый символьный буфер к новому. (Возможно, мы можем перераспределить С, и не нужно копировать.)

Итак, если мы начнем с 64 байтов, чтобы получить до 1 МБ, мы выделяем и копируем: 64, затем 128, затем 256, затем 512, затем 1024, затем 2048 ... мы делаем это двадцать раз, чтобы получить до 1 МБ. И чтобы попасть сюда, мы выделили 1 МБ только для того, чтобы выбросить его.

Предварительное выделение с использованием функции, аналогичной функции reserve() в C ++, по крайней мере, позволит нам сделать это сразу. Но это все равно для каждого токена. Вы, по крайней мере, создаете временную строку размером 1 МБ для каждого токена. Если у вас есть 2000 токенов, вы выделяете около 2 миллиардов байтов памяти, и все это в итоге составляет 1 МБ. Каждый 1 Мбайт выброс содержит преобразование предыдущей результирующей строки с применением текущего токена.

И вот почему это так долго.

Теперь да, решение о том, какой токен применять (если есть) для каждого символа, также требует времени. Возможно, вы захотите использовать регулярное выражение, которое внутренне создает конечный автомат для выполнения всех возможностей, а не поиск по множеству, как я предлагал изначально. Но то, что действительно убивает вас, - это время выделить всю эту память для 2000 копий строки размером 1 МБ.

Дэн Гибсон предлагает:

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

Это было моё рассуждение о том, чтобы поместить их в ассоциативный массив (например, Java HashSet). Но другая проблема заключается в сопоставлении, например, если один токен является «а», а другой - «ан» - если есть какие-либо общие префиксы, то есть как мы сопоставляем?

Здесь ответ Келтекса пригодится: он делегирует сопоставление Regex, что является отличной идеей, поскольку Regex уже определяет (жадное совпадение) и реализует, как это сделать. После того, как сопоставление установлено, мы можем изучить захваченное, а затем использовать карту Java (также ассоциативный массив), чтобы найти запутанный токен для сопоставленного, необсуждаемого.

Я хотел сосредоточить свой ответ не только на том, как это исправить, но и на том, почему возникла проблема.

2 голосов
/ 03 апреля 2009

Если вы можете найти свои токены с помощью регулярного выражения, вы можете сделать что-то вроде этого: 

RegEx TokenFinder = new Regex("(tokencriteria)");
string newstring = myRegEx.Replace(one_MB_string, new MatchEvaluator(Replacer));

Затем определите Replacer как: 

private string Replacer(Match match)
{
    string token= match.Groups[1].Value;
    return GetObfuscatedString(token);
}
1 голос
/ 03 апреля 2009

Было бы быстрее создать строку по одному токену за раз, заменив его только в случае необходимости? Для этого GetObfuscatedString() может быть реализовано так: 

string GetObfuscatedString(string token)
{
    if (TokenShouldBeReplaced(token))
        return ReplacementForToken(token)
    else
        return token;
}

Теперь вы можете добавить каждый токен в конструктор следующим образом: 

StringBuilder sb = new StringBuilder(one_MB_string.Length);
foreach (string token in tokens)
{
    sb.Append(da.GetObfuscatedString(token));
}

Вам нужно будет только один проход через строку, и это может быть быстрее.

...