Введение
Хотел бы поделиться с сообществом своей реализацией пузырьковой сортировки и бинарного поиска. Проект сделал исключительно в учебных целях.
Когда меня раньше спрашивали на собеседовании об алгоритмах сортировки и реализации поиска по массивам данных — я терялся и считал, что для реализации подобных вещей надо быть как минимум талантливым отличником-олимпиадником, что это сложно-долго-малоизучено и т.п. 🙂 Так же я находил курсы, где за несколько недель (месяцев) предлагают научить всех желающих всему-всему по алгоритмам, сортировкам, криптографии. Но ведь сейчас есть Интернет, а в нем уже все выложено и известно? Остается только поднять и изучить нужные знания и практически реализовать и закрепить приобретенные знания.
Итак, приступим к реализации самих алгоритмов. Забегая вперед скажу, что статья состоит из трех логических частей: реализация алгоритмов, тестирование написанного кода (PHPUnit) и проведение нагрузочных тестов (базовые функции языка VS написанный код).
Т.е. как бы имитируется разработка некой системы (выполнение практической задачи) и прохождение по всем обязательным этапам (исходя из существующих на сейчас «стандартов» разработки).
Пузырьковая сортировка
НА Википедии и в профильных статьях довольно подробно и детально описаны все виды поиска. Сортировки анимированны, а на Ютубе есть видео с основными видами сортировок и наглядным отображением самого процесса упорядочивания массивов.
Перед началом написания кода я специально не вглядывался в код реализаций такой сортировки (для чистоты эксперимента), а лишь читал условия задачи. Начал писать код, подбросил тестовые данные, запустил скрипт в первый раз и смотрю на результат: массив отсортирован! В голове легкая паника! Что я сделал не так? Где ошибка? Ошибки нет — массив отсортирован верно. Несколько строк кода — это и есть вся реализация пузырьковой сортировки?! Почему же я раньше считал, что это очень сложно и доступно не всем?
/** * * @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++) { for ($j=0; $j < $iterations; $j++) { if ($data[$j] > $data[($j + 1)]) { list($data[$j], $data[($j + 1)]) = array($data[($j + 1)], $data[$j]); } } $iterations--; } 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::sort() сек. |
BubbleSort()->sort() сек. |
|
|---|---|---|
| Массив из 100 элементов | 0.0000 | 0.0023 |
| Массив из 1000 элементов | 0.0002 | 0.2305 |
| Массив из 10000 элементов | 0.0031 | 23.1601 |
Поиск позиции элемента, нагрузочные тесты
| PHP::array_search() сек. |
PHP::in_array() сек. |
BinarySearch()->search() сек. |
|
|---|---|---|---|
| Массив из 100 элементов | 0.000012 | 0.000004 | 0.000032 |
| Массив из 1000 элементов | 0.000003 | 0.000003 | 0.000026 |
| Массив из 10000 элементов | 0.000004 | 0.000003 | 0.000034 |
| Массив из 100000 элементов | 0.000005 | 0.000003 | 0.000046 |
| Массив из 1000000 элементов | 0.000003 | 0.000003 | 0.000005 |
Выводы по результатам тестирования:
- Встроенная в PHP сортировка на три-четыре порядка эффективнее, нежели написанная автором. И это на достаточно небольших массивах данных (на больших массивах разница будет увеличиваться).
- Бинарный поиска, на удивление, показал всего лишь на порядок меньшую скорость поиска позиции элемента (по сравненнию с встроенными в язык функциями). Увеличение объемов входных данных на эффективность бинарного поиска оказывает малое влияние.
Заключение
Буду рад, если подходы, мысли и идеи, которые я применял при написании этого кода пригодятся людям или послужат основой для обсуждения и нахождения более оптимальных решений.
Понимаю, что многие разработчики уже давно прошли подобные этапы взросления и становления как специалисты. Подобные задачи почти наверняка входят в университетскую программу лабораторных работ по программированию.
Весь код, приведенный в этой статье выложен на GitHub: https://github.com/volmir/sort-search
Буду рад выслушать ваши замечания и предложения.
ссылка на оригинал статьи https://habrahabr.ru/post/324792/
Добавить комментарий