Если вам понадобится алгоритм сортировки массива, который:

• Работал бы гарантированно за O(N*log(N)) операций (обменов и сравнений);
• Требовал бы O(1) дополнительной памяти;
• Был бы устойчивым (то есть, не менял порядок элементов с одинаковыми ключами)

то вам, скорее всего, предложат ограничиться любыми двумя из этих трёх пунктов. И, в зависимости от вашего выбора, вы получите, например, либо сортировку слиянием (требует O(N) дополнительной памяти), либо пирамидальную сортировку (неустойчив), либо сортировку пузырьком (работает за O(N²)). Если вы ослабите требование на память до O(log(N)) («на рекурсию»), то для вас найдётся алгоритм со сложностью O(N*(log(N)²) — довольно малоизвестный, хотя именно его версия используется в реализации метода std::stable_sort().

На вопрос, можно ли добиться выполнения одновременно всех трёх условий, большинство скажет «вряд ли». Википедия о таких алгоритмах не знает. Среди программистов ходят слухи, что вроде бы, что-то такое существует. Некоторые говорят, что есть «устойчивая быстрая сортировка» — но у той реализации, которую я видел, сложность была всё те же O(N*(log(N)²) (по таймеру). И только в одном обсуждении на StackOverflow дали ссылку на статью B-C. Huang и M. A. Langston, Fast Stable Merging and Sorting in Constant Extra Space (1989-1992), в которой описан алгоритм со всеми тремя свойствами.

Предисловие

Одно время мне везло на всякие странные работы. Например, я чуть было не устроился админом в синагогу. Остановила меня только предчувствие, что меня там как последнего гоя будут заставлять работать по субботам.

Другой вариант тоже был любопытным. Фирма сочиняла эссе и курсовые для американских студентов, которым в лом было писать самим. Уже потом я узнал, что это довольно распространенный и прибыльный бизнес, которому даже придумали собственное название — «paper mill», но сразу такой способ зарабатывания на жизнь показался мне полным сюром. Однако же надо заметить, что интересных задач на этой работе оказалось немало и среди них — самая сложная и хитрая из тех, что я делал за свою карьеру, и которой можно потом с гордостью рассказывать детям.

Формулировка ее была очень проста. Сочинители курсовых — удаленные работники, очень часто — арабы и негры, для которых английский язык был неродным, и ленивы они были ничуть не меньше самих студентов. Нередко они шли по пути наименьшего сопротивления и вместо написания оригинальной работы тупо передирали ее из Интернета, целиком или частями. Соответственно, надо было найти источник (или источники), сравнить, как-то определить процент сплагиаченности и передать собранные сведения для уличения нерадивых.

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

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

Привет, Хабр!

Решил посмотреть лучшие посты своего любимого хаба и с ужасом обнаружил, что такой фичи нет.

В связи с тем, что данная возможность появилась, а топик сносить в черновики не хочется — ниже рейтинг самых комментируемых и добавляемых в избранное статей самых популярных хабов. Кроме того пару слов о реализации скрипта.

Стартовала распродажа в честь «Чёрной пятницы», распродажа продлится с 27 ноября до 3 декабря 22:00 по МСК времени, то есть ровно неделю.

Всем привет. В этой статье я хотел бы рассказать немного об основных приемах и идеях современной цифровой беспроводной связи — на примере стандарта IEEE 802.11. В наше время очень часто люди живут на довольно высоких уровнях абстракции, плохо представляя как именно работают окружающие нас вещи. Ну что ж — попытаюсь принести в массы свет просвещения. В статье будут использоваться вещи и терминология, объясненные в этой статье. Так что людям, далеким от радиотехники рекомендуется сначала прочитать её.
DANGER: в статье присутствует матан — особо впечатлительным не нажимать на эту кнопку:

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

Сегодня мы познакомимся с основной и самой многочисленной группой инструментов — событийными профайлерами.

Теперь статей и проектов стало больше — включены новости с pycoders, pythonplanet и по-прежнему мониторятся новые пакеты и релизы уже популярных проектов на PyPI и github.
Увы, все также мало материалов на русском языке. Присылайте мне пожалуйста ссылки если находите достойные и актуальны статьи.

Огромное спасибо гитхабо-пользователю и земляку axcel, благодаря которому на нашем инструменте для сбора новостей появились rss лента и optimistic locks при сохранении объектов.

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

Лет семь назад попал в руки крякеров архив с сорцом генератора ключей для протектора под названием Armadillo. Просто кое-кому из благодарных пользователей продукта захотелось проверить его на прочность. А где еще получишь бесплатный аудит такого интересного кода, как не на крякерском форуме.

Этот генератор нужен был для того, чтобы при покупке клиентом вашей программы, защищенной Armadillo, мерчант смог сам автоматически сгенерировать для неё лицензионный ключ. Так же, он использовался в самой Armadillo и, если б была возможность узнать секрет, то можно было бы сделать кейген для неё самой. Что делало аудит кода вдвойне интересным.

Итак, вот он, оригинальный, добытый путём титанических усилий, архив. (исходник на C)

Попробуйте без подсказок понять, в чем именно сокрыта уязвимость. Там хоть и куча кода, но он хорошо читаем. Не получилось? А если глянуть на 528 строчку?

В далеком (а может и не очень далеком) 1975 году Альфред Ахо и Маргарет Корасик опубликовали статью, в которой был подробно описан алгоритм эффективного поиска всех вхождений всех строк-образцов в заданную строку. В дальнейшем этот алгоритм и получил название «алгоритм Ахо-Корасик». Неудивительно, что через некоторое время появились технические и «художественные» переводы данной статьи на русский язык. Порой мне даже встречались вольные изложения сути алгоритма в том виде, в котором его понимает автор. Причем последний, судя по тексту, узнал об алгоритме далеко не из первоисточника. Я не знаю существовал ли перевод, который послужил первоисточником проблемы, но мне всё больше и больше попадаются статьи с описанием алгоритма Ахо-Корасик, в котором допущена одна и та же кардинальная ошибка. Последней каплей была статья пользователя rmq на хабре, которую данная ошибка не миновала. Собственно об этой ошибке мне и хотелось бы рассказать общественности в своей статье.
Замечание: статья пользователя rmq, как выяснилось позже, не содержит этой ошибки. Как она решена там расскажу ниже. А ему огромное спасибо, если бы не его топик я бы не написал свой и не получил бы инвайт!
Перед началом, еще пара слов о целевой аудитории: Скорее всего, тем, кто давно знаком с алгоритмом Ахо-Корасик, моя статья будет не интересна, так как о его особенностях они давно уже знают. По крайней мере, все мои знакомые программисты не один раз применявшие данный алгоритм знают о существовании его неверных интерпретаций не понаслышке. А вот новичкам и тем, кому не довелось часто применять его на практике, эта статья может оказаться довольно полезной.
Итак, начнем.

Если в Вашем проекте есть таблицы размер которых исчисляется гигабайтами, а для того чтобы поменять структуру такой таблицы вам на несколько часов приходится останавливать все сервисы — эта статья будет для Вас.

Дано: таблица размером в несколько десятков гигабайт данных. Задача — изменить структуру таблицы.

Оптический поток (Optical flow) – технология, использующаяся в различных областях computer vision для определения сдвигов, сегментации, выделения объектов, компрессии видео. Однако если мы захотим его по-быстрому реализовать в своем проекте, прочитав про него на википедии или где-нибудь еще, то, скорее всего, очень быстро наткнемся на то, что он работает очень плохо и сбоит при определении сдвигов уже порядка 1-2 пикселей (по крайней мере так было у меня). Тогда обратимся к готовым реализациям, например, в OpenCV. Там он реализован различными методами и совершенно непонятно, чем аббревиатура PyrLK лучше или хуже обозначения Farneback или чего-нибудь в этом роде, да и придется поразбираться со смыслом параметров, которых в некоторых реализациях очень много. Причем, что интересно, эти алгоритмы как-то работают, в отличие от того, что мы написали сами. В чем же секрет?

В предыдущей статье мы заглянули внутрь процессора, пусть и гипотетического. Мы выяснили, что для корректного выполнения параллельного кода процессору необходимо подсказывать, до каких пределов ему разрешено проводить свои внутренние оптимизации чтения/записи. Эти подсказки – барьеры памяти. Барьеры памяти позволяют в той или иной мере упорядочить обращения к памяти (точнее, кэшу, — процессор взаимодействует с внешним миром только через кэш). “Тяжесть” такого упорядочения может быть разной, — каждая архитектура может предоставлять целый набор барьеров “на выбор”. Используя те или иные барьеры памяти, мы можем построить разные модели памяти — набор гарантий, которые будут выполняться для наших программ.

В этой статье мы рассмотрим модель памяти C++11.

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

Здравствуйте, хабрачеловеки! Многие из Вас сталкивались с вынесением бизнес-логики в СУБД в виде хранимых функций/процедур, облегчая клиент. В этом есть как и преимущества, так и недостатки. Сегодня я бы хотел рассказать Вам как создавать хранимые функции в PostgreSQL, написанные на языке C. В статье будут самые основы, которые необходимо знать для начала работы с ними.

За то время, что я занимаюсь программированием, я видел не мало проектов, загнувшихся, благодаря фанатичному следованию различным модным правилам и практикам. Это может быть что-то увлекшее всю команду, например OOP или TDD, или что-то, на чем настоял отдельный разработчик, например: табы против пробелов, или определенный стиль фигурных скобок. Даже программист работающий в одиночестве, может саботировать проект, выбрав фетиш в ущерб продуктивности.
Вот немного вещей, отнимающих часы, а то и дни программистского времени:

Я надеюсь, что эта статья станет началом цикла заметок о lock-free структурах данных. Я хочу поделиться с хабрасообществом своим опытом, наблюдениям и размышлениями о том, что такое lock-free структуры данных, как их реализовывать, подходят ли концепции контейнеров стандартной библиотеки STL к lock-free контейнерам, и когда стоит (и стоит ли вообще) применять lock-free структуры данных.

Списки книг

• 25 бесплатных книг по информатике
• Шпаргалки
• CodePlex: Список бесплатных книг
• Бесплатные технические книги
• Galileo Computing (Немецкий)
• How to Design Programs: An Introduction to Computing and Programming
• Microsoft Press: Бесплатные книги
• MindView Inc
• Проект O'Reilly's Open Books
• TechBooksForFree.com
• Theassayer.org
• Wikibooks: Программирование
• Неплохая подборка, редактируемая сообществом (JIghtuse)
• Книги на Русском (telteron)

Программирование графики

После просмотра курса Programming Languages и прочтения Functional JavaScript захотелось повторить все эти крутые штуки в python. Часть вещей получилось сделать красиво и легко, остальное вышло страшным и непригодным для использования.

Статья включает в себя:

• немного непонятных слов;
• каррирование;
• pattern matching;
• рекурсия (включая хвостовую).

Статья рассчитана на python 3.3+.

В последнем обновлении SQLite планировщик запросов претерпел серьезные изменения и отныне зовется Планировщик Запросов Следующего Поколения. Мы решили сделать небольшой обзор нового планировщика и некоторых других значительных обновлений SQLite в текущем году. Новый функционал может оказаться полезным разработчикам.