한 번만 나타나는 목록에서 값을 가져 오는 방법은 무엇입니까?

Question

인터넷에서이 질문을 보았습니다. 다른 숫자가 목록에 두 번 나타나는 동안 목록에 한 번만 나타나는 유일한 번호를 가져옵니다. 데이터는 크고 분류되지 않은 약 백만 개의 숫자가 포함되어 있으며 한 번만 나타나는 한 개의 숫자를 제외하고 모든 숫자가 두 번 나타나는 무작위 순서의 음수도 포함될 수 있습니다.

my @array = (1,1,2,3,3,4,4) 

출력 :

2 

단지 2리스트에서 반복하지 않는다. 나는 나의 해결책을 시도했다.

my $unique; 
$unique ^= $_ for(@array); 
say $unique; 

음수에는 맞지 않지만 빠릅니다.

키가 숫자이고 값이 목록에있는 횟수 인 해시를 시도했습니다. 해시를 반대로하고 다른 모든 숫자의 키가 2 인 경우 키를 1로하여 값을 인쇄하십시오. 해시 솔루션은 100 만 개의 큰 입력 값으로 인해 속도가 느리지 만 음수에서는 작동합니다.

나는 탭 전체 목록을 결합 정규식 방법을 시도하고

my $combined = join " ", @array; 
$combined !~ (\d+).*$1; 
say $1; 

을 사용하지만 목록

그것을 할 수있는 빠른 방법이 있나요의 마지막 번호를? 정규식을 사용하는 아이디어?

편집 : 더 나은 답변

Answer 1

이 꽤 빠른 것 같다

use v5.10; use strict; use warnings; 

sub there_can_be_only_one { 
    my @counts; 
    $counts[ $_>=0 ? 2*$_ : (-2*$_)-1 ]++ for @{$_[0]}; 
    $counts[ $_>=0 ? 2*$_ : (-2*$_)-1 ]==1 and return $_ for @{$_[0]}; 
    return; 
} 

my @array = (1,1,-4,-4,2,3,-1,3,4,-1,4); 
say there_can_be_only_one(\@array); 

그것은 기본적으로 해시 기술의 변화,하지만 해시 대신 배열을 사용하여. 음수를 처리해야하기 때문에 @counts 배열에서 수정되지 않은 숫자를 사용할 수 없습니다. 물론 부정적인 인덱스는 Perl에서 작동하지만 긍정적 인 인덱스를 위해 데이터를 덮어 씁니다. 실패.

그래서 우리는 2의 보수와 비슷한 것을 사용합니다. 배열에 양수를 2*$_, 음수를 (-2*$_)-1으로 저장합니다. 즉이 용액리스트 정렬에 의존하고, 단순히 위에 두 과정을 수행하지 않는다

Integer: ... -3 -2 -1 0 1 2 3 ... 
Stored as: ... 5 3 1 0 2 4 6 ... 

때문에 (물론, 평균 1.5가 패스)는 (N) O에서 수행과 대조적으로, Schwern의 O (nlog n) 용액과 대조된다. 따라서 더 큰 목록 (수백만 개의 정수)은 상당히 빨라야합니다.

use v5.10; use strict; use warnings; 
use Benchmark qw(timethese); 
use Time::Limit '60'; 

sub tobyink { 
    my @counts; 
    $counts[ $_>=0 ? 2*$_ : (-2*$_)-1 ]++ for @{$_[0]}; 
    $counts[ $_>=0 ? 2*$_ : (-2*$_)-1 ]==1 and return $_ for @{$_[0]}; 
    return; 
} 

sub schwern { 
    my @nums = sort @{$_[0]}; 
    return $nums[0] if $nums[0] != $nums[1]; 
    for (1..$#nums-1) { 
     my($prev, $this, $next) = @nums[$_-1, $_, $_+1]; 
     return $this if $prev != $this && $next != $this; 
    } 
    return $nums[-1] if $nums[-1] != $nums[-2]; 
} 

my @input = (
    1..2_000_000, # 1_000_001 only appears once 
    1..1_000_000, 1_000_002..2_000_000, 
); 

timethese(1, { 
    tobyink => sub { tobyink(\@input) }, 
    schwern => sub { schwern(\@input) }, 
}); 

__END__ 
Benchmark: timing 1 iterations of schwern, tobyink... 
schwern: 11 wallclock secs (8.72 usr + 0.92 sys = 9.64 CPU) @ 0.10/s (n=1) 
     (warning: too few iterations for a reliable count) 
tobyink: 5 wallclock secs (5.01 usr + 0.08 sys = 5.09 CPU) @ 0.20/s (n=1) 
     (warning: too few iterations for a reliable count) 

UPDATE : 내 최초의 대답에 나는 어떤 숫자가 두 번 이상 나타날 수 없다는 것을 세부 사항을 놓친 여기 내 (상당히 저전력) 넷북에 대한 빠른 비교입니다. 나는 어떤 숫자가 세 번 이상 나타날 수 있다고 생각했다. 이 추가 세부 사항을 사용하여, 우리는 더 빨리 갈 수

이

sub there_can_be_only_one { 
    my $tmp; 
    $tmp ^= $_>=0 ? 2*$_ : (-2*$_)-1 for @{$_[0]}; 
    $tmp%2 ? ($tmp+1)/-2 : $tmp/2; 
} 

say there_can_be_only_one(\@array); 

이 나의 최초의 대답보다 약 30 % 더 빠르게 실행됩니다.

Answer 2

이 해시에 모든 것을 던져입니다 처리하는 표준 방법을 제목을 Repharsed.

use v5.10; 
use strict; 
use warnings; 

my @nums = (2..500_000, 500_002..1_000_000, 0..1_000_001); 

my %count; 
for (@nums) { 
    $count{$_}++ 
} 

for (keys %count) { 
    say $_ if $count{$_} == 1; 
} 

그래, 상당히 느립니다.

는 그럼 난 ... 나는 싱글을 찾기 위해 해시를 통해 루프 것을 방지 할 수 어쩌면

my @nums = (2..500_000, 500_002..1_000_000, 0..1_000_001); 
my %uniqs; 
my %dups; 
for (@nums) { 
    if($uniqs{$_}) { 
     delete $uniqs{$_}; 
     $dups{$_} = 1; 
    } 
    elsif(!$dups{$_}) { 
     $uniqs{$_} = 1; 
    } 
} 

print join ", ", keys %uniqs; 

생각하지만 그도 느렸다.

이것은 내가 생각해 낸 가장 빠른 것입니다. 위의 절반 정도 소요됩니다.

use v5.10; 
use strict; 
use warnings; 

my @nums = (2..500_000, 500_002..1_000_000, 0..1_000_001); 
@nums = sort @nums; 
say $nums[0] if $nums[0] != $nums[1]; 
for (1..$#nums-1) { 
    my($prev, $this, $next) = @nums[$_-1, $_, $_+1]; 
    say $this if $prev != $this && $next != $this; 
} 
say $nums[-1] if $nums[-1] != $nums[-2]; 

목록을 정렬하면 해당 항목을 반복하고 주어진 항목의 이웃이 중복되는지 확인할 수 있습니다. 첫 번째 요소와 마지막 요소에주의해야합니다. 모든 반복 작업에 대해 특별한 경우를 실행하지 않아도되도록 루프 외부에 체크를했습니다.

sort이 O (nlogn)이기 때문에 숫자 목록이 커지면 결국이 해법은 해시 기반 것보다 느려지지만 그 전에 메모리가 부족할 것입니다.

마지막으로이 목록이 크면 데이터베이스의 디스크에 저장하는 것이 좋습니다. 그런 다음 메모리를 사용하지 않고 데이터베이스가 효율적으로 작업하도록 할 수 있습니다.

Answer 3

음수에는 맞지 않지만 빠릅니다. 당신이 XOR은 음수에 작업 할 경우

사실, 당신은 단지 그들을 캐릭터 라인 화해야합니다

my @array = (-10..-7,-5..10,-10..10); 

my $unique; 
$unique ^= "$_" for @array; 
say $unique; 

출력

-6 

그리고 일을 몇 가지 빠른 벤치 마크 :

Benchmark: timing 100 iterations of schwern, there_can_be_only_one, tobyink, xor_string... 
    schwern: 323 wallclock secs (312.42 usr + 7.08 sys = 319.51 CPU) @ 0.31/s (n=100) 
there_can_be_only_one: 114 wallclock secs (113.49 usr + 0.02 sys = 113.51 CPU) @ 0.88/s (n=100) 
    tobyink: 177 wallclock secs (176.76 usr + 0.14 sys = 176.90 CPU) @ 0.57/s (n=100) 
xor_string: 98 wallclock secs (97.05 usr + 0.00 sys = 97.05 CPU) @ 1.03/s (n=100) 

수학적 번역을 xor-ing하는 것보다 문자열을 xoring하는 것이 15 % 빠릅니다. 양수

결과 - 정렬 된 목록은 어떻게됩니까?

Schwern의 솔루션은 흥미로운 결과를 가져옵니다. 그는 목록을 정렬 한 다음 모든 고유 요소를 검색했습니다.

우리가 doubletons의 군중 만 1 싱글이 있다는 추가 정보를 사용하는 경우, 우리는 신속하게 단순화 할 수 그러나 우리의 비교 4.

의 요인을 감소 페어의 비교를 수행하여 검색 우리 이진 검색을 수행하면 더 잘 수행 할 수 있습니다. 알려진 일치 쌍 사이의 장벽에서 목록을 분리하면 남은 두 목록 중 홀수 인 목록 중 어느 것이 우리 싱글 톤을 포함합니다.나는이 솔루션의 일부 벤치마킹을했고, 더 빨리 (물론) 무엇보다도 크기의 주문이다 :

use strict; 
use warnings; 
use Benchmark qw(timethese); 

sub binary_search { 
    my $nums = $_[0]; 

    my $min = 0; 
    my $max = $#$nums; 
    while ($min < $max) { 
     my $half = ($max - $min)/2; # should always be an integer 
     my ($prev, $this, $next) = ($min+$half-1) .. ($min+$half+1); 

     if ($nums->[$prev] == $nums->[$this]) { 
      if ($half % 2) {   # 0 0 1 1 2 2 3 (half = 3) 
       $min = $next; 
      } else {     # 0 1 1 2 2 (half = 2) 
       $max = $prev - 1; 
      } 
     } elsif ($nums->[$this] == $nums->[$next]) { 
      if ($half % 2) {   # 0 1 1 2 2 3 3 (half = 3) 
       $max = $prev; 
      } else {     # 0 0 1 1 2 (half = 2) 
       $min = $next + 1;   
      } 
     } else { 
      $max = $min = $this; 
     } 
    } 

    return $nums->[$min]; 
} 

sub xor_string { 
    my $tmp; 
    $tmp ^= "$_" for @{$_[0]}; 
} 

sub brute { 
    my $nums = $_[0]; 

    return $nums->[0] if $nums->[0] != $nums->[1]; 
    for (1..$#$nums-1) { 
     my($prev, $this, $next) = @$nums[$_-1, $_, $_+1]; 
     return $this if $prev != $this && $next != $this; 
    } 
    return $nums->[-1] if $nums->[-1] != $nums->[-2]; 
} 

sub pairwise_search { 
    my $nums = $_[0]; 
    for (my $i = 0; $i <= $#$nums; $i += 2) { 
     if ($nums->[$i] != $nums->[$i+1]) { 
      return $nums->[$i]; 
     } 
    } 
} 

# Note: this test data is very specific and is intended to take near the maximum 
# number of steps for a binary search while shortcutting halfway for brute force 
# and pairwise 
my @input = sort {$a <=> $b} (0..500_003, 500_005..1_000_000, 0..1_000_000); 
#my @input = sort {$a <=> $b} (0..499_996, 499_998..1_000_000, 0..1_000_000); 

timethese(1000, { 
    brute => sub { brute(\@input) }, 
    pairwise => sub { pairwise_search(\@input) }, 
    xor_string => sub { xor_string(\@input) }, 
    binary => sub { binary_search(\@input) }, 
}); 

결과 :

Benchmark: timing 1000 iterations of binary, brute, pairwise, xor_string... 
    binary: 0 wallclock secs (0.02 usr + 0.00 sys = 0.02 CPU) @ 62500.00/s (n=1000) 
      (warning: too few iterations for a reliable count) 
    brute: 472 wallclock secs (469.92 usr + 0.05 sys = 469.97 CPU) @ 2.13/s (n=1000) 
    pairwise: 216 wallclock secs (214.74 usr + 0.00 sys = 214.74 CPU) @ 4.66/s (n=1000) 
xor_string: 223 wallclock secs (221.74 usr + 0.06 sys = 221.80 CPU) @ 4.51/s (n=1000)