Проблемы со скоростью при подсчете SPOJ в Perl

Question

У меня проблема с задачей, похожей на эту: click (переведено) (та, с которой мне было назначено, имеет гораздо большие тесты и меньший срок),Быстрый перевод задания:

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

Ввод: заданное число, сколько чисел в последовательности,последовательность чисел

Вывод: Количество вхождений

Мои решения на данный момент:

1:

#!/usr/bin/env perl

while (<>) {
    $in = $_;
    @nums = split / /, $in, 3;

    $what = shift @nums;
    shift @nums;
    $rest = shift @nums;
    $rest = " ".$rest." ";

    $sum = () = $rest =~ /(?<=\s)$what(?=\s)/g;

    print $sum;
    print "\n";
}

2:

#!/usr/bin/env perl

while (<>) {
    $in = $_;
    @nums = split / /, $in, 3;

    $what = shift @nums;
    shift @nums;
    $rest = shift @nums;
    $rest = " ".$rest." ";

    if(!$reg{$what}){
        $reg{$what} = qr/(?<=\s)$what(?=\s)/;
    }
    $sum = () = $rest =~ /$reg{$what}/g;

    print $sum;
    print "\n";
}

Я также попробовал метод грубой силы, хеш-таблицы, grep ... Все превышают заданный лимит времени, и я понятия не имею, как написать что-нибудь, чтобудет работать быстрее, чем два выше.Любые идеи?

edit : После избавления от копирования списков (оказывается, числа также могут быть отрицательными):

#!/usr/bin/env perl

while ($line = <>) {
        $line =~ s/^(-?\d+) \d+//;
        $what = $1;

        $sum = () = $line =~ / $what\b/g;

    print $sum;
    print "\n";
}

edit2 : через http://www.chengfu.net/2005/10/count-occurrences-perl/:

print $sum = (($line =~ s/ $1\b//g)+0);

код в 2 раза быстрее, чем:

print $sum = () = $line =~ / $1\b/g;

Работает сейчас, спасибо:)

Answer 1

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

while (<>) {
    $in = $_;                   # COPY
    @nums = split / /, $in, 3;  # COPY

    $what = shift @nums;
    shift @nums;
    $rest = shift @nums;        # COPY
    $rest = " ".$rest." ";      # COPY

    $sum = () = $rest =~ /(?<=\s)$what(?=\s)/g;

    print $sum;
    print "\n";
}

Чтобы ускорить процесс, избегайте копий. Например, используйте while ($in = <>) (или просто пропустите $in и используйте $_).

Для извлечения $what и подсчета, я думаю, я бы попробовал это вместо split:

$in =~ s/^(\d+) \d+//;
$what = $1;

Вместо добавления пробела вперед и назад, просто используйте \b вместо обходных путей с \s.

    $sum = () = $in =~ /\b$what\b/g;