Сортировка

Важно понимать, что не все рабочие нагрузки, привязанные к ЦП, подходят для конкурентной модели. Это в первую очередь верно, когда очень дорого либо разбивать работу, либо объединять все результаты. Также надо учитывать оверхед от самой горутины, стэк которой занимает от 4kb. Пример этого можно увидеть в алгоритме сортировки, называемом пузырьковой сортировкой. Посмотри на следующий код, который реализует сортировку пузырьком в Go.

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

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

Пришло время поработать с кодом!

В листинге выше представлена функция bubbleSortConcurrent, которая является конкурентной версией функции bubbleSort. Он использует несколько горутин для одновременной сортировки частей списка. Однако у тебя остается список отсортированных значений по частям. Учитывая список из 36 чисел, разделенных на группы по 12, это будет результирующий список, если весь список не будет отсортирован еще раз в строке 25.

Поскольку природа пузырьковой сортировки заключается в пролистывании списка, вызов в bubbleSort строке 25 сведет на нет любые потенциальные выгоды от использования конкурентной модели. Пузырьковая сортировка не дает прироста производительности за счет использования concurrency.