Поищите в Википедии Bogosort, Slowsort или Stooge sort и приготовьтесь войти в глубокую кроличью нору, которая ведет в странный мир извращенно ужасных алгоритмов сортировки.

Эти три относительно простых алгоритма, используемые в основном для иллюстративных целей на уроках информатики, - только начало. Странный алгоритм, известный как Bogobogosort, уже много лет крутится в далеких уголках интернет-форумов (возможно, изобретен австралийским физиком Дэвидом Морган-Маром, хотя его происхождение неясно). Ожидается, что с ужасающей временной сложностью O (n! ⁿ⁻ᵏ) Богобогосорт будет продолжать сортировку до тепловой смерти вселенной для любого списка с длиной в младшие двузначные числа.

Богобогосорт реализуется путем копирования несортированного списка с последующей рекурсивной проверкой n - 1 подмножества этого списка, чтобы увидеть, больше ли последний элемент подмножества, чем первый элемент. В противном случае перетасовывается вся копия списка, и процесс начинается заново. Дэвид Морган-Мар описывает следующие шаги:

1. Сделайте копию списка номеров.

2. Отсортируйте первые n -1 элементов копии с помощью bogobogosort.

3. Убедитесь, что n -й элемент отсортированной копии больше, чем самый высокий элемент первых n -1 элементов. Если это так, копия теперь отсортирована, иначе измените порядок элементов копии в случайном порядке и перейдите к шагу 2.

4. Проверьте, находится ли копия в том же порядке, что и исходный список.

Дэвид сообщает, что пытался отсортировать список всего из 7 целых чисел за ночь с помощью Bogobogosort и, наконец, отказался и ему пришлось перезагрузить компьютер.

Однако варианты Bogosort - это только начало. Статья Мигеля Лермы 2007 года показывает, что алгоритм сортировки под названием Worstsort может быть произвольно неэффективным в соответствии с возрастающей вычислимой функцией f. То есть, мы можем сделать алгоритм сортировки настолько неэффективным, насколько захотим, даже соблюдая ограничение, согласно которому каждая часть алгоритма должна быть полезной (то есть без итераций или задержек, добавленных исключительно ради извращенности).

Worstsort теоретически может отсортировать любой список с учетом бесконечного пространства и времени, но при любой реализации Worstsort всегда возможна еще менее эффективная версия!

В чем смысл?

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

Рассмотрим проблему, которая веками ставила ученых в тупик: видовой противовес. Кодированный австрийским композитором 18-го века Иоганном Йозефом Фуксом (среди прочих) видовой контрапункт представляет собой набор строгих правил, определяющих, как музыкальные ноты должны двигаться относительно друг друга (это было задолго до того, как были разработаны современные символы аккордов). Даже сегодня ученики учатся писать контрапункт видов в качестве педагогического упражнения в музыкальной школе.

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

Я не буду утомлять вас полным списком правил, но они содержат подробные ограничения на то, как далеко могут быть друг от друга ноты, а также где и когда в мелодии могут встречаться определенные диссонирующие или согласные аккорды.

Написать решение методом перебора довольно просто. Учитывая начальную точку, вы просто просматриваете набор возможных следующих заметок, проверяете, не нарушает ли каждый вариант одно из правил, и выбираете решение из набора допустимых ходов. Это работает для двух голосов, может быть, даже для трех голосов, но если мы хотим составить контрапункт из четырех, пяти или более голосов, набор возможных ходов быстро превосходит практичность. Это алгоритм с временной сложностью O (n²).

В течение сотен лет студенты-музыкальные студенты учились делать контрапункт более или менее таким образом, в основном пробуя серию нот, проверяя, не нарушают ли они какое-либо правило вида, а затем возвращаясь к более раннему моменту, когда они застревали. Это немного похоже на судоку (и как студент-музыкальный в прошлой жизни, я могу сказать вам, что это часто очень расстраивает!).

Затем, в 1956 году, Леджарен Хиллер, исследователь химии и композитор из Университета Иллинойса в Урбана-Шампейн, увидел определенные параллели между музыкой и научными вычислениями, и у него возникла идея запрограммировать компьютер ILLIAC IV для написания контрапункта.

Результатом первого компьютерного контрапункта стала Illiac Suite для струнного квартета, которую Леярен Хиллер написал в сотрудничестве с Леонардом Айзексоном. С Illiac Suite мир, возможно, познакомился с новым взглядом на творчество.

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

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

Красота в неэффективной Вселенной

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

Возможно, самая ирония в крайне неэффективных алгоритмах сортировки заключается в том, что лучший алгоритм временной сложности может вообще не реализовываться на компьютерах! Рекорд по самой быстрой сортировке по временной сложности на самом деле может быть установлен причудливым естественным алгоритмом сортировки, называемым Bead Sort, буквально просто падающими бусинками на счеты. При определенных условиях Bead Sort теоретически имеет временную сложность O (1). Самые быстрые алгоритмы сортировки сравнения, реализованные на цифровых компьютерах, имеют временную сложность около O (n log n). Я призываю вас найти более неприятный сбой в матрице ...