Введение
Хотел бы поделиться с сообществом своей реализацией пузырьковой сортировки и бинарного поиска. Проект сделал исключительно в учебных целях.
Когда меня раньше спрашивали на собеседовании об алгоритмах сортировки и реализации поиска по массивам данных — я терялся и считал, что для реализации подобных вещей надо быть как минимум талантливым отличником-олимпиадником, что это сложно-долго-малоизучено и т.п. :) Так же я находил курсы, где за несколько недель (месяцев) предлагают научить всех желающих всему-всему по алгоритмам, сортировкам, криптографии. Но ведь сейчас есть Интернет, а в нем уже все выложено и известно? Остается только поднять и изучить нужные знания и практически реализовать и закрепить приобретенные знания.
Итак, приступим к реализации самих алгоритмов. Забегая вперед скажу, что статья состоит из трех логических частей: реализация алгоритмов, тестирование написанного кода (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++) {
$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::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.
Готов выслушать ваши замечания и предложения.
Поделиться с друзьями
Комментарии (17)
volmir
24.03.2017 17:52Посмотрел таки в Википедию :) Для реализации полноценной пузырьковой сортировки надо ввести отдельную переменную, которая будет проверять, если ли перемещения элементов в текущем цикле. Если их нет — то сортировка завершена, выход из цикла.
Ruckus
24.03.2017 18:09+1Занятно, но мы проходили оба алгоритма на первом курсе института, абы не в школе (бинарный поиск так точно в школе). Что здесь нового/интересного для аудитории хабра?
volmir
24.03.2017 18:47+1Извините, я понимаю, что это уровень первого курса в ВУЗе. Вот я до этого уровня только дорос :)
Интересного для Хабра может быть то, что все делается в комплексе, например (алгоритм -> юнит-тест -> нагрузочное тестирование). Или интересным будет то, что подобные алгоритмы достаточно просты для реализации и не надо на курсы тратиться и ходить в течении нескольких месяцев. А все можно изучить самостоятельно быстрее и дешевле.
ghost404
26.03.2017 15:05Не стоит говорить за всех. Я учился на вечерке и все алгоритмы прошли мимо меня, о чем я сейчас жалею.
Lexx918
24.03.2017 18:36А почему на тестах сравнивается нативный sort с баблом? Почему не с быстрой сортировкой, например?
volmir
24.03.2017 18:43Сравнивать можно различные сортировки друг с другом. Думаю, на эту тему много кто писал более серьезные исследования. Я просто взял две сортировки (нативную на PHP и свою реализацию) и сравнил их.
impwx
24.03.2017 18:42Две последние строки в результатах тестирования поиска: массив на порядок больше, время выполнения на порядок меньше! Как так получилось?
volmir
24.03.2017 18:44Может дело в том, что я брал одно число для поиска?
Я видел это и пробовал менять код, запускать этот кусок отдельно, менять число для поиска — результат не менялся.
Сам удивлен этим фактом.
GeMir
24.03.2017 19:19Сортировки сортировками, но вот вертикальное представление массива вижу впервые :)
mwambanatanga
24.03.2017 19:40Чтобы пузырькам было, куда всплывать. При горизонтальном расположении элементов массива можно реализовать лишь пузырьковый уровень (строительный инструмент).
GeMir
25.03.2017 12:48Вы же в курсе, что у строительного уровня, расположенного на горизонтальной поверхности, пузырьки (а точнее пузырёк) будет строго по центру?
volmir
24.03.2017 19:23Я сам был удивлен в начале подобным представлением. А потом понял (прочитал) — что это как бы наглядная иллюстрация к пузырьковой сортировке: «тяжелые» (большие) числа опускаются на дно, а «легкие» (маленькие) числа всплывают наверх :)
JekaMas
Тут даже пооптимизировать можно. Например, зачем в цикле по j идти по всем элементам массива — часть массива же уже отсортирована на предыдущих шагах.
volmir
$j зависит $iterations. А $iterations постоянно уменьшается. Т.е. все о чем вы пишите — реализовано.
Спасибо за замечание. Оптимизацию можно провести эвристически :) — реализовать более продвинутые алгоритмы сортировки.