проблемы с производительностью при нахождении n-го вхождения символа с регулярным выражением

Question

У меня есть регулярное выражение, чтобы найти nth вхождение символа в строку, вот код:

 public static int NthIndexOf(this string target, string value, int n)
    {
        Match m = Regex.Match(target, "((" + value + ").*?){" + n + "}");

        if (m.Success)
        {
            return m.Groups[2].Captures[n - 1].Index;
        }
        else
        {
             return -1;
        }
    }

Теперь у меня есть 1594 записи в этой строке с 1593 точками с запятой. Если я напишу:

tempstring.NthIndexOf(";", 1593) 

Ответ возвращается немедленно и правильно. Если я дам что-нибудь за 1594, оно зависнет. Кто-нибудь знает, как это исправить?

Контрольный пример

 string holder = "test;test2;test3";
        string test = "";
        for (int i = 0; i < 600; i++)
        {
            test += holder;
        }
        int index = test.NthIndexOf(";", 2000);

Это занимает очень много времени. Измените 600 на 6, и это очень быстро. Сделайте 2000 до 1700, и это очень быстро.

Почему мое регулярное выражение лица такое медленное?

Answer 1

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

public static int NthIndexOf(this string target, char testChar, int n)
{
   int count = 0;

   for(int i=0; i<target.Length; i++)
   {
      if(target[i] == testChar)
      {
         count++;
         if(count == n) return i;  
      }
   }

   return -1;
}

и используйте это. У него должно быть гораздо меньше ограничений.

Что касается того, почему ваше оригинальное регулярное выражение работает медленно, вот что я подозреваю:

• Для вашего быстрого случая это работает, потому что он может найти совпадение при первом прохождении (с каждой группой, совпадающей ровно с одним символом)
• Для медленного случая это потому, что он не может найти соответствие (и никогда не найдет его, потому что не хватает точек с запятой, чтобы удовлетворить регулярное выражение), но он рекурсивно пытается всеми возможными способами разбить строку (что действительно большая операция)

Answer 2

Попробуйте использовать более четкое и эффективное регулярное выражение:

"^(?:[^" + value + "]*" + value + "){" + (n - 1) + "}([^" + value + "]*)

Это создаст следующее регулярное выражение для tempstring.NthIndexOf(";", 1593):

^(?:[^;]*;){1592}([^;]*)

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

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