.png "BitSorting Алгоритм со сложностью О(n)")
В свободное от работы время решил поразмыслить, а нельзя ли создать алгоритм соритировки который имел бы сложность O(n) не занимал бы много дополнительной памяти и мог бы быть легко распараллелен. И добился некоторого результата.
Читать полностью »
.png "Merge sort и AS3. Обгоняем родной Vector.sort(Array.NUMERIC)")
Слева — mergeSort, справа — родная сортировка. PepperFlash и 75 миллионов элементов.Читать полностью »
Если вам понадобится алгоритм сортировки массива, который:
то вам, скорее всего, предложат ограничиться любыми двумя из этих трёх пунктов. И, в зависимости от вашего выбора, вы получите, например, либо сортировку слиянием (требует O(N) дополнительной памяти), либо пирамидальную сортировку (неустойчив), либо сортировку пузырьком (работает за O(N2)). Если вы ослабите требование на память до O(log(N)) («на рекурсию»), то для вас найдётся алгоритм со сложностью O(N*(log(N)2) — довольно малоизвестный, хотя именно его версия используется в реализации метода std::stable_sort().
На вопрос, можно ли добиться выполнения одновременно всех трёх условий, большинство скажет «вряд ли». Википедия о таких алгоритмах не знает. Среди программистов ходят слухи, что вроде бы, что-то такое существует. Некоторые говорят, что есть «устойчивая быстрая сортировка» — но у той реализации, которую я видел, сложность была всё те же O(N*(log(N)2) (по таймеру). И только в одном обсуждении на StackOverflow дали ссылку на статью B-C. Huang и M. A. Langston, Fast Stable Merging and Sorting in Constant Extra Space (1989-1992), в которой описан именно такой алгоритм.
В прошлой статье мы оттолкнулись от так называемой глупой сортировки и путём нехитрых метаморфоз получили всем известную пузырьковую сортировку. Трансформируя последнюю пришли к целому вороху обменных способов упорядочивания массивов. Один из которых, между прочим, на структурах до нескольких тысяч элементов, даже работает быстрее чем быстрая сортировка.
Сегодня мы снова возьмём за основу stupid sort и внесём в неё другое маленькое, но существенное изменение. В результате получим совершенного другой эволюционный ряд сортировочных алгоритмов.
image: эволюция
А что это мы всё об умных да об эффективных алгоритмах? А давайте эту тоскливую осеннюю пятницу развеем чем-нибудь контрпродуктивным!?
Представляю Вашему вниманию ТОП-5 самых нетрадиционных сортировок всех времён и народов.
Младопрограммистам такое полезно показывать в дидактических целях. Всех остальных как минимум позабавит.
Читать полностью »
Когда речь заходит об эффективных алгоритмах сортировок, эрудированный читатель сразу же припомнит неувядаемую «быструю сортировку», новомодную «сортировку Тима», легендарную «сортировку слиянием» и даже мудрёную «интроспективную сортировку».
Не подвергая сомнению эффективность вышеприведённых методов, предлагаю Вашему вниманию сортировку, которая при определённых входных данных легко уделывает по скорости любой другой алгоритм.
Читать полностью »
Задача сортировки — это классическая задача, которую должен знать любой программист. Именно поэтому эта статья посвящена данной теме — реализации сортировки на платформе .NET. Я хочу рассказать о том, как устроена сортировка массивов в .NET, поговорить о ее особенностях, реализации, а также провести небольшое сравнение с Java.
Итак, начнем с того, что первые версии .NET используют алгоритм быстрой сортировки по умолчанию. Поэтому небольшой экскурс в быструю сортировку:
Читать полностью »
Всё началось с того, что на работе у коллеги стали падать тесты. Причём только у неё одной. Вдаваться в подробности не буду, но суть в том, что в тесте было два объекта List. Первый был эталонным, а второй — возвращался тестируемым методов. Затем листы сравнивались поэлементно.
Очень быстро было выяснена причина падения теста: у коллеги порядок элементов в результирующем массиве был обратным порядку в эталонном массиве. В коде тестируемого метода использовался стандартный List.Sort с нашим компаратором, который именно на этом тесте всегда возвращает 0. Но у всей команды элементы возвращались в одном порядке, а у одной сотрудницы — строго в обратном. Было быстро выяснено, что у коллеги давно не было обновлений и версия mscorlib.dll у неё сильно отличалась от той, что была у остальных. На этом можно было бы и успокоиться, но мне стало интересно я решил копать дальше и вот что выяснил. Читать полностью »
Disclaimer: я начал писать этот скрипт, когда весёлые новости ещё не подоспели.
Буду краток.
vk_music_organizer.py из архива, открываете в блокноте, в самом начале пишете в строках email = '...' и password = '...' свой логин и пароль соответственно. Сохраняете. Если у вас корректно установлен Python, то после этого достаточно просто запустить этот файл двойным щелчком. Да простят меня понимающие люди за такие слова.
Не все комментарии одинаково полезны
2014-01-20 в 14:08, admin, рубрики: comments, digg, Алгоритмы, комментарии, математика, Медиа, ранжирование, сортировка, хабрахабр, метки: comments, digg, комментарии, ранжирование, сортировка, ХабрахабрДостаточно много статей на хабре набирает существенное количество комментариев, e.g. в статьях "лучшее за месяц" их, как правило, более сотни. За годы чтения хабра, создалось впечатление, что примерно в половине случаев для комментариев первого уровня получается вот такая вот картина
(картинка сделана на основе хабра-статьи Список скептика)
Под катом рассказ, какие бывают сортировки комментариев, где они применяются и краткое рассуждение о том, как вообще можно сортировать комментарии (и зачем).
Читать полностью »