Regex vs. string: find () для простой границы слова

Question

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

Один из способов сделать это - использовать регулярное выражение , например:

.*\y(good|better|best)\y.*

Еще один способ сделать это - использовать псевдо код, подобный следующему:

 if ( (readLine.find("good")   != string::npos) ||
      (readLine.find("better") != string::npos) ||
      (readLine.find("best")   != string::npos) )
 {
   // line contains a word from a finite set of words.
 }

Какой путь будет иметь лучшую производительность? (то есть скорость и загрузка процессора)

Answer 1

Вы не узнаете, что быстрее, пока не измерите, но на карту поставлены следующие проблемы:

1. Реализация регулярного выражения, esp. нужно ли прекомпилировать (например, Google RE2, регулярные выражения POSIX).
2. Реализация string::find.
3. Длина строки, в которой вы ищете.
4. Сколько строк вы ищете.

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

Answer 2

Регулярное выражение будет работать лучше, но избавьтесь от этих '. *' Частей. Они усложняют код и не служат никакой цели. Регулярное выражение вроде этого:

\y(good|better|best)\y

будет искать строку за один проход. Алгоритм, который он строит из этого регулярного выражения, сначала будет искать \ y, затем символ 1 (g | b), затем символ 2 (g => go или b => be), символ 3 (go => goo или be => bes | bet), персонаж 4 (go => good или bes => best или bet => bett) и т. д. Без создания собственного конечного автомата это происходит так быстро, как только может.

Answer 3

Очевидно, что это не второе (с использованием 'find'), так как вы выполняете три сравнения (необходимо перебрать строку как минимум 3 раза) вместо одного, надеюсь, умного.Если механизм регулярных выражений работает вообще так, как должен (а я полагаю, работает), то он, вероятно, будет как минимум в три раза быстрее.