🙎🏻 👉🏿 🤘🏽 PHPでのバブルソートとバイナリ検索（トレーニング、実験） 👨‍👨‍👧‍👧 🐿️ 🧝🏾

はじめに

バブルソートとバイナリ検索の実装をコミュニティと共有したいと思います。このプロジェクトは、教育目的でのみ行われました。

インタビューでデータ配列の検索を並べ替えて実装するアルゴリズムについて尋ねられたとき、私は失われ、そのようなことを実装するには、少なくとも才能のある優秀な学生、オリンピアードである必要があると考えました。これは難しく、長く、ほとんど研究されていません、など :)また、数週間（月）にわたって、すべて、アルゴリズム、並べ替え、暗号化のすべてを望むすべての人に教えるコースを見つけました。しかし、今インターネットがあり、その中にすべてがすでにレイアウトされ、知られていますか？必要な知識を高めて研究し、獲得した知識を実際に実装および統合するだけです。

したがって、アルゴリズム自体の実装を開始します。今後は、この記事は3つの論理部分で構成されていると言います。アルゴリズムの実装、記述コードのテスト（PHPUnit）、および負荷テスト（VS言語記述コードの基本機能）の実行です。

つまり特定のシステムの開発（実際のタスクの実装）およびすべての必須段階（現在の開発の「標準」に基づく）の通過をシミュレートする方法。

バブルソート

ウィキペディアおよび専門記事では、すべてのタイプの検索が十分に詳細かつ詳細に説明されています。並べ替えはアニメーション化され、YouTubeには、並べ替えの主要な種類と配列の並べ替えプロセスの視覚的な表示を含むビデオがあります。

コードの記述を開始する前に、（実験の純度のために）そのようなソートを実装するためのコードに特に目を通しませんでしたが、問題の条件のみを読みました。コードを書き始め、テストデータをスローし、初めてスクリプトを実行して、結果を確認しました。配列が並べ替えられています。私の頭にわずかなパニックがあります！私は何を間違えましたか？間違いはどこですか？エラーはありません-配列は正しくソートされています。

数行のコード-これがバブルソートの実装全体です！？では、なぜこれが非常に難しく、誰もがアクセスできないと思いましたか？

ネタバレの下のコード

/** * * @param array $data * @return array */ public function sort(array $data) { $count_elements = count($data); $iterations = $count_elements - 1; for ($i=0; $i < $count_elements; $i++) { $changes = false; for ($j=0; $j < $iterations; $j++) { if ($data[$j] > $data[($j + 1)]) { $changes = true; list($data[$j], $data[($j + 1)]) = array($data[($j + 1)], $data[$j]); } } $iterations--; if (!$changes) { return $data; } } return $data; }

バイナリ検索

バイナリ検索の実装はもう少し難しくなりました。コードを何度か書き直し、削除して再構築しました。時間の一部は、テストデータの準備と、検索が正しく機能するさまざまな状況の確認に費やされました。

しかし、すべてがうまくいきました。私が現在知らない唯一のことは、「平均インデックスを計算する際の整数オーバーフロー」です:)

ネタバレの下のコード

  /** * * @param int $element * @return mixed */ public function search(int $element, array $data) { $begin = 0; $end = count($data) - 1; $prev_begin = $begin; $prev_end = $end; while (true) { $position = round(($begin + $end) / 2); if (isset($data[$position])) { if ($data[$position] == $element) { return $position; } if ($data[$position] > $element) { $end = floor(($begin + $end) / 2); } elseif ($data[$position] < $element) { $begin = ceil(($begin + $end) / 2); } } if ($prev_begin == $begin && $prev_end == $end) { return false; } $prev_begin = $begin; $prev_end = $end; } }

コードテスト

クラスコードは個別のファイルに分けられます。コードを単体テストでカバーし、実装に変更を加えた場合、基本機能の機能を迅速に再確認できるのは論理的です。

バイナリ検索のテストでは、次の状況が考慮されました。

入力に0/1/2要素の配列を渡します
最初/最後のアイテム
配列に要素がありません
配列外の要素へのアクセス

ネタバレの下のコード

 class BinarySearchTest extends PHPUnit_Framework_TestCase { /** * * @var BinarySearch */ public $binary; /** * * @var array */ public $empty_data = []; /** * * @var array */ public $one_element = [1]; /** * * @var array */ public $two_elements = [1,2]; /** * * @var array */ public $many_elements = [-189, -55, -34, -9, 0, 1, 6, 9, 10, 12, 25, 45, 67, 287, 633, 673, 783, 942]; public function setUp() { $this->binary = new BinarySearch(); } public function tearDown() { } public function testEmptyData() { $result = $this->binary->search(1, $this->empty_data); $this->assertEquals($result, false); } public function testOneElement() { $result = $this->binary->search(1, $this->one_element); $this->assertEquals($result, 0); $result = $this->binary->search(2, $this->one_element); $this->assertEquals($result, false); } public function testTwoElements() { $result = $this->binary->search(1, $this->two_elements); $this->assertEquals($result, 0); $result = $this->binary->search(2, $this->two_elements); $this->assertEquals($result, 1); } public function testManyElements() { $result = $this->binary->search(-34, $this->many_elements); $this->assertEquals($result, 2); $result = $this->binary->search(-1, $this->many_elements); $this->assertEquals($result, false); $result = $this->binary->search(0, $this->many_elements); $this->assertEquals($result, 4); $result = $this->binary->search(11, $this->many_elements); $this->assertEquals($result, false); $result = $this->binary->search(25, $this->many_elements); $this->assertEquals($result, 10); $result = $this->binary->search(673, $this->many_elements); $this->assertEquals($result, 15); } public function testLastFirstElement() { $result = $this->binary->search(-189, $this->many_elements); $this->assertEquals($result, 0); $result = $this->binary->search(942, $this->many_elements); $this->assertEquals($result, 17); } public function testOutsideData() { $result = $this->binary->search(-479, $this->many_elements); $this->assertEquals($result, false); $result = $this->binary->search(1294, $this->many_elements); $this->assertEquals($result, false); } }

バブルのソートは非常に簡単にテストされます-結果を比較し、正しいデータ配列を期待します。

ネタバレの下のコード

 class BubbleSortTest extends PHPUnit_Framework_TestCase { /** * * @var BubbleSort */ public $bubble; /** * * @var array */ public $unsorted_data = [2, 0, -1, 3, 1]; /** * * @var array */ public $sorted_data = [-1, 0, 1, 2, 3]; public function setUp() { $this->bubble = new BubbleSort(); } public function tearDown() { } public function testSort() { $sorted_data = $this->bubble->sort($this->unsorted_data); $this->assertInternalType('array', $sorted_data); $this->assertEquals($sorted_data, $this->sorted_data); } }

負荷試験

テストファイルコード

 set_time_limit(0); include 'src/BinarySearch.php'; include 'src/BubbleSort.php'; include 'lib/Benchmark.php'; $benchmark = new Benchmark(); $array_100 = []; $array_1000 = []; $array_10000 = []; $array_100000 = []; $array_1000000 = []; for ($i=0; $i<100; $i++) { $array_100[] = mt_rand(0, 100); } for ($i=0; $i<1000; $i++) { $array_1000[] = mt_rand(0, 1000); } for ($i=0; $i<10000; $i++) { $array_10000[] = mt_rand(0, 10000); } for ($i=0; $i<100000; $i++) { $array_100000[] = mt_rand(0, 100000); } for ($i=0; $i<1000000; $i++) { $array_100000[] = mt_rand(0, 1000000); } $array_100_copy = $array_100; $array_1000_copy = $array_1000; $array_10000_copy = $array_10000; /** * Test bubble sort */ $bubble = new BubbleSort(); $benchmark->mark('begin_sort_100'); sort($array_100); $sort_100 = $benchmark->elapsedTime('begin_sort_100', 'end_sort_100'); $benchmark->mark('begin_sort_100_copy'); $bubble->sort($array_100_copy); $sort_100_copy = $benchmark->elapsedTime('begin_sort_100_copy', 'end_sort_100_copy'); $benchmark->mark('begin_sort_1000'); sort($array_1000); $sort_1000 = $benchmark->elapsedTime('begin_sort_1000', 'end_sort_1000'); $benchmark->mark('begin_sort_1000_copy'); $bubble->sort($array_1000_copy); $sort_1000_copy = $benchmark->elapsedTime('begin_sort_1000_copy', 'end_sort_1000_copy'); $benchmark->mark('begin_sort_10000'); sort($array_10000); $sort_10000 = $benchmark->elapsedTime('begin_sort_10000', 'end_sort_10000'); $benchmark->mark('begin_sort_10000_copy'); $bubble->sort($array_10000_copy); $sort_10000_copy = $benchmark->elapsedTime('begin_sort_10000_copy', 'end_sort_10000_copy'); /** * Test binary search */ $binary = new BinarySearch(); sort($array_100); sort($array_1000); sort($array_10000); sort($array_100000); sort($array_1000000); reset($array_100); reset($array_1000); reset($array_10000); reset($array_100000); reset($array_1000000); $benchmark->mark('begin_search_100'); $position = array_search(50, $array_100); $search_100 = $benchmark->elapsedTime('begin_search_100', 'end_search_100', 6); $benchmark->mark('begin_search_100_in_array'); $position = in_array(50, $array_100); $search_100_in_array = $benchmark->elapsedTime('begin_search_100_in_array', 'end_search_100_in_array', 6); $benchmark->mark('begin_search_100_second'); $position = $binary->search(50, $array_100); $search_100_second = $benchmark->elapsedTime('begin_search_100_second', 'end_search_100_second', 6); $benchmark->mark('begin_search_1000'); $position = array_search(50, $array_1000); $search_1000 = $benchmark->elapsedTime('begin_search_1000', 'end_search_1000', 6); $benchmark->mark('begin_search_1000_in_array'); $position = in_array(50, $array_1000); $search_1000_in_array = $benchmark->elapsedTime('begin_search_1000_in_array', 'end_search_1000_in_array', 6); $benchmark->mark('begin_search_1000_second'); $position = $binary->search(50, $array_1000); $search_1000_second = $benchmark->elapsedTime('begin_search_1000_second', 'end_search_1000_second', 6); $benchmark->mark('begin_search_10000'); $position = array_search(50, $array_10000); $search_10000 = $benchmark->elapsedTime('begin_search_10000', 'end_search_10000', 6); $benchmark->mark('begin_search_10000_in_array'); $position = in_array(50, $array_10000); $search_10000_in_array = $benchmark->elapsedTime('begin_search_10000_in_array', 'end_search_10000_in_array', 6); $benchmark->mark('begin_search_10000_second'); $position = $binary->search(50, $array_10000); $search_10000_second = $benchmark->elapsedTime('begin_search_10000_second', 'end_search_10000_second', 6); $benchmark->mark('begin_search_100000'); $position = array_search(50, $array_100000); $search_100000 = $benchmark->elapsedTime('begin_search_100000', 'end_search_100000', 6); $benchmark->mark('begin_search_100000_in_array'); $position = in_array(50, $array_100000); $search_100000_in_array = $benchmark->elapsedTime('begin_search_100000_in_array', 'end_search_100000_in_array', 6); $benchmark->mark('begin_search_100000_second'); $position = $binary->search(50, $array_100000); $search_100000_second = $benchmark->elapsedTime('begin_search_100000_second', 'end_search_100000_second', 6); $benchmark->mark('begin_search_1000000'); $position = array_search(50, $array_1000000); $search_1000000 = $benchmark->elapsedTime('begin_search_1000000', 'end_search_1000000', 6); $benchmark->mark('begin_search_1000000_in_array'); $position = in_array(50, $array_1000000); $search_1000000_in_array = $benchmark->elapsedTime('begin_search_1000000_in_array', 'end_search_1000000_in_array', 6); $benchmark->mark('begin_search_1000000_second'); $position = $binary->search(50, $array_1000000); $search_1000000_second = $benchmark->elapsedTime('begin_search_1000000_second', 'end_search_1000000_second', 6); ?> <h3>,  </h3> <table> <thead> <tr> <th> </th> <th> PHP::sort() <br>. </th> <th> BubbleSort()->sort() <br>. </th> </tr> </thead> <tbody> <tr> <td>   100  </td> <td><?=$sort_100?></td> <td><?=$sort_100_copy?></td> </tr> <tr> <td>   1000  </td> <td><?=$sort_1000?></td> <td><?=$sort_1000_copy?></td> </tr> <tr> <td>   10000  </td> <td><?=$sort_10000?></td> <td><?=$sort_10000_copy?></td> </tr> </tbody> </table> <h3>  ,  </h3> <table> <thead> <tr> <th> </th> <th> PHP::array_search() <br>. </th> <th> PHP::in_array() <br>. </th> <th> BinarySearch()->search() <br>. </th> </tr> </thead> <tbody> <tr> <td>   100  </td> <td><?=$search_100?></td> <td><?=$search_100_in_array?></td> <td><?=$search_100_second?></td> </tr> <tr> <td>   1000  </td> <td><?=$search_1000?></td> <td><?=$search_1000_in_array?></td> <td><?=$search_1000_second?></td> </tr> <tr> <td>   10000  </td> <td><?=$search_10000?></td> <td><?=$search_10000_in_array?></td> <td><?=$search_10000_second?></td> </tr> <tr> <td>   100000  </td> <td><?=$search_100000?></td> <td><?=$search_100000_in_array?></td> <td><?=$search_100000_second?></td> </tr> <tr> <td>   1000000  </td> <td><?=$search_1000000?></td> <td><?=$search_1000000_in_array?></td> <td><?=$search_1000000_second?></td> </tr> </tbody> </table>

選別、ストレステスト

	PHP ::ソート（）秒	BubbleSort（）->ソート（）秒
100要素の配列	0.0000	0.0023
1000要素の配列	0.0002	0.2305
10,000個の要素の配列	0.0031	23.1601

アイテムの位置の検索、ストレステスト

	PHP :: array_search（）秒	PHP :: in_array（）秒	BinarySearch（）->検索（）秒
100要素の配列	0.000012	0.000004	0.000032
1000要素の配列	0.000003	0.000003	0.000026
10,000個の要素の配列	0.000004	0.000003	0.000034
100,000要素の配列	0.000005	0.000003	0.000046
1,000,000要素の配列	0.000003	0.000003	0.000005

テスト結果からの結論：

PHPに組み込まれているソートは、著者が書いたものよりも3〜4桁効率的です。そして、これはかなり小さなデータ配列で行われます（大きな配列では違いが大きくなります）。
驚くべきことに、バイナリ検索では、要素の位置を見つける速度が桁違いに低いことが示されました（言語に組み込まれた関数と比較して）。バイナリ検索の有効性に関する入力データの増加はほとんど効果がありません。

おわりに

このコードを作成するときに使用したアプローチ、考え、アイデアが人々に役立つか、議論の基礎となり、より最適なソリューションを見つけることができれば嬉しいです。

私は、多くの開発者が成長してスペシャリストになる段階を長い間経験してきたことを理解しています。同様のタスクは、ほぼ間違いなく大学の実験室プログラミングプログラムの一部です。

この記事のすべてのコードはGitHubに投稿されています。

コメントや提案を聞く準備ができています。

PHPでのバブルソートとバイナリ検索（トレーニング、実験）

はじめに

バブルソート

バイナリ検索

コードテスト

負荷試験

おわりに

More articles: