Bogosort

Сегодня на собеседовании (я всё ещё ищу пайтонистов, ау) всплыли алгоритмы сортировки и я решил немного почитать на эту тему. Оказывается есть смешной алгоритм сортировки Bogosort, который на практике не применяется, а служит только иллюстративным целям:

Bogosort (также рандомная сортировка, сортировка ружья или обезьянья сортировка) является очень неэффективным алгоритмом сортировки. Её используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если bogosort использовать для сортировки колоды карт, то сначала в алгоритме нужно проверить, лежат ли все карты по порядку, и если не лежат, то подбросить колоду в воздух, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода.

Я, для интереса, написал его на Пайтоне и поразвлекался с запускам на разных данных. Вот код, если интересно:

from random import shuffle
from itertools import izip, islice

def bogosorted(arr):
    for x, y in izip(islice(arr, 1, None), islice(arr, 0, len(arr) - 1)):
         if y > x: return False

    return True

def bogosort(arr):
    while arr and not bogosorted(arr):
        shuffle(arr)

    return arr


print bogosort([1, 1, 3, 2, 2, 2])
Поделиться
Отправить
27 комментариев
zero_sharp 2011

Не работает на пустых массивах.

Евгений Степанищев (bolknote.ru) 2011

Комментарий для zero_sharp:

Ох, точно. Как переписал на islice, перестало. Сейчас скорректирую, спасибо!

gogis 2011

Я бы не задумываясь писал бы в цикле что-то вроде

if current_val < last_var return false
last_var = current_val

Я вот хоть убей не понимаю, зачем ты сделал это через izip. Другое мышление?

gogis 2011

Или эээ... максимальная неэффективность?

zero_sharp 2011

Комментарий для Евгения Степанищева:

def bogosort(arr):
    while not all(x <= y for x, y in izip(arr, islice(arr, 1, None))):
        shuffle(arr)
    return arr

twitter.com/Flash_it 2011

Зря вы так скептически относитесь к этому алгоритму. Такие вещи сейчас довольно активно применяют в областях AI и data mining, когда данные имеют огромную размерность и классические алгоритмы будут работать слишком долго, или когда классические алгоритмы не могут быть применены, а какие-то специфические работают за полиномиальное время, например.

Вот можно почитать http://en.wikipedia.org/wiki/Randomized_algorithm

Евгений Степанищев (bolknote.ru) 2011

Комментарий для gogis:

Я вот хоть убей не понимаю, зачем ты сделал это через izip. Другое мышление?
Или эээ… максимальная неэффективность?

Мне совершенно непонятно что тут может быть неясно. Там итераторы работают. Это позволяет увеличить скорость на больших массивах.

Евгений Степанищев (bolknote.ru) 2011

Комментарий для zero_sharp:

while not all(x <= y for x, y in izip(arr, islice(arr, 1, None))):

Можно сразу выкинуть islice и izip. Функция all убъёт всю пользу итераторов.

Евгений Степанищев (bolknote.ru) 2011

Комментарий для http://twitter.com/Flash_it:

Спасибо, посмотрю! А то мне совершенно неясна польза рандомизации на этой задачи (кроме иллюстративной, вроде, «можно так, но не нужно»), может эта статья прояснит.

Мохов Олег (o-mokhov.ya.ru) 2011

Помню на asm были чуваки, у которых таким образом все задачки решались. =)

Евгений Степанищев (bolknote.ru) 2011

Комментарий для o-mokhov.ya.ru:

Где? Не понял в каком значении ты слово asm используешь.

gogis 2011

Мне совершенно непонятно что тут может быть неясно. Там итераторы работают. Это позволяет увеличить скорость на больших массивах.

Я не пишу на питоне и не пользовался итераторами(чтение статьи в википедии не в счет), но мне совершенно непонятно, почему это быстрее, чем просто пробежаться по исходному массиву в цикле. Потому и не ясно.

Евгений Степанищев (bolknote.ru) 2011

Комментарий для gogis:

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

У меня как-то смешались в сознании два комментария, ваш и zero_sharp’a, каюсь.

Мне нравится использовать итераторы. Писать «влоб» такие задачки — скучно, поэтому, чтобы хоть как-то разнообразить, я использую итераторы. Мой первый вариант был примерно похож на ваш.

twitter.com/Flash_it 2011

Комментарий для Евгения Степанищева:

Дело собственно в том, что для больших объёмов данных часто бывает возможно оценить степень упорядоченности данных довольно быстро, но не отсортировать их. Поэтому делают какое-то заданное число итераций данной «сортировки» и выбирают наилучший. AI и data mining ведь в принципе пока не дают никаких точных результатов, многие алгоритмы строятся на опредлённых условиях и допущениях, поэтому данный подход вполне оправдан.

andr (andr.mp) 2011

Было бы интересно ещё посчитать количество итераций.

Евгений Степанищев (bolknote.ru) 2011

Комментарий для andr.mp:

Количество итераций в каком случае?

andr (andr.mp) 2011

Комментарий для Евгения Степанищева:

Сколько раз надо шаффлить массив, пока он не отсортируется таким образом.

Евгений Степанищев (bolknote.ru) 2011

Комментарий для andr.mp:

По-разному, на 10 запусков: 6, 49, 20, 6, 110, 35, 39, 85, 133, 17.

Vladimir Moskva (fulc.ru) 2011

Комментарий для Евгения Степанищева:

Функция all убъёт всю пользу итераторов.

Каким образом?

Евгений Степанищев (bolknote.ru) 2011

Комментарий для fulc.ru:

all не умеет с ними работать. Просто преобразует всё это дело в list.

Vladimir Moskva (fulc.ru) 2011

Комментарий для Евгения Степанищева:

А если итератор бесконечный? Или конечный, но очень большой?

И зачем преобразовывать итератор в list, чтобы по нему опять итерироваться?

Vladimir Moskva (fulc.ru) 2011
Евгений Степанищев (bolknote.ru) 2011

Комментарий для fulc.ru:

Гм. Похоже, что не убъёт. Мы сегодня с art делали эксперимент, показалось, что убивает. Сильно удивились. А сейчас я попробовал сделать замеры, не подтвердилось.

Значит, мы ошиблись. all тут вполне подойдёт.

Vladimir Moskva (fulc.ru) 2011

Комментарий для Евгения Степанищева:

Проверить просто: all(xrange(1000000000)) завершается сразу, а all(xrange(1, 100000000)) не сжирает всю память (сравни с list вместо all).

К list’у приводит itertools.cycle, потому что у него нет другого выхода. На вход могут подать не просто iterable, а именно итератор, который нельзя отмотать назад. Но и он не сразу приводит к списку, а складывает значения по одному.

Евгений Степанищев (bolknote.ru) 2011

Комментарий для fulc.ru:

Проверить просто: all(xrange(1000000000)) завершается сразу, а all(xrange(1, 100000000)) не сжирает всю память (сравни с list вместо all).

Я просто сунул функцию в свой пример, которая печатала и возвращала то, что ей дали. Не понимаю в чём дело, но нам с art’ом показалось, что она не смогла съесть итератор.

А сейчас, дома, у меня получается, что превосходно его ест. Непонятно.

Признаю́, что zero_sharp прав.

Илья 2011

А почему бы и не
while arr != sorted(arr)... По-моему, гораздо глупее :)

Евгений Степанищев (bolknote.ru) 2011

Комментарий для Илья:

while arr != sorted(arr)... По-моему, гораздо глупее :)

Глупее — да :) Но ломает алгоритм, из-за того, что содержит сортировку.

Популярное