«И плохой генератор ПСЧ на что-нибудь годится»

Полумесяц с ретортой

В процессе работы над одной задачей возник неожиданный побочный эффект. Визуализация хорошего генератора псевдослучайных чисел представляет собой шум и\или путаницу. Заведомо плохой никто не хочет применять даже для тестов. Мне было все равно, примененный очень простой генератор меня вполне удовлетворял и при аккуратном обращении с ним выдавал приемлемый результат. И вдруг будто-то кто-то уверенным росчерком стал выдавать изящные абстрактные рисунки.
Всего 22 точки соединены кривыми Безье и такой забавный результат. Загогулины можно бесконечно генерировать и за ними, как за облаками, не надоедает наблюдать. Можно придумать интересную игру — разгадать, что же выдала на сей раз нам случайность, какая в ней есть закономерность и придумать ей название.
Но у этих кривых есть и более практическое значение. Генератор представляет собой произведение младшей и старшей части счетчика тиков процессора, от которого взят беззнаковый остаток. Если генерировать числа достаточно редко, случайность получается терпимой. Здесь числа генерируются часто, случайность плохая, что и видно по формам загогулин. Несмотря на потенциальное количество 200 в 22 степени разных загогулин, чаще всего повторяются определенные элементы.
Предположительно, степень «лохматости» фигуры, зависит от нагрузки на систему в те микросекунды, когда генерировались числа. Диагональная линия, ака «путешественник» говорит о почти линейной зависимости случайных числе от времени и малой нагрузке на систему. «Скалярия» — о большей случайности, а значит достаточно высокой нагрузке…
Для тех, кто захочет развлечься лиловыми загогулинами, ниже приведен код и несколько ярких представителей.

Concise Binary Object Representation (сжатое бинарное представление объекта) — формат данных, который был спроектирован таким образом, чтобы обеспечить максимально простой код реализации, формирования компактных выходных данных и возможность расширения формата без необходимости обмена информацией о версии.

Стандарт формата CBOR был официально анонсирован комитетом IETF в октябре 2013 года в новом документе RFC 7049, авторами которого являются Carsten Bormann и Paul Hoffman. Взглянув на имя первого автора, можно предположить другую причину происхождения аббревиатуры для названия формата, но возможно это просто совпадение. Формат CBOR получил MIME-тип application/cbor.

На данный момент существует, вероятно, сотни всевозможных бинарных форматов для представления структурированных данных, ряд которых стандартизирован, популярен и широко применяется (например, BER и DER для ASN.1, MessagePack и BSON). Все существующие стандарты решают поставленные перед ними задачи, и CBOR здесь не исключение. К формату было предъявлено семь важных требований, и, поскольку ни один из существующих форматов в полной мере не мог им удовлетворить, был создан новый (да, тут напрашивается картинка ).

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

• Работал бы гарантированно за 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), в которой описан алгоритм со всеми тремя свойствами.

Egghead.io — проект, созданный Джоном Линдвистом (John Lindquist), цель которого создание видео курсов. Как утверждает автор, он никогда не был доволен существующими реализациями сайтов с видео уроками. Поэтому главной его задачей стало применение лучших практик для организации и подачи обучающих видео материалов в сети.
Пока сам ресурс находится в стадии доработки и нуждается в качественном дизайне. Но уже сейчас доступен первый курс видео туториалов по AngularJS.
Проект получил множество хороших отзывов сообщества, также был упомянут в рассылке javascript weekly и на странице javascript в google+.

Построение lock-free структур данных зиждется на двух китах – атомарных операциях и способах упорядочения доступа к памяти. В этой статье речь пойдет об атомарности и атомарных примитивах.

Анонс. Спасибо за теплый прием Начал! Вижу, что тема lock-free интересна хабрасообществу, это меня радует. Я планировал построить цикл по академическому принципу, плавно переходя от основ к алгоритмам, попутно иллюстрируя текст кодом из libcds. Но часть читателей требует зрелищ не мешкая показать, как пользоваться библиотекой, особо не рассусоливая. Я согласен, в этом есть свой резон. В конечном счете, и мне не так интересно, что там внутри boost, — опишите, как его применять! Поэтому свой эпический цикл я разделю на три части: Основы, Внутри и Извне. Каждая статья эпопеи будет относится к одной из частей. В Основах будет рассказываться о низкоуровневых вещах, вплоть до строения современных процессоров; это часть для почемучек вроде меня. Внутри будет освещать интересные алгоритмы и подходы в мире lock-free, — это скорее теория о том, как реализовать lock-free структуру данных, libcds будет неисчерпаемым источником C++ кода. В Извне будут статьи о практике применения libcds, — программные решения, советы и FAQ. Извне будет питаться вашими вопросами/замечаниями/предложениями, дорогие хабражители.

А пока я судорожно готовлю начало Извне, — первая часть Основ. Статья во многом не о C++ (хотя и о нем тоже) и даже не о lock-free (хотя без atomic lock-free алгоритмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых проблемах, возникающих при использовании таких примитивов.
Атомарность — это первый круг ада низкий уровень из двух.

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

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

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

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

PHP один из самых широко используемых языков для создания вебсайтов. PHP фреймворки, такие как Zend, CakePHP, CodeIgniter и т.д и open source классы и библиотеки упростили разработку.
Независимо от того, являетесь ли вы опытным разработчиком или новичком, инструменты, которые вы используете, имеют прямое влияние на вашу продуктивность. Здесь собран список действительно полезных утилит и расширений для PHP разработчиков, которые помогут ускорить разработку, и улучшит итоговое качество кода.

Так уж повелось, что программисты закрепляют удачные решения в виде шаблонов проектирования. По шаблонам существует множество литературы. Классикой безусловно считается книга Банды четырех «Design Patterns» by Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides" и еще, пожалуй, «Patterns of Enterprise Application Architecture» by Martin Fowler. Лучшее из того, что я читал с примерами на PHP – это «PHP Objects, Patterns and Practice» by Matt Zandstra. Так уж получилось, что вся эта литература достаточно сложна для людей, которые только начали осваивать ООП. Поэтому у меня появилась идея изложить некоторые паттерны, которые я считаю наиболее полезными, в сильно упрощенном виде. Другими словами, эта статья – моя первая попытка интерпретировать шаблоны проектирования в KISS стиле.
Сегодня речь пойдет о том, какие проблемы могут возникнуть с инициализацией объектов в ООП приложении и о том, как можно использовать некоторые популярные шаблоны проектирования для решения этих проблем.

Преподаватель из Стэнфордского университета Кит Шварц (Keith Schwarz) уже несколько лет пополняет свой архив интересного кода — образцы самых лучших алгоритмов и структур данных, когда-либо изобретённых человечеством (Шварц весьма амбициозно оценивает свою коллекцию).

Примеры на сайте преимущественно закодированы в C++, поскольку STL предоставляет прекрасную базу для выражения алгоритмов, работающих с различными типами данных. Структуры данных реализованы на Java.

Кит Шварц дает разрешение использовать свой код всем желающим без всяких ограничений.

Одним из самых больших нововведений в PHP 5.5 будет поддержка генераторов и корутин (сопрограмм). Генераторы уже достаточно были освещены в документации и в нескольких других постах (например в этом или в этом). Сопрограммы же получили очень мало внимания. Это гораздо более мощный, но и более сложный для понимания и объяснения, инструмент.

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

Генераторы

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

Онлайн-сервисы становятся все популярнее, постепенно усложняя функционал и улучшая интерфейсы. В этой подборке представлены онлайн-инструменты для кодеров.

Cloud9

«Это Google Docs, только для кода» — так говорят о проекте. Облачный сервис вырос из Mozilla Bespin. Основные фишки: SSH, drag-and-drop и возможность разработки оффлайн.

Администраторам Linux писать скрипты на Bash приходится регулярно. Ниже я привожу советы, как можно ускорить эту работу, а также повысить надежность скриптов.

Совет 1

Не пишите скриптов, которые выполняют действия ничего не спрашивая. Такие скрипты нужны довольно редко. А вот всевозможного «добра» для копирования, синхронизации, запуска чего-либо, хоть отбавляй. И если в любимом Midnight Commander Вы вдруг нажали не на тот скрипт, то с системой может произойти все что угодно. Это как правила дорожного движения — «написано кровью».

Совет 2

Отталкиваясь от предыдущего, в начало каждого скрипта неплохо помещать что-то вроде:

read -n 1 -p "Ты уверен, что хочешь запустить это (y/[a]): " AMSURE 
[ "$AMSURE" = "y" ] || exit
echo "" 1>&2

Команда echo, кстати, здесь нужна потому, что после нажатия кнопки <y> у вас не будет перевода строки, следовательно, следующий любой вывод пойдет в эту же строку.

Совет 3

Это ключевой совет из всех. Для того, чтобы не писать каждый раз одно и то же — пользуйтесь библиотеками функций. Прочитав много статей по Bash, я вынужден констатировать, что этой теме уделяется мало внимания. Возможно в силу очевидности. Однако я считаю необходимым напомнить об этом. Итак.
Заведите свою библиотеку функций, например myfunc.sh и положите ее, например в /usr/bin. При написании скриптов она не только поможет сократить ваш труд, но и позволит одним махом доработать множество скриптов, если Вы улучшите какую-либо функцию.
Например, в свете совета 2 можно написать такую функцию:

Введение

jQuery UI больше всего известен как набор готовых виджетов. Главное их преимущество, на мой взгляд, — консистентное API: каждый виджет управляется одинаково. Второе их преимущество — они хранят свое состояние: если повторно навесить виджет на элемент, то результатом будет уже существующий инстанс виджета.
Но jQuery UI — это не только набор окошечек и табов (далеко не всеми любимых). Это еще целая инфраструктура для создания своих виджетов: с удобным консистентным API, с хранением состояния и с возможностью наследования. Как ни странно, это для многих новость, в результате чего и появилась эта статья — так же, как это было новостью для меня всего несколько месяцев назад.

Дабы не было двусмысленностей, обозначу суть. При приёме на новую работу мне дали тестовое задание, которое кратко можно описать так: «Написать аналог Glow для геовизуализации событий входа пользователей в кастомерку интернет-магазина». Проще говоря, необходимо мониторить лог системы на предмет возникновения определенных событий и в случае оных выполнять (в данном случае) отображение точки на карте, которая будет определяться IP-адресом пользователя. Цель реализации: создать приятную на вид «игрушку» для презентационных целей, способную погрузить смотрящего в нирвану гармонии и эстетического наслаждения. Основным условием было использование в процессе разработки стека Java-технологий, чем обусловлено принятие многих решений. Кроме этого, было решено реализовать это в виде одностраничного сайта. А поскольку с Java и web я был знаком крайне поверхностно (писал в основном на C/C++), пришлось многому научиться. Что ж, будем разбираться вместе.

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

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

Курс этот предназначен прежде всего для junior developer'ов и позволяет повысить уровень аргументации в холиварах на тему «почему PHP (Java, Perl, Bash) отстой».

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

Часть первая: Как появлялись языки и зачем
Часть вторая: Принцип сохранения функционала
Часть третья: Синтаксический сахар или история развития языков

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

Возьмем немного функций высшего порядка, добавим частичное применение функций, приправим fold с map-ом и получим Javascript DSL для работы с DOM.

Человеческим языком:
Простое и понятное введение в функциональное программирование на чистом и понятном Javascript.

В отличие от «Через тернии к Haskell» все разжевано (возможно даже слишком) и разложено по полочкам.

Прочтение статьи развоплотит миф о неприменимости ФП в реальной жизни. Вы сможете смотреть на решение одной и той же задачи с разных точек зрения. Прямо как на картинке.