どのように2つの配列の要素間の距離を見つけるには？

Question

私はperlで書いていますが、アルゴリズムの質問のように思えます。他の言語での返信は大歓迎です。

私は整数の2つのソート配列、shortとlongを持っています。 short内の各要素について、私はlongに最も近い要素を見つけたい、と私の特定のケースでは、私は距離のヒストグラムを作りたいです。

sub makeDistHist { 
    my ($hist, $short, $long, $max) = @_; # first 3 are array references 

    my $lIndex = 0; 
    foreach my $s (@$short) { 
     my $distance = abs($s - $long->[$lIndex]); 
     while (abs($s - $long->[$lIndex+1]) < $distance) { 
      $distance = abs($s - $long->[$lIndex]); 
      $lIndex++; 
     } 
     $distance = $max if $distance>$max; # make overflow bin 
     $hist->[$distance]++; 
    } 
} 

これはshortとlongがソートさに依存しています：

はここで私が使用しているアルゴリズムです。

は、ここで私は私のアルゴリズムをテストするために書いたサブルーチンです。最初のテストは成功しますが、2番目は失敗：それはないですので、私はそれから1つのを引いた要素のコピーにlongを比較する場合

は

$VAR1 = [ 
      7, 
      5 
     ]; 

（問題が解決しない：ここ

sub test { # test makeDistHist 

    my @long = qw(100 200 210 300 350 400 401 402 403 404 405 406); 
    my @short = qw(3 6 120 190 208 210 300 350); 
    my @tarHist; 
    $tarHist[97]++; 
    $tarHist[94]++; 
    $tarHist[20]++; 
    $tarHist[10]++; 
    $tarHist[2]++; 
    $tarHist[0]+=3; 

    my $max = 3030; 
    my @gotHist; 
    makeDistHist(\@gotHist, \@short, \@long, $max); 

    use Test::More tests => 2; 
    is_deeply(\@gotHist, \@tarHist, "did i get the correct distances for two different arrays?"); 

    @gotHist =(); 
    @tarHist = (@long+0); 
    makeDistHist(\@gotHist, \@long, \@long, $max); 
    is_deeply(\@gotHist, \@tarHist, "did i get the correct distances between an array and itself?"); # nope! 
    print Dumper(\@gotHist); 
} 

をダンプです。。アルゴリズムlongより厳密に短くすることshortを要求するも、私は401、402を変更した場合... 402に、404 ... gotHistが(7, undef, 5)なり）

は、ここで私はy'allのから欲しいものです：最初とf oremost、これのための働くアルゴリズム。私が持っているものを修正するか、布全体から別のものを考案する。第二に、私はデバッグのスキルを助けることができます。既存のアルゴリズムの問​​題を特定するにはどうすればよいでしょうか？私はこの質問をする:)

感謝を必要としないことをやることができれば！

Answer 1

サブルーチンを分割する必要があります。距離の計算とヒストグラムの作成は2つの異なるものであり、2つを組み合わせようとすると多くの明瞭さが失われます。最初の最も簡単な解決策と

スタート。私はソートされた@longを使用して潜在的な最適化を理解しますが、List::Util::minが遅い場合にのみそれに頼ります。

Statistics::Descriptiveを使用すると、度数分布を生成できます。

#!/usr/bin/perl 

use strict; use warnings; 
use List::Util qw(min); 
use Statistics::Descriptive; 

my $stat = Statistics::Descriptive::Full->new; 

my @long = (100, 200, 210, 300, 350, 400, 401, 402, 403, 404, 405, 406); 
my @short = (3, 6, 120, 190, 208, 210, 300, 350); 

for my $x (@short) { 
    $stat->add_data(find_dist($x, \@long)); 
} 

my $freq = $stat->frequency_distribution_ref([0, 2, 10, 20, 94, 97]); 
for my $bin (sort { $a <=> $b } keys %$freq) { 
    print "$bin:\t$freq->{$bin}\n"; 
} 

sub find_dist { 
    my ($x, $v) = @_; 
    return min map abs($x - $_), @$v; 
} 

出力：もちろん

[sinan@archardy so]$ ./t.pl 
0:  3 
2:  1 
10:  1 
20:  1 
94:  1 
97:  1

、どのモジュールを使用してソート@longのあなたの仮定を使用せずにこれを行うことが可能です：

#!/usr/bin/perl 

use strict; use warnings; 

my @long = (100, 200, 210, 300, 350, 400, 401, 402, 403, 404, 405, 406); 
my @short = (3, 6, 120, 190, 208, 210, 300, 350); 

my @bins = reverse (0, 2, 10, 20, 94, 97); 
my %hist; 

for my $x (@short) { 
    add_hist(\%hist, \@bins, find_dist($x, \@long)); 
} 

for my $bucket (sort { $a <=> $b } keys %hist) { 
    print "$bucket:\t$hist{$bucket}\n"; 
} 

sub find_dist { 
    my ($x, $v) = @_; 
    my $min = abs($x - $v->[0]); 
    for my $i (1 .. $#$v) { 
     my $dist = abs($x - $v->[$i]); 
     last if $dist >= $min; 
     $min = $dist; 
    } 
    return $min; 
} 

sub add_hist { 
    my ($hist, $bins, $x) = @_; 
    for my $u (@$bins) { 
     if ($x >= $u) { 
      $hist{ $u } += 1; 
      last; 
     } 
    } 
    return; 
} 

Answer 2

デバッグに関する部分については、ブレークポイントを可能にIDEを使用しています。私はperlの例を持っていませんが、PHPとASP.NETの場合、それぞれEclipseとVisual Studio（または無料版、Visual Web Developer）があります。