Почему мое Perl-выражение так медленно? - PullRequest
2 голосов
/ 23 октября 2010

У меня есть следующее регулярное выражение:

my $scores_compiled_regex  = qr{^0
                                  \s+
                                  (\p{Alpha}+\d*)
                                  \s+
                                  (\d+
                                  \s*
                                   \p{Alpha}*)
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}                              
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s{2,}
                                   (\d+)?
                                   \s+
                                   \d+ #$
                                   }xos

;

Он должен соответствовать таким строкам (из простого текстового файла):

0            AAS  211    1   1       5       2   6                                                                         15

Пока имена столбцов:

0 INST, NAME             A  A-  B+   B  B-  C+   C  C-  D+   D  D-   F  CR   P  PR   I  I*   W  WP  WF  AU  NR  FN  FS

и это означает: оценка A = 1, оценка A- = 1, отсутствие оценки B +, оценка B = 5 и т. Д. Я пытаюсь разбить его на список, и не игнорируя пустые столбцы, он работает, но очень медленно, также сопоставление очень медленное, и под медленным я имею в виду более 5 секунд, иногда даже больше!

Первые несколько файлов в файле выглядят так:

0 PALMER, JAN            A  A-  B+   B  B-  C+   C  C-  D+   D  D-   F  CR   P  PR   I  I*   W  WP  WF  AU  NR  FN  FS   TOTAL
0            ECON 103   98      35 114   1  14  75           9      35               1          10       1                     

Счеты - это все, что следует за колонкой справа.

есть идеи? Спасибо,

Ответы [ 5 ]

5 голосов
/ 23 октября 2010

См. Мою программу :

use strict;
use warnings;

# Column details and sample line, from the post
my $header  = q{0 AOZSVIN, TAMSSZ B      A  A-  B+   B  B-  C+   C  C-  D+   D  D-   F  CR   P  PR   I  I*   W  WP  WF  AU  NR  FN  FS};
my $sample  = q{0            AAS  150   23  25  16  35  45  14   8  10   2   1   1   4                           4                     };
#               -+--------+-----+-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---..
# chars         1212345678912345612345612341234123412341234123412341234123412341234123412341234123412341234123412341234123412341234...
# num. chars:   2 9        6     6     4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   *
my $unpack  = q{A2A9       A6    A6    A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A4  A*};
$unpack =~ s/\s//g;

# Get column names from the "$header" variable above
my @column_names = unpack($unpack, $header);
s/\s+$// for @column_names; # get rid of trailing spaces
s/^\s+// for @column_names; # get rid of leading spaces

# Some sample data in same format, to try the script out
my @samples = (
  q{0            AAS  150   23  25  16  35  45  14   8  10   2   1   1   4                           4                     },
  q{0            AAS  353    2   3   5   2   6       1                   2                                                     },
  q{0            T304 480M   3  10   8   8   2   3   2   1                                               1               1    },
  q{0            BIOS 206    3  14   5  11   9   8   4   8   3   1   1   6                           7                      },
);

my @big_sample = (@samples) ;#x 200_000;

my @unpacked_data_as_arrayrefs;
m    y @unpacked_data_as_hashrefs;
my $begin = time;
for my $line ( @big_sample ) {
    my @data = unpack($unpack,$line);
    s/\s+$// for @data; # get rid of trailing spaces
    s/^\s+// for @data; # get rid of leading spaces
    push @unpacked_data_as_arrayrefs, [@data]; # stop here if this is all you need
    ## below converts the data in a hash, based on the column names given
    #my %as_hash;
    #for ( 0..$#column_names ) {
    #    $as_hash{ $column_names[$_] } = $data[$_];
    #}
    #push @unpacked_data_as_hashrefs, { %as_hash };
}
my $tot = time - $begin;
print "Done in $tot seconds\n";

# verify all data is as we expected
# uncomment the ones that test hashref, if the above hashref-building code is also uncommented.
{
    use Test::More;
    # first sample
    is($unpacked_data_as_arrayrefs[0]->[2],'AAS'); # AAS in the third column
    is($unpacked_data_as_arrayrefs[0]->[7],'35');  # 35 in the 8th column
    # fourth sample
    is($unpacked_data_as_arrayrefs[3]->[2],'BIOS');
    is($unpacked_data_as_arrayrefs[3]->[15],'6');
    # sixth
    is($unpacked_data_as_arrayrefs[5]->[7],'114');
    is($unpacked_data_as_arrayrefs[5]->[10],'75');
    done_testing();
}

он использует распаковать , чтобы разделить текст на несколько кусков в зависимости от ширины (в символах) полей в вашей строке. См. Также perlpacktut для получения более подробной информации о том, как использовать распаковку для этого вида строкового поиска. Распаковка, возможно, лучше всего подходит для такого формата, поскольку она работает невероятно быстро по сравнению с регулярным выражением (анализирует 600_000 таких строк за ~ 6 секунд на моем компьютере).

Пожалуйста, дайте мне знать, если вам нужно пройтись по какой-либо части программы. Я не размещал это здесь, поскольку это немного на длинной стороне (лучше иметь комментарии, чем нет!). Пожалуйста, скажи мне, если ты предпочитаешь.

4 голосов
/ 23 октября 2010

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

Отклонение Perl разрешит неоднозначность, выбрав «крайнее левое, самое длинное» соответствие, но (а) это не обязательно то, что вы хотите, и (б) количество возможных попыток экспоненциально по количеству числовых полей. вы пропали без вести, отсюда и медлительность.

Для иллюстрации давайте используем более простое регулярное выражение:

/\A(\d+)?\s{2,}
   (\d+)?\s{2,}
   (\d+)?\s{2,}
   (\d+)?\z/xs;

И предположим, что ввод:

123    456    789

(Между каждым числом четыре пробела.) Должно ли 456 возвращаться второе или третье поле? Оба являются действительными совпадениями. В этом случае обратное отслеживание Perl сделает его вторым полем, но я сомневаюсь, что вы действительно хотите положиться на обратное отслеживание Perl, чтобы решить это.

Предложение: Если это вообще возможно, замените каждый \s{2,} регулярным выражением с фиксированным размером. Если вы разрешаете только переменный размер, потому что числа выстроены в столбцы, а числа могут состоять из 1 или 2 цифр, просто используйте substr(), чтобы получить из известных смещений столбца вместо регулярного выражения. (Невозможно эффективно проанализировать данные фиксированной ширины с помощью регулярного выражения.)

3 голосов
/ 24 октября 2010

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

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

chomp( my $header = <DATA> );
my( $num, $name, $rest ) = unpack "a2 a20 a*", $header;
my @grades = split /(?=\s+)/, $rest;

my @grade_keys = map { /(\S+)/} @grades;

my $format = 'a13 a4 a5 ' . join ' ', map { 'a' . length } @grades;

while( <DATA> ) {
    my( $key, $label, $number, @grades ) = unpack $format, $_;

    $$_ =~ s/\s//g foreach ( \$key, \$label, \$number );

    @{ $hash{$key}{$label}{$number} }{@grade_keys} = 
         map { s/\s//g; $_ } @grades;
    }

use Data::Dumper;   
print Dumper( \%hash );

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

Вот структура данных, которую я создал для "AOZSVIN, TAMSSZ B" (чьи данные образца теперь скрыты в редактировании вашего вопроса), хотя вы можете расположить их так, как вам нравится:

$VAR1 = {
          '0' => {
                   'BIOS' => {
                               '206' => {
                                          'F' => '6',
                                          'AU' => '',
                                          'FS' => '',
                                          'B-' => '9',
                                          'D+' => '3',
                                          'CR' => '',
                                          'B+' => '5',
                                          'WP' => '7',
                                          'C+' => '8',
                                          'NR' => '',
                                          'C' => '4',
                                          'PR' => '',
                                          'A' => '3',
                                          'W' => '',
                                          'I*' => '',
                                          'A-' => '14',
                                          'P' => '',
                                          'WF' => '',
                                          'B' => '11',
                                          'FN' => '',
                                          'D' => '1',
                                          'D-' => '1',
                                          'I' => '',
                                          'C-' => '8'
                                        }
                             },
                   'AAS' => {
                              '353' => {
                                         'F' => '2',
                                         'AU' => '',
                                         'FS' => '',
                                         'B-' => '6',
                                         'D+' => '',
                                         'CR' => '',
                                         'B+' => '5',
                                         'WP' => '',
                                         'C+' => '',
                                         'NR' => '',
                                         'C' => '1',
                                         'PR' => '',
                                         'A' => '2',
                                         'W' => '',
                                         'I*' => '',
                                         'A-' => '3',
                                         'P' => '',
                                         'WF' => '',
                                         'B' => '2',
                                         'FN' => '',
                                         'D' => '',
                                         'D-' => '',
                                         'I' => '',
                                         'C-' => ''
                                       },
                              '150' => {
                                         'F' => '4',
                                         'AU' => '',
                                         'FS' => '',
                                         'B-' => '45',
                                         'D+' => '2',
                                         'CR' => '',
                                         'B+' => '16',
                                         'WP' => '4',
                                         'C+' => '14',
                                         'NR' => '',
                                         'C' => '8',
                                         'PR' => '',
                                         'A' => '23',
                                         'W' => '',
                                         'I*' => '',
                                         'A-' => '25',
                                         'P' => '',
                                         'WF' => '',
                                         'B' => '35',
                                         'FN' => '',
                                         'D' => '1',
                                         'D-' => '1',
                                         'I' => '',
                                         'C-' => '10'
                                       }
                            },
                   'T304' => {
                               '480M' => {
                                           'F' => '',
                                           'AU' => '',
                                           'FS' => '1',
                                           'B-' => '2',
                                           'D+' => '',
                                           'CR' => '',
                                           'B+' => '8',
                                           'WP' => '',
                                           'C+' => '3',
                                           'NR' => '',
                                           'C' => '2',
                                           'PR' => '',
                                           'A' => '3',
                                           'W' => '',
                                           'I*' => '',
                                           'A-' => '10',
                                           'P' => '',
                                           'WF' => '1',
                                           'B' => '8',
                                           'FN' => '',
                                           'D' => '',
                                           'D-' => '',
                                           'I' => '',
                                           'C-' => '1'
                                         }
                             }
                 }
        };

А для вашего нового образца "Palmer, Jan":

$VAR1 = {
          '0' => {
                   'ECON' => {
                               '103' => {
                                          'F' => '35',
                                          'AU' => '1',
                                          'FS' => '',
                                          'B-' => '1',
                                          'D+' => '',
                                          'CR' => '',
                                          'B+' => '35',
                                          'WP' => '10',
                                          'C+' => '14',
                                          'NR' => '',
                                          'C' => '75',
                                          'PR' => '',
                                          'A' => '98',
                                          'W' => '',
                                          'I*' => '',
                                          'A-' => '',
                                          'P' => '',
                                          'WF' => '',
                                          'B' => '114',
                                          'FN' => '',
                                          'TOTAL' => '',
                                          'D' => '9',
                                          'D-' => '',
                                          'I' => '1',
                                          'C-' => ''
                                        }
                             }
                 }
        };
3 голосов
/ 23 октября 2010

Если столбцы могут быть пустыми, либо (а) ваши данные неоднозначны, и у вас есть большая проблема, чем медленное регулярное выражение, или (б) ваши данные в формате фиксированной ширины, например:

NAME   A     A-
foo    123   456
bar          789
fubb   111     

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

0 голосов
/ 24 октября 2010

Сначала разбейте строку на куски фиксированной ширины и все.Затем очистите куски.В противном случае вы пытаетесь сделать 2 вещи одновременно, что может привести к ошибкам.

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