現: 2016-04-21 (木) 15:37:58 takatsuka[3] [4] | |||
---|---|---|---|
Line 1: | Line 1: | ||
+ | #contents | ||
+ | PHP には何故か二分探索(バイナリサーチ)が標準で用意されてません。 | ||
+ | PHPにとってあまり重要ではないのか?言語的に別の手段で解決できるものなのか?というような事情はわかってはいませんが、あれば便利だと思うので作ってみました。 | ||
+ | -配列内にお目当ての要素があるか否かだけの関数(いわゆる C++ で言う std::binary_search )だけでなく、 | ||
+ | 最初に現れた指定値以上の要素の位置を返す関数( std::lower_bound )と、 | ||
+ | 最初に現れた指定値を超えた要素の位置を返す関数( std::upper_bound )を用意してます。 | ||
+ | きっと、ありがたみ的には binary_search より lower_bound、upper_bound の方が上だろうなと思います。 | ||
+ | |||
+ | -単純な配列にしか使えないんじゃ使い勝手が悪いので、比較関数を渡せるようにして、どんな形の配列でも対応できるようにしてあります。 | ||
+ | |||
+ | -配列内に同じ値(要素)がダブって存在していても、正しくソートされている配列であれば正常に動作します。 | ||
+ | もちろん、正しくソートされてない配列の場合の結果は不定です。 | ||
+ | |||
+ | ***クラス定義 [#t3b1a0db] | ||
+ | #prettify{{ | ||
+ | <?php | ||
+ | |||
+ | class CBinarySearch | ||
+ | { | ||
+ | // std::upper_bound 普通の配列専用版 | ||
+ | public static function UpperBound( $list, $value ) | ||
+ | { | ||
+ | return self::UpperBoundT( $list, $value, | ||
+ | function( $value, $elem ){ | ||
+ | return $value < $elem; | ||
+ | }); | ||
+ | } | ||
+ | |||
+ | // std::upper_bound 自前比較関数を渡す版 | ||
+ | public static function UpperBoundT( $list, $value, $funcLess ) | ||
+ | { | ||
+ | $count = count($list); | ||
+ | $first = 0; | ||
+ | while( 0 < $count ){ | ||
+ | $count2 = (int)($count / 2); | ||
+ | $mid = $first + $count2; | ||
+ | if( ! $funcLess( $value, $list[$mid] ) ){ | ||
+ | $first = ++$mid; | ||
+ | $count -= $count2 + 1; | ||
+ | }else{ | ||
+ | $count = $count2; | ||
+ | } | ||
+ | } | ||
+ | return $first; | ||
+ | } | ||
+ | |||
+ | // std::lower_bound 普通の配列専用版 | ||
+ | public static function LowerBound( $list, $value ) | ||
+ | { | ||
+ | return self::LowerBoundT( $list, $value, | ||
+ | function( $elem, $value ){ | ||
+ | return $elem < $value; | ||
+ | }); | ||
+ | } | ||
+ | |||
+ | // std::lower_bound 自前比較関数を渡す版 | ||
+ | public static function LowerBoundT( $list, $value, $funcLess ) | ||
+ | { | ||
+ | $count = count($list); | ||
+ | $first = 0; | ||
+ | while( 0 < $count ){ | ||
+ | $count2 = (int)($count / 2); | ||
+ | $mid = $first + $count2; | ||
+ | if( $funcLess( $list[$mid], $value ) ){ | ||
+ | $first = ++$mid; | ||
+ | $count -= $count2 + 1; | ||
+ | }else{ | ||
+ | $count = $count2; | ||
+ | } | ||
+ | } | ||
+ | return $first; | ||
+ | } | ||
+ | |||
+ | // std::binary_search 普通の配列専用版 | ||
+ | public static function BinarySearch( $list, $value ) | ||
+ | { | ||
+ | $f = function( $elem, $value ){ | ||
+ | return $elem < $value; | ||
+ | }; | ||
+ | return self::BinarySearchT( $list, $value, $f, $f ); | ||
+ | } | ||
+ | |||
+ | // std::binary_search 自前比較関数を渡す版 | ||
+ | public static function BinarySearchT( $list, $value, $funcLess0, $funcLess1 ) | ||
+ | { | ||
+ | $first = self::LowerBoundT($list, $value, $funcLess0 ); | ||
+ | return $first>=count($list) ? false : ! $funcLess1( $value, $list[$first] ); | ||
+ | } | ||
+ | |||
+ | } | ||
+ | }} | ||
+ | ***サンプルコード [#j2930aa3] | ||
+ | #prettify{{ | ||
+ | // サンプルコード | ||
+ | $list = [-5, 0, 5, 10, 10, 11, 11, 13, 18]; // ソート済みの配列 | ||
+ | $testValues = [-7, -5, 0, 1, 2, 10, 12, 13, 18, 19 ]; // テストケース | ||
+ | |||
+ | echo '<br>LowerBound'; | ||
+ | foreach( $testValues as $v ){ | ||
+ | echo " {$v}:" . CBinarySearch::LowerBound($list,$v); // 結果表示 | ||
+ | } | ||
+ | |||
+ | echo '<br>UpperBound'; | ||
+ | foreach( $testValues as $v ){ | ||
+ | echo " {$v}:" . CBinarySearch::UpperBound($list,$v); // 結果表示 | ||
+ | } | ||
+ | |||
+ | echo '<br>BinarySearch'; | ||
+ | foreach( $testValues as $v ){ | ||
+ | echo " {$v}:" . ( CBinarySearch::BinarySearch($list,$v) ? '1' : '0' ); // 結果表示 | ||
+ | } | ||
+ | |||
+ | // 自前比較関数版 | ||
+ | echo '<br>BinarySearchT'; | ||
+ | foreach( $list as $v ){ // サンプルデータの作成 | ||
+ | $list2[] = [ 'id' => $v ]; | ||
+ | } | ||
+ | foreach( $testValues as $v ){ | ||
+ | $less0 = function( $elem, $value ){ // 引数の型違いの関数は別々の関数にするしかない。 | ||
+ | return $elem['id'] < $value; // ちょっと冗長っぽいかもだけど、 | ||
+ | }; // 致し方ない。 | ||
+ | $less1 = function( $value, $elem ){ // もう少しスマートな書き方があるなら、 | ||
+ | return $value < $elem['id']; // 教えてほしいです。 | ||
+ | }; | ||
+ | echo " {$v}:" . ( CBinarySearch::BinarySearchT($list2,$v,$less0,$less1) ? '1' : '0' ); // 結果表示 | ||
+ | } | ||
+ | }} | ||
+ | |||
+ | サンプルコードの結果は以下です。 | ||
+ | LowerBound -7:0 -5:0 0:1 1:2 2:2 10:3 12:7 13:7 18:8 19:9 | ||
+ | UpperBound -7:0 -5:1 0:2 1:2 2:2 10:5 12:7 13:8 18:9 19:9 | ||
+ | BinarySearch -7:0 -5:1 0:1 1:0 2:0 10:1 12:0 13:1 18:1 19:0 | ||
+ | BinarySearchT -7:0 -5:1 0:1 1:0 2:0 10:1 12:0 13:1 18:1 19:0 |
(This host) = https://thinkridge.com