Все началось с данного топика на сайте gamedev.ru. Топикстартер предложил найти сортировку, которая обладает следующими свойствами:

1. Время выполнения — гарантированные O(nlogn).
2. Использование O(1) дополнительной памяти.
3. Применимость для сортировки данных в односвязных списках (но не ограничиваясь ими).

Оговорки на все три ограничения:

1. Гарантированные O(nlogn) означают, что, например, среднее время быстрой сортировки не подходит — должно получаться O(nlogn) для любых, даже самых худших входных данных.
2. Рекурсию использовать нельзя, поскольку она подразумевает O(logn) памяти на хранение стека рекурсивных вызовов.
3. Произвольного доступа к элементам сортируемого массива нет, мы можем двигаться итератором от любого элемента только к соседнему (за O(1)), причем только в одном направлении (вперед по списку). Модифицировать сам список (перевешивать указатели на следующие элементы) нельзя.

Вся информация, которую мы знаем об элементах массива — это то, что они все образуют линейно упорядоченное множество. Все, что мы можем делать — это сравнивать два элемента массива (за O(1)) и менять их местами (тоже за O(1)).

Под катом можно узнать, что в итоге получилось у нас.

Challenge. Прежде чем заглядывать под кат, предлагаю сначала самостоятельно подумать над алгоритмом. Если придумается что-то круче нашего варианта — напишите в комментариях.

Где вы нашли философию у Дональда Кнута? Академическое сообщество, это — 20 сумасшедших учёных, 2000 чичиковых, 20000 бюрократов и миллион детишек. Кнут это — Чичиков. На западе, даже сумасшедший учёный — умеет быть медийным, у нас это — «ранимые люди, с ними надо очень бережно, в лучшем смысле слова». Не могут связать двух слов, обижаются на вопросы. Поэтому в нашей науке видны только чичиковы, они раздают и получают награды, становятся директорами, основывают лаборатории, распиливают гранты, пристраивают своих. С прессой общаются, правда, тоже с трудом, — совок. А на западе это — развитой класс, они умеют работать с прессой, позиционироваться, колонизировать, занимать ниши, основывать религии. Найти человека который прочитал «Искусство Программирования» или «Конкретная Математика» практически невозможно, — те, кто считают Кнута за авторитет слишком глупы чтобы прочитать их, а те, что поумнее — читают книжки получше. Видимо, поэтому Кнут платил по 2.56 за каждую найденную опечатку, в надежде, что хотя-бы прочитают. Все его, с позволения сказать, книги — это копипаста алгоритмов из стэнфордских журналов, разбавленная топорным юмором, человек просто вовремя занял тему. А «детишки» от науки читают то, что им дают взрослые дяди — бюрократы и чичиковы. Вот и выходит, у бюрократов нет мозгов, у чичиковых есть мозги, но нет совести, сумасшедшие учёные — ранимые люди, обижаются.

def Миф и язык extends «трёхнаправленное программирование»;

Миф о том, что русские программисты лучшие в мире, запущен вовсе не партийными пропагандистами, он возник на перестроечной волне, вместе с мифами о хозяине-предпринимателе, невидимой руке рынка и ста сортах колбасы. Миф, это то, что человек не читавший взрослых книг называет «мем», а человек вообще не читающий, называет правдой. Передача «Разрушители мифов» берёт поверхностные мифы, которые можно легко опровергнуть, например, бросив бутерброд с маслом на пол тысячу раз. А вот Гордон, в одном из своих первых телепроектов «Собрание заблуждений», брался за раскрытие мифов посложнее, такие мифы нельзя раскрыть затопив машину и проверив, можно ли всё-таки открыть двери до того, как машина полностью наполнится водой, они как плавающий баг у которого нету «steps to reproduce». Вспомните Холмса или Хауса, интеллектуал в первую очередь отличается тем, что видит невидимое — пока паникующие пассажиры всматриваются в туман за бортом, он закрывает глаза и всматривается в свои «чертоги разума», вспоминает карту местности и ТТХ парохода.

«Всё содержится в моих чертогах разума, вы же понимаете о чём я мистер Холмс? Я обладаю знаниями, и поэтому могу щёлкать доктора Ватсона по носу хоть целый день.»

Эта история началась, когда мой друг и соратник, Яп Чэ-шень, сказал мне следующее:

— Я больше не хочу никогда в своей жизни писать на Дельфи! Я поклялся: больше ни единой строчки! С сегодняшнего дня все свои проекты и библиотеки перевожу на JavaScript!

Яп — китаец, с классическим менталитетом, свойственным его народу. Я многие годы работаю с ним над гуманитарными проектами в области оцифровки древней литературы, в первую очередь, «Буддийской библии» — Типитаки. Познания Япа, как в области самых древних текстов, так и самого современного программирования, не перестают удивлять меня уже более десяти лет — с тех пор, как мы начали сотрудничать и общаться на самые разные темы. Для себя я давно понял, что, если Яп что-то говорит, а я не согласен или не понимаю, то это лишь значит, что надо продолжать обсуждение, и вся громада причин и следствий в размышлениях моего друга выйдет на поверхность, и как всегда окажется, что Яп прав. Кажущаяся эмоциональность китайцев, на самом деле, необычайно рациональна.

Маленькая Лямбда решила, что уборку в комнате можно отложить и на потом.

Ленивые вычисления — часто используемая методика при исполнении компьютером программ на Haskell. Они делают наш код проще и модульнее, но могут вызвать и замешательство, особенно когда речь заходит об использовании памяти, становясь для новичков распространённой ловушкой. Например, безобидно выглядящее выражение

foldl (+) 0 [1..10^8]

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

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

Тема ленивых вычислений рассматривалась во многих учебниках (например, в книге Саймона Томпсона «Haskell — The Craft of Functional Programming»), но информацию о них, кажется, всё ещё проблематично найти в сети. Надеюсь, моё руководство посодействует решению этой проблемы.

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

Это Norton Commander? Это Volkov Commander? Это Dos Navigator? Это Far Manager?
Нет, это «Деодар» — новая рабочая среда для Линукс.
Деодар хостится на GitHub, основан на Node.js, написан на JavaScript плюс немного C++.
Распространяется по антилицензии Unlicense.org. Безвозмездно, то есть даром.
В данной статье на большом количестве картинок и малом количестве пояснений вы можете ознакомится с тем, что уже есть.
Да, «Деодар» — это такое дерево, Cedrus Deodara растёт высоко в горах, очень красивое.

Странно, что на Хабре нет никакой информации, когда весь мой твиттер гудит этим эпическим событием в мире програмирования, open source и startups.

Основатель одноименного издательства: TIM O'REILLY.

Сотрудник GitHub один из авторов книги Pro Git book, майнтайнер веб-странички Git-а и Git Community Book: SCOTT CHACON

Создатель BitTorrent: BRAM COHEN

Основатель InfoQ: FLOYD MARINESCU

Автор Symfony PHP framework: FABIEN POTENCIER

Программирование рассматривается как процесс создания компьютерных программ. Слово процесс в этом определении не лишнее. Обычно рассуждают в духе «посмотрите, какую замечательную структуру данных можно описать на данном языке программирования». Философия программирования подразумевает оглянуться по сторонам, да и в глубь копнуть.

Собственно разделение на кодирование, и создание алгоритмов это уже специфика, сначала идёт жизнь, то есть человек опирается на некую мысль вроде «напишу-ка я фреймворк с такими-то свойствами». И вот это начальное направление это вопрос философии. Проблема в том, что часто жена программиста лучше его самого знает, на философском уровне, что он делает и почему. Элементарные философские категории: мышление, сознание, обусловленность программисту неведомы. И это странно, если сравнить способность программиста мыслить, например, читая статьи по функциональному программированию или алгоритмам поиска, вперемешку со статьями видных русских или европейских философов, окажется, что собственно навык мышления у программистов развит не меньше, а то и больше. Вот только язык программиста очень богат пока он рассуждает о паттерн-матчинге и жалок и органичен когда ему надо выйти из своей песочницы, оторваться от IDE и файлового менеджера.

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

1 Один столбец вместо нескольких

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

Мы тут весь год общались с детскими психологами и вообще много думали о теме детского образования. Как один из результатов — сделали игру на развитие логики.



В общем, юному программисту нужно будет написать стек действий для таксиста. Чтобы довезти пассажира куда надо с первого раза. Сразу говорю — можно играть и с 4-5 лет. Как обычно, если ребёнок — сын инженера, смело вычитайте 2 года из минимального возраста.

Сегодня мы посмотрим на структуру данных, называемую Scapegoat-деревом. «Scapegoat», кто не в курсе, переводится как «козёл отпущения», что делает дословный перевод названия структуры каким-то странным, поэтому будем использовать оригинальное название. Деревьев поиска, как вы, возможно, знаете есть очень много разных видов, и в основе всех их лежит одна и та же идея: "А хорошо бы при поиске элемента перебирать не весь набор данных подряд, а только какую-то часть, желательно размера порядка log(N)".

Для этого каждая вершина хранит ссылки на своих детей и какой-то критерий, по которому при поиске точно понятно, в какую из дочерних вершин надо перейти. За логарифмическое время это всё будет работать тогда, когда дерево является сбалансированным (ну или стремится к этому) — т.е. когда «высота» каждого из поддеревьев каждой вершины примерно одинакова. А вот способы балансировки дерева уже у каждого типа деревьев свои: в красно-чёрных деревьях в вершинах хранятся маркеры «цвета», подсказывающие когда и как нужно перебалансировать дерево, в АВЛ-деревьях в вершинах хранится разница высот детей, Splay-деревья ради балансировки вынуждены изменять дерево во время операций поиска и т.д.

Scapegoat-дерево тоже имеет свой подход к решению проблемы балансировки дерева. Как и для всех остальных случаев он не идеален, но вполне применим в некоторых ситуациях.

К достоинствам Scapegoat-дерева можно отнести:

• Отсутствие необходимости хранить какие-либо дополнительные данные в вершинах (а значит мы выигрываем по памяти у красно-черных, АВЛ и декартовых деревьев)
• Отсутствие необходимости перебалансировать дерево при операции поиска (а значит мы можем гарантировать максимальное время поиска O(log N), в отличии от Splay-деревьев, где гарантируется только амортизированное O(log N))
• Амортизированная сложность операций вставки и удаления O(log N) — это в общем-то аналогично остальным типам деревьев
• При построении дерева мы выбираем некоторый коэффициент «строгости» α, который позволяет «тюнинговать» дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.

К недостаткам можно отнести:

• В худшем случае операции модификации дерева могут занять O(n) времени (амортизированна сложность у них по-прежнему O(log N), но защиты от «плохих» случаев нет).
• Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента α — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что как-то не хорошо.

Примечание переводчика: перед прочтением этого поста рекомендую сначала ознакомиться с постом Вникаем в метаклассы Ruby.

Все рубисты знакомы с формальными определениями для include и extend. Вы делаете include модуля, чтобы добавить методы экземпляра класса, и extend — чтобы добавить методы класса. К сожалению, данные определения не совсем точны. Они не могут объяснить почему мы используем instance.extend(Module), чтобы добавить методы объекту. Разве не должны мы в этом случае использовать instance.include(Module)? Чтобы разобраться в этом вопросе, начнем с выяснения где же хранятся методы.

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

Начнем с такого интересного типа, как ENUM.

mysql> CREATE TABLE enums(a ENUM('c', 'a', 'b'), b INT, KEY(a));
Query OK, 0 rows affected (0.36 sec)

mysql> INSERT INTO enums VALUES('a', 1), ('b', 1), ('c', 1);
Query OK, 3 rows affected (0.05 sec)
Records: 3  Duplicates: 0  Warnings: 0

Итак, у нас есть таблица, в ней есть два столбца. У первого, a, тип ENUM, у второго, b, INT. В таблице три строки, у всех трех значение b равно 1. Интересно, чему равны минимальный и максимальный элементы в столбце a?

mysql> SELECT MIN(a), MAX(a) FROM enums;
+--------+--------+
| MIN(a) | MAX(a) |
+--------+--------+
| c      | b      |
+--------+--------+
1 row in set (0.00 sec)

Кажется странным, было бы разумно, если бы самым маленьким был 'a', а самым большим — 'c'.
А что если выбрать минимум и максимум только среди тех строк, где b = 1? То есть, среди всех строк?

mysql> SELECT MIN(a), MAX(a) FROM enums WHERE b = 1;
+--------+--------+
| MIN(a) | MAX(a) |
+--------+--------+
| a      | c      |
+--------+--------+
1 row in set (0.00 sec)

Вот так мы заставили MySQL поменять свое мнение о том, как сравнивать поля в ENUM, просто добавив предикат.
Разгадка такого поведения заключается в том, что в первом случае MySQL использует индекс, а во втором нет. Это, конечно, не объясняет, почему MySQL сравнивает ENUMы по разному для сортировки в индексе, и при обычном сравнении.

Второй пример проще и лаконичнее:

mysql> (SELECT * FROM moo LIMIT 1) LIMIT 2;
+------+
| a    |
+------+
|    1 |
|    2 |
+------+
2 rows in set (0.00 sec)

Когда я показал этот запрос своему коллеге, который занимается разработкой парсера SQL, его вопрос был не «почему этот запрос возвращает две строки», а «как надо написать SQL парсер так, чтобы такой запрос был валидным, без того, чтобы написать правило, специально разрешающее такой запрос».

Интересно, что далеко не любой SELECT в скобках сработает, в частности, UNION в скобках — это синтаксическая ошибка:

mysql> (SELECT * FROM moo UNION ALL SELECT * FROM hru) LIMIT 2;
ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'UNION ALL SELECT * FROM hru) LIMIT 2' at line 1

Еще несколько интересных примеров под катом

В комментариях Хабра упоминались вопросы по использованию представлений. Данный топик является обзором представлений, появившихся в MySQL версии 5.0. В нем рассмотрены вопросы создания, преимущества и ограничения представлений.

Что такое представление?

Представление (VIEW) — объект базы данных, являющийся результатом выполнения запроса к базе данных, определенного с помощью оператора SELECT, в момент обращения к представлению.

Представления иногда называют «виртуальными таблицами». Такое название связано с тем, что представление доступно для пользователя как таблица, но само оно не содержит данных, а извлекает их из таблиц в момент обращения к нему. Если данные изменены в базовой таблице, то пользователь получит актуальные данные при обращении к представлению, использующему данную таблицу; кэширования результатов выборки из таблицы при работе представлений не производится. При этом, механизм кэширования запросов (query cache) работает на уровне запросов пользователя безотносительно к тому, обращается ли пользователь к таблицам или представлениям.

Всю рутину, которую можно отдать роботам, нужно отдать роботам. Большие системы без этого невозможны. В разработке и тестировании очень много похожих задач, которые не требуют высокой квалификации, но отнимают много времени. Человек, который умеет обеспечить разработку, тестирование и деплой – это редкий специалист и его на количество страничек никак не масштабируешь.

В Яндексе тестировщику невозможно без автоматизации. Мы даже развиваем экспериментального робота, который способен брать на себя функциональное тестирование. В какой-то момент мы поняли, что не так много людей осознают, сколько сейчас есть возможностей работать не 12 часов, а головой. Собрав весь свой опыт в тестировании и деплое, мы открыли в питерском офисе Яндекса Школу автоматизации процессов разработки. У нас получилась школа, где каждый, кто пишет код, может получить базовый набор знаний о том, как собрать, запустить и поддерживать сервис в продакшене так, чтобы это стоило недорого.



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

Сейчас занятия закончились, и мы, как и обещали, выкладываем записи лекций, которые перемежаются с мастер-классами, для всех желающих. Понятно, что наш опыт и знания – не 42, но мы надеемся, что они принесут вам пользу.

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

Эта моя публикация чуть более чем полностью является ответом на перевод статьи «Почему вы никогда не должны использовать MongoDB». Статья, которая, по сути, рекомендует держаться подальше от MongoDB, является самой заплюсованной в хабе. И это звучит как приговор. Поэтому логично либо хаб закрыть и больше никогда не читать, либо написать ещё более рейтинговое опровержение. Конечно же, я выбрал второй вариант, рискуя своим рейтингом и кармой (ввиду крайней холиварности в комментах).

Картинка самоиронии

В статье пойдет речь о том, как из любого запроса на естественном языке получить реальные данные, с которыми может работать ваше приложение. А именно, о REST API сервиса SpeechMarkup, который преобразует обычную строчку текста в JSON со всеми найденными смысловыми сущностями с конкретными данными в каждой из них.

Да-да, это та самая технология, которая лежит в основе любого голосового ассистента и используется в поисковиках.
Она позволяет однозначно интерпретировать запрос, а затем вернуть вашему приложению результат в виде обычного набора данных.

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

Предлагаем вашему вниманию подборку с ссылками на полезные ресурсы, интересные материалы и IT-новости

Здравствуй, дорогой хабрадруг! Сегодня существуют более тысячи способов создать кнопку; чтобы понять их сущность, вам нужно лишь потратить немного времени, просмотрев работы на сайте dribbble.com. Большинство из этих примеров очень похожи друг на друга, однако время от времени попадаются и такие кнопки, на создание которых потратили чуть больше внимания, времени и сил.



Воспользовавшись замечательными параметрами CSS3, мы можем создать элегантые и стильные кнопки без особых усилий (учитывая старые браузеры, конечно). Создаете ли вы кнопку непосредственно в CSS или пользуетесь специальными инструментами для их создания, всегда нужно тщательно подумать о том, как ваша кнопка будет выглядеть в контексте веб-сайта.