新しい値を順序付き配列に挿入するための最適なアルゴリズムをPHPで作成するタスクを得ました。 さらに、この特定のアルゴリズムが最適であることを証明することが主張されています。 これを行うには、3つのオプションを記述し、それらから最適なものを選択することが提案されました。 もちろん、最良の検索方法はバイナリであることを知っていますが、彼らがそれが最良であることを証明すると言ったので、それで、私はさらに2つを書きます。 この姿勢と将来の結果に対する自信を持って、私はコーディングを始めました。
このことから、初心者のプログラマーに本を読んでもらい、議論するための経験を積んでもらいました。
挑戦する
かなり大きな（1万要素）番号付きの配列があります。 順序を維持しながら、新しい値を最適に挿入する必要があります。
ソリューションオプション
最も簡単な方法は、最後に挿入し、組み込み関数で再ソートすることです。 しかし、最初はそうしない条件がありました。
新しい値を挿入するには何をする必要がありますか？ 開始するには、目的の位置を見つけます。 アレイのサイズを考えると、これはおそらく最もリソースを消費する部分です。 そして、この値を見つかった位置に貼り付けます。 そのため、この位置に3つの検索オプションを記述する必要があります。 実験ウサギとして、ブルートフォース、バイナリ検索、補間による検索（バイナリに似ていますが、半分に分割するのではなく、より正確に位置を推測します）。
興味がない場合は、検索機能のプログラムコードをスキップできます。
検索で検索
function insertBruteForce(&$array, $value) { function insertBruteForce(&$array, $value) { foreach($array as $position => $test) { if ($test >= $value) { break; } } insertTo($array, $position, $value); }
バイナリ検索
function insertBinary(&$array, $value) { $begin = 0; $end = count($array) - 1; while ($end - $begin > 1) { $position = round(($begin + $end) / 2); if ($array[$position] > $value) { $end = $position; } elseif ($array[$position] < $value) { $begin = $position; } else { break; } } if ($array[$position] < $value) { ++$position; } insertTo($array, $position, $value); }
正確な値を探しているのではなく、要素間の位置を探しているという事実により、やや奇妙な外観をしています。
補間による検索
function insertInterpolation(&$array, $value) { $begin = 0; $end = count($array) - 1; while ($end - $begin > 1) { $range = $array[$end] - $array[$begin]; $percentPosition = ($value - $array[$begin]) / $range; $position = $begin + round(($end - $begin) * $percentPosition); $position = min($position, $end); if($array[$position] <= $value && (!isset($array[$position+1]) || $array[$position+1] >= $value)) { break; } elseif ($array[$position] > $value) { $end = $end != $position ? $position : $position - 1; } elseif ($array[$position] < $value) { $begin = $begin != $position ? $position : $position + 1; } } if ($array[$position] < $value) { ++$position; } insertTo($array, $position, $value); }
見つかった位置に値を挿入します
まあ、それは単純なはずです（その時考えたように）。 ただし、PHPには、指定された位置に新しい値を挿入する組み込み関数はありません。値の置換のみがあります。 怖くない、値を切り取って貼り付けて貼り付けてください。 これは配列の列挙ではなく、一度行うだけで済み、組み込み関数を使用します。また、それらは迅速に機能します。
function insertTo(&$array, $position, $value) { $array = array_merge(array_slice($array, 0, $position), array($value), array_slice($array, $position)); }
後で判明したように、これは行われるべきではありません。試験結果
データのランダム配列を生成するコードをすばやく作成し、複数回実行して統計を収集するテスト。 そして、奇妙なことが起こりました。 結果は次のようになりました。
insertBruteForce：0.0088
insertBinary：0.0088
insertInterpolation：0.0087
バイナリ検索と補間の違いがないことはまだ説明できます。 しかし、単純なバストで同じ結果が得られるのはなぜですか？ 配列を増やしても、力のバランスは変わりません。
急いでプロファイリングする
通常の時間測定ではこれらの質問に答えられないことが明らかになりました。 さて、Xdebugは既にインストールされ設定されています。Xdebugはプロファイリングを有効にし、何が起こるかを確認するためだけに残っています。
そして、再び驚きが待っていました。 時間の大部分は、位置を見つけることではなく、見つかった位置に新しい要素を挿入することで占められていました。 同時に、検索自体の実行時間は結果の影響をほとんど受けませんでした。
したがって、挿入関数を書き換える必要があります。 切り取って接着する代わりに、押して貼り付けようとします。
function insertDown(&$array, $value) { $i = count($array); for ($i = $i - 1; $i >= 0 && $array[$i] < $value; --$i) { $array[$i+1] = $array[$i]; } $array[$i] = $value; }
すでに良くなっていますが、それでも正しくありません。このオプションは40％高速に動作し、メモリの消費量が少なくなります。 結果は次のとおりです。
insertBruteForce：0.0052
insertBinary：0.0053
insertInterpolation：0.0053
そして、最後の関数をもう一度見てみましょう。 彼女は何をしているの？ 彼女は目的の位置に到達するまで要素を押します。 しかし、彼女は本当に前もって位置を知る必要がありますか？
1つのボトルで検索して挿入
function insertDown(&$array, $value) { $i = count($array); for ($i = $i - 1; $i >= 0 && $array[$i] >= $value; --$i) { $array[$i+1] = $array[$i]; } $array[$i] = $value; }
結果：ただ1つの単純な関数（はい、列挙あり）と0.0049秒のテスト時間、これまでで最高の結果。
集合知の利点
翌日追加されました。ここでの議論の結果、コードの仲間と私は、編集中に犯したエラーを明らかにしました（初期バージョンをテストしましたが、実験を開始しました）。 すでに修正され、更新された結果がテキストに挿入されています。
PQRは、値挿入関数を次のものに置き換えることを提案しました。
function insertTo(&$array, $position, $value) { array_splice($array, $position, 0, $value); }
PHPには挿入関数がありますが、より汎用的な関数の一部であることがわかります。 試験結果：
insertBruteForce：0.0035
insertBinary：0.0036
insertInterpolation：0.0037
insertDown：0.0047
さらに良いが、それでも奇妙だ。
SerafimArtsは、通常の配列の代わりにSplFixedArrayクラスを使用することを提案しました。 やってみます 挿入機能は本当に「手動」で作成する必要がありました。
function insertTo($array, $position, $value) { $size = $array->count(); $array->setSize($size + 1); for ($i = $size - 1; $i >= $position; --$i) { $array[$i+1] = $array[$i]; } $array[$position] = $value; }
結果：
insertBruteForce：0.0033
insertBinary：0.0019
insertInterpolation：0.0018
insertDown：0.0026
すべてのオプションで、実行時間が短縮されました。 そして、最も興味深いのは、結果はまさに当初期待されていたものであり、私たちが大学で教えられた方法です。
エピローグ
知識と仮定は良好ですが、実際に何が起こるかを確認する必要があります。 これに適したツールは一般的に受け入れられていません。
$start = microtime(true); <- > $time = microtime(true) - $start;
およびプロファイリング。 上記の方法は有用かもしれませんが、プロファイリングは、明示的に指定した場所だけでなく、より詳細な情報を提供し、統計を収集します（これも可能です）。
コードを試すときは、自動化されたテストを書く
ように非常に注意する必要
があります。 私の場合、これは彼の編集中に犯した多くの間違いを除外します。
すべてのコメンテーターに、ヒントや提案をありがとう。