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

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

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

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

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

gogis

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

if current_val < last_var return false
last_var = current_val

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

gogis

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

zero_sharp

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

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

http://twitter.com/Flash_it

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

gogis

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

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

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

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

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

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

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

http://twitter.com/Flash_it

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

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

andr (andr.mp)

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

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

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

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

andr (andr.mp)

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

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

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

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

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

Vladimir Moskva (fulc.ru)

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

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

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

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

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

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

Vladimir Moskva (fulc.ru)

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

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

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

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

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

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

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

Vladimir Moskva (fulc.ru)

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

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

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

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

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

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

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

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

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

Илья

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

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

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

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

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

Популярное