技術系備忘録​/PHP​/二分探索(binary search) をテンプレートにして作成 :: シンクリッジ

開始行:
#contents PHP には何故か二分探索(バイナリサーチ)が標準で用意されて... PHPにとってあまり重要ではないのか？言語的に別の手段で解決... -配列内にお目当ての要素があるか否かだけの関数（いわゆる C... 最初に現れた指定値以上の要素の位置を返す関数（ std::lower... 最初に現れた指定値を超えた要素の位置を返す関数（ std::upp... きっと、ありがたみ的には binary_search より lower_bound、... -単純な配列にしか使えないんじゃ使い勝手が悪いので、比較関... -配列内に同じ値(要素)がダブって存在していても、正しくソー... もちろん、正しくソートされてない配列の場合の結果は不定で... ***クラス定義 #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, $func... { $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, $func... { $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, $fu... { $first = self::LowerBoundT($list, $value, $funcLess0 ); return $first>=count($list) ? false : ! $funcLess1( $va... } } }} ***サンプルコード #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) ... } // 自前比較関数版 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... } }} サンプルコードの結果は以下です。 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 1... BinarySearchT -7:0 -5:1 0:1 1:0 2:0 10:1 12:0 13:1 18:1 ...

終了行:
#contents PHP には何故か二分探索(バイナリサーチ)が標準で用意されて... PHPにとってあまり重要ではないのか？言語的に別の手段で解決... -配列内にお目当ての要素があるか否かだけの関数（いわゆる C... 最初に現れた指定値以上の要素の位置を返す関数（ std::lower... 最初に現れた指定値を超えた要素の位置を返す関数（ std::upp... きっと、ありがたみ的には binary_search より lower_bound、... -単純な配列にしか使えないんじゃ使い勝手が悪いので、比較関... -配列内に同じ値(要素)がダブって存在していても、正しくソー... もちろん、正しくソートされてない配列の場合の結果は不定で... ***クラス定義 #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, $func... { $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, $func... { $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, $fu... { $first = self::LowerBoundT($list, $value, $funcLess0 ); return $first>=count($list) ? false : ! $funcLess1( $va... } } }} ***サンプルコード #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) ... } // 自前比較関数版 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... } }} サンプルコードの結果は以下です。 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 1... BinarySearchT -7:0 -5:1 0:1 1:0 2:0 10:1 12:0 13:1 18:1 ...

ページ名: