perl에서 SPOJ 발생 카운팅 속도 문제가 있습니다

Question

click (translated) (내가 할당 한 것에는 더 큰 테스트와 더 낮은 시간 제한이 있습니다)와 비슷한 문제가 있습니다. 작업의 빠른 번역 :

주어진 순서로 주어진 숫자가 몇 번 있었는지 확인하는 프로그램을 작성하십시오.

입력 : 주어진 숫자에 얼마나 많은 숫자 순서에있는 숫자의 순서

출력 :

내 솔루션까지 발생 수 :

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을 시도했다. 어떤 아이디어?

편집 : 복사 목록 치우는 후 (밝혀 숫자는 음수가 될 수 있습니다) :

#!/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); 

빠른 배 결과 코드 :

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; 

대신 공간 전후를 추가하는 단지 \s와 \b 대신 lookarounds를 사용합니다.

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