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

/** * * @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; } } 

 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>