Вторник Flutter Benchmark: падение короля пузырьковой сортировки

*** Внимание, спойлер: сортировка вставками побеждает, но есть одна загвоздка***

Мы продолжаем нашу регулярную серию Проверка очевидных вещей по вторникам. На этот раз, продолжая циклы (ссылка на мою предыдущую статью»👈), мы проверим эффективность различных алгоритмов сортировки во Flutter.

Я избавлю вас от утомительного вступления с описанием каждого алгоритма, так как вам все станет ясно в конце статьи, хорошо? Итак, для сегодняшних испытуемых имеем:

• Пузырьковая сортировка
• Сортировка вставками
• Сортировка слиянием
• Быстрая сортировка
• Быстрая сортировка со случайным выбором сводной точки
• Встроенная сортировка методом

Вероятно, вы сами написали половину этих алгоритмов в старшей школе, а некоторые даже в детском саду. Тем не менее, фундамент есть фундамент.

Давай, пошли

Как обычно, мы начнем с создания файла _test в папке test, но вместо модульных тестов у нас будут бенчмарки (я такой дальновидный):

Полезный совет: из приведенного выше кода вы можете использовать пузырьковую сортировку или сортировку выбором для своей лабораторной работы вместо того, чтобы гуглить или задавать вопросы на Stack Overflow. Совершенно бесплатно. Спасибо.

В начале фрагмента кода создается 7 массивов — по одному для каждого из алгоритмов сортировки и дополнительный для встроенного метода сортировки в Dart.

Затем вызывается каждый алгоритм сортировки и измеряется время его выполнения с помощью функции syncBenchmark() из библиотеки benchmarking. Результаты измерений выводятся на консоль методом report().

Определим функции для реализации каждого из алгоритмов сортировки: bubbleSort(), insertionSort(), selectionSort(), mergeSort(), quickSort() и quickSortRandomPivot(). Каждая функция принимает массив целых чисел и сортирует его в соответствии с соответствующим алгоритмом сортировки.

merge() — вспомогательная функция для сортировки слиянием (mergeSort()). Он объединяет два отсортированных подмассива в один отсортированный массив.

Каждая функция принимает необязательные параметры left и right, которые определяют границы сортируемого массива. Если эти параметры не указаны, функция сортирует весь массив.

Уф, сколько строк кода. Запустим тест и посмотрим на результат:

Боже мой, что я вижу. Сортировка вставками разгромила всех конкурентов, она в 20–200 раз быстрее, Карл. Я просмотрю весь свой код, попивая лавандовый латте 🤙.

Не забывайте подписываться, ставить лайки и оставлять комментарии…

Подождите, что?

TL;DR

К сожалению, многие разработчики иногда забывают о такой важной вещи, как временная сложность алгоритмов, что может привести к созданию медленного или неэффективного кода или к ложным выводам о том, как работает их код, как мы можем видеть на наш случай.

Временная сложность алгоритма — это мера количества времени, необходимого для выполнения алгоритма, в зависимости от размера входных данных. Он оценивает, насколько быстро алгоритм будет работать при увеличении размера входных данных, таких как количество элементов в списке или длина строки.

Хорошо, я понимаю. Я погуглю эту штуку и выберу алгоритм на ее основе. Это нормально?

Не совсем. Есть еще один момент, о котором нельзя забывать — наилучший и наихудший сценарии, то есть конфигурации входных данных, при которых алгоритм работает либо хуже, либо лучше, чем в других случаях.

Да, эти вещи неоднородны.

Наилучший случай для алгоритма — это когда он работает наиболее эффективно, т. е. когда его временная сложность минимальна. Например, для алгоритма поиска в отсортированном массиве наилучший случай имеет место, когда искомый элемент находится в середине массива, и временная сложность в этом случае равна O(1).

Худший случай для алгоритма — это когда он работает наименее эффективно, т. е. когда его временная сложность максимальна. Например, для алгоритма поиска в несортированном массиве наихудший случай имеет место, когда искомый элемент находится в конце массива, и алгоритм должен будет проверять каждый элемент массива, что приводит к временной сложности O( н).

Понимание наилучшего и наихудшего сценариев необходимо при выборе алгоритма для решения конкретной задачи. Алгоритм с наихудшей временной сложностью O(n²) может быть применим для решения задачи, если наихудший сценарий почти никогда не встречается в реальной жизни, но может быть неэффективным, если он используется для обработки больших объемов данных.

Итак, что мы имеем с нашими алгоритмами?

• Пузырьковая сортировка: временная сложность — O(n²). Лучше использовать для небольших массивов, когда не требуется высокая производительность или когда массив уже почти отсортирован.
• Сортировка вставками: временная сложность — O(n²), в лучшем случае — O(n). Хорошо работает для небольших и частично отсортированных массивов.
• Сортировка выбором: временная сложность — O(n²). Используется редко, в основном для обучения или на очень маленьких массивах.
• Сортировка слиянием: временная сложность — O(n log n). Хорошо работает с большими массивами, но требует дополнительной памяти для хранения временных массивов.
• Быстрая сортировка: средняя временная сложность — O(n log n), худший случай — O(n²). Один из наиболее широко используемых алгоритмов сортировки, поскольку он хорошо работает с большими массивами и обычно быстрее, чем сортировка слиянием. Однако для наихудших входных данных (например, уже отсортированных массивов) производительность может значительно ухудшиться.
• Быстрая сортировка со случайным выбором опорной точки: средняя временная сложность — O(n log n), худший случай — O(n²). Подходит для больших массивов, аналогична быстрой сортировке, но обычно показывает более стабильную работу на разных входных данных из-за случайного выбора опорных элементов.
• Встроенный метод сортировки: обычно используется быстрая сортировка или сортировка слиянием в зависимости от реализации. Производительность может варьироваться в зависимости от конкретной реализации, но в целом его лучше использовать, когда не требуется специальной настройки сортировки и нужно добиться максимальной производительности.

Мы можем наблюдать реализация встроенного метода sort в Dart, который включает в себя следующий комментарий относительно алгоритма сортировки:

/**
 * Dual-Pivot Quicksort algorithm.
 *
 * This class implements the dual-pivot quicksort algorithm as presented in
 * Vladimir Yaroslavskiy's paper.
 *
 * Some improvements have been copied from Android's implementation.
 */

Быстрая сортировка? Я не впечатлен.

Вместо заключения

Хорошо, сортировка вставками имеет лучшую временную сложность в лучшем случае, когда массив уже отсортирован. Если массив частично отсортирован или уже отсортирован, сортировка вставками может работать значительно быстрее, чем пузырьковая сортировка, сортировка выбором, сортировка слиянием и даже быстрая сортировка. В этом случае генерация случайных чисел, вероятно, привела к частично отсортированному массиву, поэтому сортировка вставками работает намного быстрее, чем другие алгоритмы.

Однако в худшем случае, когда массив уже отсортирован в обратном порядке, сортировка вставками будет иметь квадратичную временную сложность и будет медленнее, чем другие алгоритмы. Поэтому для общего использования лучше выбирать другие алгоритмы, такие как Quick Sort или Merge Sort, которые во всех случаях имеют более равномерную временную сложность.

Да. Обычно лучше всего использовать встроенный метод сортировки, поскольку он уже оптимизирован для повышения производительности и обрабатывает различные входные данные. В Dart метод sort — хороший выбор для сортировки массивов.

А теперь подпишитесь, чтобы не пропустить новые статьи!

Вам также могут быть интересны другие мои тесты:

Технический персонал:

Или целая серия статей о работе с REST API (это настоящее дерьмо как Санта-Барбара):