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

• Алгоритм закраски с затравкой
• Алгоритмы со списком рёберных точек
• Алгоритмы XOR

Некоторое время назад я публиковал статью о самодельных микропроцессорах, сегодня же мы затронем более сложную и щекотливую тему (особенно в свете событий на Фокусиме) – создание ядерного реактора, способного генерировать энергию в домашних условиях. И перед тем как вы начнете волноваться, вспоминая о негативных опытах в прошлом (см. Радиоактивный бойскаут – наковырявший прилично амерция-241 из детекторов дыма) заранее скажу, что все что описано в этой статье – относительно безопасно (по крайней мере не опаснее работы с фтороводородной кислотой дома), но крайне не рекомендуется к повторению. Перед любыми действиями проконсультируйтесь со своим адвокатом — законы разные в разных странах. Много кто уже сидит.

Введение

Многие уже знакомы с таким термином, как синглтон. Если описать вкратце, то это — паттерн, описывающий объект, у которого имеется единственный экземпляр. Создать такой экземпляр можно разными способами. Но сейчас пойдет речь не про это. Я также опущу вопросы, связанные с многопоточностью, хотя это очень интересный и важный вопрос при использовании данного паттерна. Рассказать бы я хотел о правильном использовании синглтона.

Любой программист, изучающий haskell, рано или поздно встречается с таким непостижимым понятием как монада. Для многих знакомство с языком заканчивается монадами. Существует множество руководств по монадам, и постоянно появляются новые (1). Те немногие, кто понимает монады, тщательно скрывают свои знания, объясняя монады в терминах эндофункторов и естественных преобразований (2). Ни один опытный программист не может найти монадам место в своей устоявшейся картине мира.

В результате java-программисты только посмеиваются над хаскелем, не отрываясь от своего миллионострочного энтерпрайзного проекта. Разработчики на С++ патчат свои сверх-быстрые приложения и придумывают ещё более умные указатели. Веб-разработчики листают примеры и огромные спецификации по css, xml и javascript. А те из них, кто в свободное время изучает haskell, сталкивается с труднопреодолимым препятствием, имя которому монады.

Итак, узнаем как программировать на хаскеле без монад.

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

… которая представляет из себя кучу мусора из старых добрых простых данных!

Недавно на хабре появилось сразу два материала, посвященных языкам из «большой четверки тьюринговых трясин»: про алгоритм Маркова и Brainfuck. Думаю, для полноты картины будет интересно сравнить эти эзотерические системы с еще одним важным алгоритмическим примитивом — машиной Поста, которой я как раз занимаюсь.

Машина Поста (wiki; для простоты оттуда же взят вариант синтаксиса) похожа на всем известную машину Тьюринга, однако обладает интересными особенностями. Она содержит лишь 6 команд, кроме того, в ячейки-биты памяти могут записываться лишь 2 символа (двоичное кодирование информации). «Естественно», никакой дополнительной памяти, не зря же эзотерикой зовется!

Таким образом, при программировании на машине Поста помимо необходимости совладать с оккамовским синтаксисом надо думать о том, как записать на ленте все промежуточные результаты, не потеряв по пути обратную тропинку к остаткам входных данных. Почему «остаткам»? Зачастую ввиду отсутствия дополнительной памяти приходится обрабатывать входные данные итеративно (а иногда и рекурсивно). Надеюсь, вышеизложенное убедительно доказывает, что написание привычных алгоритмов на машине Поста — неплохая разминка для мозгов и весьма увлекательное занятие.

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

Для начала вкратце о задаче и о самом алгоритме:

Для просмотра разной внешней документации (man/perldoc/pydoc/etc.) в Vim есть множество плагинов и рецептов. Проблема в том, что одни не настраиваются на открытие окон с документацией удобным мне способом, другие не расширяются для поддержки новых источников документации, третьи глючат и написаны слишком криво чтобы их можно было относительно просто пофиксить и выслать патч автору. На днях меня эта ситуация окончательно достала, и я написал плагин viewdoc, решающий все эти проблемы.

Он прост внутри и удобен в использовании, предоставляет единый пользовательский интерфейс для работы с любой документацией (включая встренный :help), умеет определять требуемую документацию по контексту, гибко настраивается, и очень просто расширяется (внешними плагинами или прямо в ~/.vimrc) для добавления новых источников документации. Основной недостаток — тестировался только в linux, может работать в других *nix, точно не будет работать в винде.

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

На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.

После возни с трехмерной игрой «Жизнь» я вспомнил о том, что для обычной, конвеевской версии этой игры существует алгоритм под названием «Hashlife». Он несколькими фразами описан в Википедии, и приведенной там картинки с комментарием («конфигурация через 6 октиллионов поколений») для меня было достаточно, чтобы держаться от этой идеи подальше: сколько же ресурсов нужно этому алгоритму? Стоит ли за него браться вообще?

Общая идея алгоритма такая.

Допустим, что у нас есть квадрат поля размером N*N (N>=4 – степень двойки). Тогда мы можем однозначно определить состояние его центральной области размером (N/2)*(N/2) через T=N/4 шага. Если мы запомним состояние исходного квадрата и результат его эволюции в словаре, то сможем в следующий раз, встретив такой квадрат, сразу определить, что с ним станет.

Предположим, что для квадратов N*N эволюцию на N/4 шага мы считать умеем. Пусть у нас есть квадрат 2N*2N. Чтобы просчитать его развитие на N/2 шагов, можно сделать следующее.

Разобьем квадрат на 16 квадратиков со стороной N/2. Составим из них 9 квадратов со стороной N, для каждого из них найдем результат эволюции на N/4 шага. Получится 9 квадратов со стороной N/2. В свою очередь, из них составим уже 4 квадрата со стороной N, и для каждого из них найдем результат эволюции на N/4 шага. Полученные 4 квадрата со стороной N/2 объединим в квадрат со стороной N – он и будет ответом.

Чтобы управлять доступом можно использовать различные решения gitosys, gitolite, mercurial-server, но эти решения работают через SSH, что не всегда удобно (должен быть ключ). В добавок не хватает гибкости у подобных решений.

Основные требования:

• доступ по логину/паролю (HTTPS)
• контроль прав на чтение/запись
• публичный/приватный репозиторий
• управления всем через веб интерфейс
• все данные (информация о проекте и пользователях) должны храниться в базе (MySQL)

Для решения этой задачи сделал следующую систему…

Статья "Недопонимание CAP-теоремы" и комментарии к ней свидетельствуют, что непонимание действительно есть. И связано оно не только с неправильным толкованием термина «partitioning», но и с ментальными ошибками на других уровнях. Попробую внести ясность.

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

Способов хостинга mercurial репозиториев достаточно, но я сочинил именно такой вариант по следующим причинам:

1. nginx: мало кушает, быстро работает — скорость
2. supervisor: мониторит процесс, перезапускает если что — надёжность
3. gunicorn: wsgi, большие возможности по настройке — эффективность

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

Если вас заинтересовала тема, то конкретные инструкции и конфиги — под катом.

В последнее время я довольно часто натыкаюсь на данную теорему. Она довольно давно доказана и про нее много чего написано. Однако каждый раз когда я натыкаюсь на распределенную систему, претендующую в описании на CA в терминах данной теоремы, т.е. систему в которой жертвуют Partition Tolerance в угоду Consistency и Avalability, я зависаю, так как хоть убейте не могу себе представить такого зверя. После долгих раздумий я все же пришел к выводу, что такая система бессмысленна, о чем и хочу порассуждать в данном топике.

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

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

Каким же должен быть полный ответ на вопрос про деструкторы?

Некоторое время назад озадачился поиском способа развертывания проектов Django, к которому предъявлялись два требования:

1. Удобное управление запуском/остановкой/перезапуском нескольких проектов на одном хосте
2. Поддержка разных виртуальных сред для разных проектов

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

Введение

Это статья написана, чтобы иллюстрировать применение возможностей Common Lisp к типичным задачам веб-разработки.

Я постараюсь показать, как на лиспе реализовываются основные применяемые в веб-программировании вещи — шаблонизация, роутинг и кеширование. Также я оставил немножко места для макросов.

Статья в большой степени учебная, тем не менее это вполне работающий веб-сайт — rigidus.ru

Введение

Эта вводная статья предназначена для желающих попробовать применить Common Lisp в задачах веб-программирования. Я не буду останавливаться на преимуществах этого языка, за меня это сделал ababo в своем вводном посте Разработка web-приложений на языке Common Lisp (часть первая)

Я занимаюсь вопросами разработки веб-приложений на Common Lisp немногим более года и сделал на Common Lisp крупный интернет-магазин, что, как мне кажется, предупредит возражения тех, кто считает, что лисп бесполезен для коммерческого применения.

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

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

Для тех, кто любит проматывать скучные процедуры установки — в конце статьи размещена небольшая вкусность, которая, возможно, расширит ваш взгляд на веб-программирование, если до этого момента вы не имели дела с лиспом. Ищите по ключевым словам SLIME и SWANK :)