Какой самый быстрый способ разбора текста?

Question

Скажем, я хочу извлечь первое слово (или число с плавающей запятой), которое следует за данной строкой, найденной в некотором текстовом файле (см. Как извлечь первое слово, которое следует за строкой? ).Я знаю, что вы можете сделать это с помощью perl или sed, и, возможно, многими другими способами.Я ищу производительность.Какой самый быстрый способ разбора?

Answer 1

Если вы ищете фиксированную строку, вы, вероятно, захотите найти ее, используя что-то вроде Бойера-Мура или Бойера-Мура-Хорспула (для последнего я бы рекомендовал реализацию Рэя Гарднера). Обратите внимание, что B-M и B-M-H оба сублинейны . Регулярные выражения, напротив, в лучшем случае являются линейными ¹ , а многие реализации (те, которые используют обратное отслеживание) квадратичны.

Следующий шаг - обеспечить максимально быстрое считывание данных в память. В действительности, это, как правило, является узким местом. К сожалению, чтобы хорошо справиться с узким местом, вам, как правило, приходится использовать непереносимый код. В Linux mmap обычно подходит вам лучше всего, в то время как в Windows вы обычно лучше, читая большие куски за раз, и вызывая CreateFile с флагом FILE_FLAG_NO_BUFFERING. Также стоит использовать порты завершения ввода / вывода (IOCP) для выполнения чтения, чтобы вы могли выполнять поиск и чтение параллельно.

¹ Теоретически было бы возможно написать движок RE, который выполнял бы сублинейный поиск правильных типов паттернов - но если есть какие-то, которые действительно делают, я не знаю об этом.

Answer 2

Большую часть времени вы будете читать строку с диска или, что еще хуже, читать ее по сети, и это уже на несколько порядков медленнее, чем любой разумный способ поиска, который вы выберете.Тем не менее, если ваша строка уже находится в памяти и вы заранее знаете свой поисковый термин, регулярные выражения (настоящие, основанные на FSM, а не Perl) гарантированно будут работать во времени, линейном по отношению к размеру ввода - так что все быстреетолько будет быстрее с постоянным фактором.Есть быстрая библиотека движков регулярных выражений с именем re2.

Answer 3

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

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

Answer 4

Держу пари, если это действительно простой случай (без реального регулярного выражения), C победит (memchr () и друзья), в противном случае TCL будет сильным соперником, за которым следует Perl (последний требует хороших навыков крафтадля дизайна регулярных выражений).

Приложение : читая ваше описание снова (и сопровождающую ссылку), я бы сказал, что вы должны протестировать некоторые инструменты и сравнить результаты.Можете ли вы предоставить входной файл для нас (где-то) и указать точную проблему на основе этого файла?

Приложение 2 (для Фейнмана) : я сохранил этот сайт (~ 44 КБ, 'soft.dat ') и выполнил повторный поисковый тест (как вы предложили: "дизайн сайта /") в Perl.Используемый код:

 ...
 use Benchmark qw' timeit timestr ';

{
  open my $fh, '<', 'sof.dat' or die $!;
  undef $/;
  our $data = <$fh>;
  close $fh;

   my $count = 100000;
   my  $t = timeit($count, ' $data =~ m|site design /| ? 1 : 0 '  );
   print "$count loops of code took:", timestr($t),"\n";
}
...

При моей настройке (2,4 ГГц E6600, Win7, Activeperl) вышло следующее время:

100000 циклов кода заняло:1 раз в час (1,36 usr + 0,00 sys = 1,36 CPU) @ 73746,31 / s (n = 100000)

, что означает, что я могу найти этот текст на этой странице около 74 тысяч раз в секунду.

Если я включу полную обработку файла:

use Benchmark qw' timeit timestr ';

{
   my $count = 10000;
   my  $t = timeit($count, q{
                   open my $fh, '<', 'sof.dat' or die $!;
                   undef $/;
                   our $data = <$fh>;
                   close $fh;
                   $data =~ m|site design /| ? 1 : 0
                   } );
   print "$count loops of code took:", timestr($t),"\n";
}

, мы получим только:

10000 циклов кода заняло: 3 секунды Wallclock (1,70 usr +1,51 sys = 3,21 CPU) @ 3110,42 / s (n = 10000)

около 3 тысяч проходов поиска / поиска в секунду.

С уважением

rbo