Ускорьте поиск строки

Question

Я использую этот простой алгоритм для поиска некоторого текста в документе и отслеживания того, на какой странице я его нашел

for (int i = 1; i <= a.PageCount; i++)
{
    Buf.Append(a.Pages[i].Text);
    String contain = Buf.ToString();
    if (contain != "")
    {
        // Inside is dictionary of keys and value contain page where I found it
        foreach (KeyValuePair<string, List<string>> pair in inside)
        {
              if (contain.Contains(pair.Key))
                  inside[pair.Key].Add((i).ToString());
        }
    }

    Buf.Clear();
 }

У меня нет проблем с этим, но когда я ищу документ на 700 страниц,поиск более 500 ключей, это очень медленно, прошло около 1-2 минут, есть ли способ, как ускорить его?Я использую c #

Спасибо!

Answer 1

Несколько баллов:

• Избавиться от Buf; просто присвойте a.Pages[i].Text непосредственно contain:
• inside[pair.Key] тратит время на поиск значения, связанного с этим ключом; время потрачено впустую, потому что у вас есть намного более дешевая ссылка на этот объект в pair.Value.
• если у вас есть список целочисленных значений, почему вы храните их как строки?

Пример кода:

for (int i = 1; i <= a.PageCount; i++)
{
    String contain = a.Pages[i].Text
    if (contain != "")
    {
        // Inside is dictionary of keys and value contain page where I found it
        foreach (KeyValuePair<string, List<int>> pair in inside)
        {
            if (contain.Contains(pair.Key))
                pair.Value.Add(i);
        }
    }
}

Наконец, убедитесь, что Pages действительно использует индекс на основе одного. Коллекции чаще всего индексируются нулями.

РЕДАКТИРОВАТЬ , поскольку Pages является словарем:

foreach (KeyValuePair<int, Page> kvp in a.Pages)
{
    string contain = kvp.Value.Text;
    if (contain == "")
        continue;
    foreach (KeyValuePair<string, List<int>> pair in inside)
        if (contain.Contains(pair.Key))
            pair.Value.Add(kvp.Key);
}

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

Как заметил кто-то еще, главная проблема в том, что вы звоните contain.Contains(pair.Key) 350 000 раз; это, вероятно, ваше узкое место. Вы можете профилировать метод, чтобы узнать, правда ли это. Если это равно true, тогда, вероятно, лучшим вариантом будет что-то вроде алгоритма Рабина Карпа, предложенного Miserable Variable.

Answer 2

[[

РЕДАКТИРОВАТЬ: следующее не имеет значения, так как вы очищаете Buf в конце цикла (хотя обратите внимание, что вам не нужен buf, string pageText = a.Pages[i].Text это все, что вам нужно)

Что такое Buf?У вас есть

Buf.Append(a.Pages[i].Text);

Разве это не заставляет Contains просматривать все более крупные строки?Я удивлен, что у вас не хватает памяти на 700 страниц.

]]

Есть более эффективные способы проверить, появляется ли any of a set of strings в другом string.Например, вы можете подготовить древовидную структуру ключей, чтобы вам не приходилось сравнивать несколько раз.

См. Алгоритм Рабина-Карпа

Рассмотрите существующие сторонние библиотеки, их должно быть несколько.

Answer 3

Стандартные процедуры производительности / отладки - закомментируйте кусочки вашего кода и оцените.Добавляйте их обратно по одному, пока не станет «плохо».Это, вероятно, ваша проблемная область. Например,

, вы можете начать с комментирования всего foreach.

Похоже, что используются некоторые возможно сложные / дорогие объекты - внутри, в Buf и т. Д. Закомментируйте их использование и возвращайте по одному.

Answer 4

У меня нет 700 страниц для тестирования, но вы можете попробовать использовать регулярное выражение:

var s = Stopwatch.StartNew();
var r = new Regex(string.Join("|", from x in inside select Regex.Escape(x.Key)));

for (int i = 1; i <= a.PageCount; i++)
{
    foreach (Match match in r.Matches(a.Pages[i].Text))
    {
        inside[match.Value].Add(i.ToString());
    }
}

Console.WriteLine(s.Elapsed);