perl - Perlでバイナリ検索を実装するにはどうすればよいですか？

Question

Perlで二分探索アルゴリズムを実装したいと思います。私の「配列」は降順でソートされています（実際の配列ではなく、インデックスを取得して値を返す関数）。問題は、同じ値の範囲が存在する可能性があることです。検索した値がこのように広がっている場合は、それを含む最初のインデックスを返したいと思います。

これは私が書いたものです：

# get_val should be a *decreasing* function for idexes $i in min..max,
# formally: for any $i,$j s.t. $max>=$i>$j>=$min :
# $get_val_subref($i, $extra) <= $get_val_subref($j, $extra)
# min and max are the inclusive boundaries for the search
# get_val sub should get an index in min..max and an extra data reference, and return
# the value for the given index
# returns the smallest index $i in min..max for which $get_val_subref($j, $extra)
# returns $searched_val, or undef if no such index exists
sub binary_search {
    my ( $min, $max, $searched_val, $get_val_subref, $get_val_sub_extra_data )
        = @_;
    my ( $mid, $val );
    while ( $min <= $max ) {
        $mid = $min + int( ( $max - $min ) / 2 );
        $val = $get_val_subref->( $mid, $get_val_sub_extra_data );

        if ( $val > $searched_val ) {
            $min = $mid + 1;
        }
        elsif ( $val < $searched_val ) {
            $max = $mid - 1;
        }
        else { ## SEE MY QUESTION BELOW ##

            # surely $val == $searched_val, but is it the first one?

            if (    $mid > $min
                and $get_val_subref->( $mid - 1, $get_val_sub_extra_data )
                == $searched_val )
            {

                # $val == $searched_val and prev($val) == $searched_val
                # we have to continue
                $max = $mid - 1;
            }
            else {

                # $val == $searched_val and prev($val) != $searched_val
                # wer'e done
                return $mid;
            }
        }
    }

    # $val was not found. return undef
    return undef;

}

これはそれを使用するための簡単な例です：

sub get_val_sub {
    my ( $pos, $a ) = @_;
    my $val = $a->[$pos];
    return $val;
}

my @arr = (80, 40, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);
 say "RET:", binary_search( 0, $#arr, 0, \&get_val_sub, \@arr );

問題は、私の最後の（でマークされた## SEE MY QUESTION BELOW ##）が「きれい」かどうかわからないことです。それを行うためのより良い方法はありますか？

score 4 · Accepted Answer

最初は Axeman の回答に同意しましたが、線形論理 (少なくともその一部) を使用した最初の (本当に悪い) 回答と少し似ています。$get_val_subref具体的には、で呼び出す理由はありません$mid - 1。これは不要な線形検索ステップです。

これが私が提案するものです。線形検索を回避することに加えて、非常に単純であるという利点があります。

sub binary_search {
    ...
    my ( $mid, $val, $solution );
    while ( $min <= $max ) {
        ...
        else {
            $solution = $mid; # Store a possible solution.
            $max = $mid - 1;  # But continue with the binary search
                              # until $min and $max converge on each other.
        }
    }
    return $solution;
}

score 1 · Accepted Answer

私は最初にFMの答えに同意しましたが、あなたが示したケース（すべてゼロ）は、線形逆検索には適していません。そして、単純に二分探索を続けるのは好きではありませんでしたが、「最初のx 」には計算可能な値があり、線形バックサーチには - もちろん - 線形のパフォーマンスがあります。 .

だから私はあなたのアイデアが好きですが、次のようにもっとコンパクトです：

else {  
    return $mid unless 
        (   $mid > $min
        and $get_val_subref->( $mid - 1, $get_val_sub_extra_data )
            == $searched_val
        );
    $max = $mid - 1;
}

線形バックサーチはより簡単な計算ですが、値関数が複雑になるにつれて、計算が少ないほど良い結果が得られます。

score 0 · Accepted Answer

0

ニュートンの近似法を探しているかもしれません。

于 2010-10-08T06:38:32.947 に答える

perl - Perlでバイナリ検索を実装するにはどうすればよいですか？

3 に答える 3

Related

Reference