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

Я столкнулся с необходимостью составления списка всех перестановок из n элементов. Для n = 4 или даже 5, задача решается вручную в считанные минуты, но для 6! = 720 и выше исписывать страницы мне уже было лень – нужна была автоматизация. Я был уверен, что этот «велосипед» уже изобретён многократно и в различных вариациях, но было интересно разобраться самостоятельно – поэтому, намеренно не заглядывая в профильную литературу, я засел за создание алгоритма.

Всем доброго времени суток!

Началось всё с того, что в качестве тестового задания на собеседованиях, я начал просить соискателей реализовать предзагрузчик картинок на JS. Помимо самой предзагрузки, скрипт должен был уметь подставлять fallback-картинку, если нужная картинка не могла быть загружена. Обязательным условием было — использование ES6 Promise.
Затем я подумал: «А почему бы самому не реализовать такой предзагрузчик и не выложить в общее пользование? Да это же еще и отличный повод написать статью на Хабр!».
Собственно, под катом описание логики работы такого предзагрузчика + ссылка на сам предзагрузчик.

Друзья, мы с радостью продолжаем публикацию интересных материалов, посвященных самым разнообразным аспектам работы с PostgreSQL. Сегодняшний перевод открывает целую серию статей за авторством Hubert Lubaczewski, которые наверняка заинтересуют широкий круг читателей.



Одна из первых вещей, которую слышит новоиспеченный администратор баз данных – «используй EXPLAIN». И при первой же попытке он сталкивается c непостижимым:

                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=146.63..148.65 rows=808 width=138) (actual time=55.009..55.012 rows=71 loops=1)
   Sort Key: n.nspname, p.proname, (pg_get_function_arguments(p.oid))
   Sort Method: quicksort  Memory: 43kB
   ->  Hash Join  (cost=1.14..107.61 rows=808 width=138) (actual time=42.495..54.854 rows=71 loops=1)
         Hash Cond: (p.pronamespace = n.oid)
         ->  Seq Scan on pg_proc p  (cost=0.00..89.30 rows=808 width=78) (actual time=0.052..53.465 rows=2402 loops=1)
               Filter: pg_function_is_visible(oid)
         ->  Hash  (cost=1.09..1.09 rows=4 width=68) (actual time=0.011..0.011 rows=4 loops=1)
               Buckets: 1024  Batches: 1  Memory Usage: 1kB
               ->  Seq Scan on pg_namespace n  (cost=0.00..1.09 rows=4 width=68) (actual time=0.005..0.007 rows=4 loops=1)
                     Filter: ((nspname <> 'pg_catalog'::name) AND (nspname <> 'information_schema'::name))

Что бы это могло значить?

Продолжение цикла статей о физике в играх про Соника.

Примечание:

Обзор затрагивает все четыре части игры на Genesis/Mega Drive и Sonic CD.

Все написанное ниже относится к ситуации, когда Соник находится на плоской сухой поверхности, не имея специальных бонусов. Кривые, физика поведения в воде, бонусы Super Sonic и Speed Shoes будут рассмотрены в отдельных статьях. Под шагами в статье понимаются программные циклы, а не шаги персонажа.

По просьбе tulskiy делаю вольный перевод частей официальной документации GitHub'а Fork A Repo и Send pull requests.

Итак, что же такое «запрос на включение (сделанных вами изменений)» (именно так я перевёл pull request)? В официальной документации гитхаба говорится следующее:

Pull request'ы позволяют вам рассказать другим о тех изменениях, которые вы разместили в своём GitHub-репозитории. Как только pull request отправлен, заинтересованные стороны рассматривают ваши изменения, обсуждают возможные правки или даже добавляют дополняющие коммиты, если нужно.

Говоря своим языком: Посылая pull request, вы говорите автору изначального репозитория (и всем заинтересованным лицам): «Смотрите, что я сделал, не хотите ли принять мои изменения и влить их в проект?»

Не так давно в мире web-разработки произошло важное событие — вышла бета Angular 2. И уже можно строить предположения о том, как он будет выглядеть после релиза.

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

Так и родилась мысль сравнить Angular 2 с новым, но весьма амбициозным проектом Aurelia, который так же недавно вышел в бету. А заодно пополнить копилку Хабра информацией об этом фреймворке, поскольку пока ее гораздо меньше, чем информации об Angular 2.

Индикатор кулачкового аналогового компьютера / Wiki

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

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

Даже самый честный человек – мастер самообмана. Мы умеем быстро выделять аномальные результаты, однако часто принимаем на веру все, как нам кажется, «логичные» выводы. Таким образом, мы бессознательно уходим от реальности.

Сегодня я хочу вам рассказать об алгоритмах подсчёта количества палиндромов в строке: для чего это нужно, где применяется, как это быстро сделать, какие подводные камни нас ожидают и многое другое. Рассмотрим различные способы для решения данной задачи, выясним плюсы и минусы каждого способа. Эта статья будет обзорной: если я что-то не описываю здесь, то постараюсь всегда дать вам набор ссылок, где всё подробно описано и расписано. Надеюсь, что материал будет интересен как новичкам в сфере алгоритмов, так и матёрым программистам. Что же, если я смог заинтересовать вас, то прошу под кат!

Python жив! С такого громкого заявления хочется начать статью.

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



В конце 2014 года мы подводили итоги за год. В этот раз мы рассмотрим тенденции за неполные 11 месяцев 2015-года.

Но перед тем как перейдем к тенденциям — расскажем что сделали за (почти) год.

Интересующихся подробностями милости просим под кат.

Статьи о получении (псевдо)случайных чисел, о проверке качества полученных последовательностей неизменно вызывают интерес у населения Хабра.

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

Метод описанный ниже предложен Санделиусом (М. Sandelius) еще в 1962 г. в работе [1].

Группа немецких ученых из немецкого сообщества hardwaluxx.de обнаружила ошибку в работе процессоров Intel Skylake, приводящую к зависанию компьютера в процессе осуществления сложных вычислений. Позднее математики из проекта добровольных вычислений по поиску простых чисел Мерсенна (GIMPS) подтвердили наличие проблемы. Баг проявился в ходе работ по поиску простых чисел Мерсенна с помощью инструмента Prime95.

Здравствуйте, уважаемые хабровчане! Мы решили возобновить публикации еще до окончания больших праздников, но в сегодняшней статье все-таки раскрыта тема справедливой раздачи подарков. Сама же статья, как понятно из названия, посвящена сравнительному анализу параллелизма и конкурентности.

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

Python — один из немногих динамических языков, в которых отсутствует встроенная поддержка регулярных выражений, но это компенсируется проработанной базовой системой (с точки зрения API). В то же время он весьма причудлив. К примеру, поведение написанного на Python парсера может вас удивить. Если вы попытаетесь в ходе импорта профилировать Python, то, скорее всего, 90% времени вы проведёте в работе с модулем re.

18-19 сентября в Екатеринбурге прошла третья международная конференция python-разработчиков PyCon Russia. 21 доклад, два мастер-класса, Lightning Talks — все это PyCon-2015. Под катом — отчет о прошедшей конференции, много видео и презентации докладов.

Питонисты собрались из 25 городов, среди которых: Сан-Франциско, Париж, Прага, Бонн, Таллин, Минск, Киев, Москва, Санкт-Петербург, Казань, Уфа

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

Мир javascript развивается с невероятной скоростью: новые стандарты языка, новые фреймворки, и в браузере, и на сервере и в десктопных приложениях и так далее… Но иногда хочется вместо изучения новой супер-фичи погрузиться в какую-то более базовую тему. И погрузиться глубоко, до самых исходников.

И в этот момент под моим пристальным взглядом оказалась незаметная строчка «native code», которая так или иначе появляется перед глазами любого JS разработчика в консоли Chrome или Node.js:

[].sort.toString();
"function sort() { [native code] }"

Итак, кому интересно, какая реализация сортировки скрывается в V8 за надписью [native code] — добро пожаловать под кат.

Года полтора назад встал вопрос совместимости написанного кода с Python3. Поскольку уже стало более менее очевидно, что развивается только Python3 и, рано или поздно, все библиотеки будут портированы под него. И во всех дистрибутивах по умолчанию будет тройка. Но постепенно, по мере изучения, что нового появилось в последних версиях Python мне все больше стал нравится Asyncio и, скорее, даже не Acyncio а написанный для работы с ним aiohttp. И, спустя какое то время, появилась небольшая обертка вокруг aiohttp в стиле like django. Кому интересно что из этого получилось прошу под кат.

Вторая часть

Введение
Краткий обзор других фреймворков на базе aiohttp
1. Структура
2. aiohttp и jinja2
3. aiohttp и роуты
4. Статика и GET, POST параметры, редиректы
5. Websocket
6. asyncio и mongodb, aiohttp, session, middleware
7. aiohttp, supervisor, nginx, gunicorn
8. После установки, о примерах.
9.RoadMap

Ты просто-напросто ненавидишь Git? Ты абсолютно счастлив с Mercurial (или, фу, с Subversion), но раз в месяц тебе приходится отважно сталкиваться с Git, потому что каждый, даже его чертова собака, теперь использует GitHub? Тебя терзают смутные подозрения, что половина всех команд Git на самом деле удалят всю твою работу навсегда, но ты не знаешь какие именно и не хочешь проводить три недели, углубляясь в документацию?

Хорошие новости! Я написал тебе этот изумительный Интернет-пост. Я надеюсь, что смогу размазать достаточно Git-а по твоему лицу, чтобы понизить вероятность сделать что-то непоправимое, а так же уменьшить твой страх что-то сломать. Этого должно быть также достаточно, чтобы сделать документацию Git немного более понятной; она крайне тщательно и глубоко проработана и очень глупо, если ты все еще не прочитал половину.

Я постараюсь излагать коротко, но также, чтобы это было потенциально полезно тем людям, кто вообще никогда не сталкивался с контролем версий, поэтому повсюду будет разбросан 101 совет. Не бойся! Я не думаю, что пользователи Mercurial понятия не имеют, что такое патч.

Недавно я снова исследовал вопрос загрузки шрифтов, так как я хотел использовать локальную копию шрифта и сделать ее загрузку максимально быстрой и эффективной. Данный подход существенно отличается от того, когда вы используете TypeKit или шрифты Google и простые сниппеты «копировать/вставить».

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

1, 2, 3

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

Цели:

1. Асинхронно загружать веб-шрифты
2. Избежать сильного пересчета положения в макете
3. Как можно быстрее загружать веб-шрифты
4. Избежать загрузки шрифтов для возвращающихся посетителей

А теперь давайте попробуем добиться наших целей поэтапно:

Прочитав эту статью, я вспомнил, как писал внешнюю сортировку, которая использовала O(1) внешней памяти. Функция получала бинарый файл и максимальный размер памяти, которую она могла выделить под массив:

void ext_sort(const std::string filename, const size_t memory)

Я использовал алгоритм из Effective Performance of External Sorting with No Additional Disk Space:

1. Разделим файл на блоки, которые помещаются в доступную память. Обозначим эти блоки Block_1, Block_2, …, Block_(S-1), Block_S. Установим P = 1.
2. Читаем Block_P в память.
3. Отсортируем данные в памяти и запишем назад в Block_P. Установим P = P + 1, и если P ≤ S, то читаем Block_P в память и повторяем этот шаг. Другими словами, отсортируем каждый блок файла.
4. Разделим каждый блок на меньшие блоки B_1 и B_2. Каждый из таких блоков занимает половину доступной памяти.
5. Читаем блок B_1 блока Block_1 в первую половину доступной памяти. Установим Q = 2.
6. Читаем блок B_1 блока Block_Q во вторую половину доступной памяти.
7. Объеденим массивы в памяти с помощью in-place слияния, запишем вторую половину памяти в блок B_1 блока Block_Q и установим Q = Q + 1, если Q ≤ S, читаем блок B_1 блока Block_Q во вторую половину доступной памяти и повторяем этот шаг.
8. Записываем первую половину доступной памяти в блок B_1 блока Block_1. Так как мы всегда оставляли в памяти меньшую половину элементов и провели слияние со всеми блоками, то в этой части памяти хранятся M минимальных элементы всего файла.
9. Читаем блок B_2 блока Block_S во вторую половину доступной памяти. Установим Q = S −1.
10. Читаем блок B_2 блока Block_Q в первую половину доступной памяти.
11. Объеденим массивы в памяти с помощью in-place слияния, запишем первую половину доступной памяти в блок B_2 блока Block_Q и установим Q = Q −1. Если Q ≥ 1 читаем блок B_2 блока Block_Q в первую половину доступной памяти и повторяем этот шаг.
12. Записываем вторую половину доступной памяти в блок B_2 блока Block_S. Аналогично шагу 8, тут хранятся максимальные элементы всего файла.
13. Начиная от блока B_2 блока Block_1 и до блока B_1 блока Block_S, определим новые блоки в файле и снова пронумеруем их Block_1 to Block_S. Разделим каждый блок на блоки B_1 и B_2. Установим P = 1.
14. Читаем B_1 и B_2 блока Block_P в память. Объеденим массивы в памяти. запишем отсортированный массив назад в Block_P и установим P = P +1. Если P ≤ S, повторяем этот шаг.
15. Если S > 1, возвращаемся к шагу 5. Каждый раз мы выделяем M минимальных и максимальных элементов, записываем их в начало и конец файла соответственно, а потом делаем то же самое с оставшимися элементами, пока не дойдем до середины файла.

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

Реализуем алгоритм на C++.