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])
9 февраля 2011 14:41

zero_sharp (инкогнито)
9 февраля 2011, 15:04

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

bolk (bolknote.ru)
9 февраля 2011, 15:08, ответ предназначен zero_sharp

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

gogis (инкогнито)
9 февраля 2011, 15:18

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

if current_val < last_var return false
last_var = current_val

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

gogis (инкогнито)
9 февраля 2011, 15:21

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

zero_sharp (инкогнито)
9 февраля 2011, 15:29, ответ предназначен bolk (bolknote.ru):

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 (инкогнито)
9 февраля 2011, 15:30

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

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

bolk (bolknote.ru)
9 февраля 2011, 16:20, ответ предназначен gogis

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

bolk (bolknote.ru)
9 февраля 2011, 16:21, ответ предназначен zero_sharp

while not all(x <= y for x, y in izip(arr, islice(arr, 1, None))):
Можно сразу выкинуть islice и izip. Функция all убъёт всю пользу итераторов.

bolk (bolknote.ru)
9 февраля 2011, 16:22, ответ предназначен http://twitter.com/Flash_it

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

Мохов Олег (o-mokhov.ya.ru)
9 февраля 2011, 16:35

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

bolk (bolknote.ru)
9 февраля 2011, 16:52, ответ предназначен Мохов Олег (o-mokhov.ya.ru):

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

gogis (инкогнито)
9 февраля 2011, 17:40

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

bolk (bolknote.ru)
9 февраля 2011, 17:56, ответ предназначен gogis

почему это быстрее, чем просто пробежаться по исходному массиву в цикле. Потому и не ясно.
У меня как-то смешались в сознании два комментария, ваш и zero_sharp'a, каюсь.

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

http://twitter.com/Flash_it (инкогнито)
9 февраля 2011, 18:57, ответ предназначен bolk (bolknote.ru):

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

andr (andr.mp)
9 февраля 2011, 20:54

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

bolk (bolknote.ru)
9 февраля 2011, 20:55, ответ предназначен andr (andr.mp):

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

andr (andr.mp)
9 февраля 2011, 21:21, ответ предназначен bolk (bolknote.ru):

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

bolk (bolknote.ru)
9 февраля 2011, 21:36, ответ предназначен andr (andr.mp):

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

Vladimir Moskva (fulc.ru)
9 февраля 2011, 22:17, ответ предназначен bolk (bolknote.ru):

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

bolk (bolknote.ru)
9 февраля 2011, 22:24, ответ предназначен Vladimir Moskva (fulc.ru):

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

Vladimir Moskva (fulc.ru)
9 февраля 2011, 22:29, ответ предназначен bolk (bolknote.ru):

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

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

Vladimir Moskva (fulc.ru)
9 февраля 2011, 22:31

http://docs.python.org/library/functions.html#all

bolk (bolknote.ru)
9 февраля 2011, 22:33, ответ предназначен Vladimir Moskva (fulc.ru):

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

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

Vladimir Moskva (fulc.ru)
9 февраля 2011, 22:40, ответ предназначен bolk (bolknote.ru):

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

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

bolk (bolknote.ru)
9 февраля 2011, 22:48, ответ предназначен Vladimir Moskva (fulc.ru):

Проверить просто: all(xrange(1000000000)) завершается сразу, а all(xrange(1, 100000000)) не сжирает всю память (сравни с list вместо all).
Я просто сунул функцию в свой пример, которая печатала и возвращала то, что ей дали. Не понимаю в чём дело, но нам с art'ом показалось, что она не смогла съесть итератор.

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

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

Илья (инкогнито)
9 февраля 2011, 23:46

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

bolk (bolknote.ru)
10 февраля 2011, 00:03, ответ предназначен Илье

while arr != sorted(arr)... По-моему, гораздо глупее :)
Глупее — да :) Но ломает алгоритм, из-за того, что содержит сортировку.

Ваше имя или адрес блога (можно OpenID):

Текст вашего комментария, не HTML:

Кому бы вы хотели ответить (или кликните на его аватару)