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

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

Решил сделать следующую попытку, когда познакомился с детским языком-конструктором Scratch. Это даже не язык — это средство создания скриптов путем перетаскивания на экране «блоков» и соединения их друг с другом. Теперь дело пошло получше. Ребенок смог сделать даже какую-то простую игру. Но ведь нужно двигаться дальше?



Что бы как-то разнообразить «программирование» я придумал сделать машинку, но что бы ее поведением можно было управлять с компьютера программой на Scratch. То есть что бы ребенок смог бы как-то программировать логику поведения машинки.

На днях набрел на хорошую виртуальную клавиатуру. Почему-то я ее раньше нигде не встречал, хотя продукт достойный. Наш, русский, даже имеет патент (РОСПАТЕНТа №2009611147 от 20.02.2009).

Приветствую, Хабрахабр. Сегодня я хочу, в своём обычном стиле, устроить сообществу небольшой ликбез по структурам данных. Только на этот раз он будет гораздо более всеобъемлющ, а его применения и практичность — простираться далеко в самые разнообразные области программирования. Самые красивые применения, я, конечно же, покажу и опишу непосредственно в статье.

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

Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.

Моноид как концепция

Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = a ⊗ b — тоже какой-то элемент этого множества.

Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+": "John" ◦ "Doe" = "JohnDoe". Здесь множество M — строки, а "◦" выступает в качестве операции "⊗".
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так, fst(5, 2) = 5; fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.

Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
(a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.

И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
a ⊗ e = e ⊗ a = a
В примере со строками нейтральным элементом выступает пустая строка "": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь fst(e, a) = e всегда, и если a ≠ e, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :)

Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:

public interface IMonoid<T> {
    T Zero { get; }
    T Append(T a, T b);
}

Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.

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

Не так давно я начал изучать Ruby on Rails 3 и нашел очень интересный плагин для него: Compass. По сути, этот CSS-фреймворк независим от Rails, им можно пользоваться и в других типах проектов.

Расскажу-ка я вам, как Compass облегчил мою жизнь.

В настоящее время я работаю над одним веб-приложением, и вот захотелось мне обновить нынешний, довольно-таки топорный интерфейс на что-то более современное, более красивое. Начать решил с кнопок как с наиболее технически нагруженной части: в них требуется не только заменить внешний вид, но и добавить индикацию нажатия и обработку событий. Сразу же возникла проблема: как обеспечить масштабирование? Обычной растровой картинкой не обойтись, так как у пользователей могут использоваться разные шрифты (как вид, так и размер), и картинка-подложка не будет под них адаптирована. Логично было бы попробовать использовать для этих целей SVG, чем я и занялся.

К сожалению, в конечном итоге я пришёл к выводу, что овчинка не стоит выделки: слишком много проблем вылезло при попытке реализации этой идеи. Тем не менее, я не считаю это время потерянным: я приобрёл новые знания и навыки и теперь хотел бы поделиться ими с сообществом, чтобы облегчить жизнь тем, кто решит повторить мой путь. Описать свои мучения я планирую в двух статьях: в первой — работа над собственно SVG-картинкой, во второй — техника внедрения полученной картинки в качестве кнопок, возникающие при этом проблемы и их решение или обходные пути. Кому интересна первая часть, прошу под кат.

Недавно была выпущена бета-версия Adobe Flash 10.2, которая значительно меньше потребляет ресурсы компьютера и имеет ряд значительных преимуществ. К сожалению, Google Chrome все еще использует стабильную версию Flash. Для тех, кому интересно как переключиться на новую версию прошу под кат.

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

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

Так как большинство авторов не удосуживается хотя бы залезть в документацию, то обычно в таких статьях вся информация базируется на неких слухах и пересказах слухов. Эти слухи бродят по сети и поражают википедию, хабрахабр и другие уважаемые ресурсы. В результате получаются опусы вроде "Вы наверное шутите, мистер Дал, или почему Node.js" (пунктуация автора сохранена): она, в основном, верная по сути, но изобилует неточностями, содержит ряд фактических ошибок и изображает предмет с какого-то непонятного ракурса.

Мне было сложно пройти мимо статьи, изобилующей фразами вроде «эффективные реализации polling'а на сегодняшний день имеются лишь в *nix-системах» (как будто poll() есть где-то, кроме некоторых *nix). Этот пост начинался как комментарий, разъясняющий уважаемому inikulin ошибки в его статье. В процессе написания оказалось, что проще изложить предмет с самого начала, что я собственно и делаю отдельным постом.
В моем очерке нет срыва покровов или каких-то неизвестных трюков, здесь просто описываются преимущества и недостатки разных подходов человеком, который проверял, как всё это работает на практике в разных операционных системах.
Для желающих просветиться — добро пожаловать под кат.

Одна из самых потрясающих вещей в jQuery — это движок селекторов. Доступ к элементам DOM используюя селекторы в jQuery становиться довольно простой задачей, еще и потому, что большинство селекторов используют те же выражения что и селекторы в CSS. Это то что веб-дизайнеры НЕ программисты могут легко усвоить.
Это статья — упражение в создании произвольного слектора, вы можете её использовать, как руководство по созданию своего собственного селектора.

Внимание

Статья содержит информацию об устаревшей версии PHP Console.

О новой версии PHP Console 3.0 читайте тут.

PHP Console 1.0

Речь пойдёт об одном чудном расширении для Google Chrome, которое позволяет проксировать вывод ошибок и дебаг сообщений из PHP в консоль Google Chrome, а также отображать их в виде всплывающих popup-уведомлений.

Есть хорошая статья Питера Норвига, в которой он рассказывает как написать спеллчекер в 20 строк кода. В этой статье он показывает как поисковые системы могут исправлять ошибки в запросах. И делает это довольно элегантно. Однако, у его подхода есть два серьезных недостатка. Во-первых, исправление более трех ошибок требует больших ресурсов. А гугл, кстати, неплохо справляется и с четырьмя ошибками. Во-вторых, нет возможности проверки связного текста.



Итак, хочется исправить эти проблемы. А именно, написать корректор коротких фраз или запросов, который:

• умел бы выявлять три (и более) ошибки в запросе;
• умел бы проверять «разорванные» или «слипшиеся» фразы, например expertsexchange — experts_exchange, ma na ger — manager
• не требовал много кода для реализации
• мог бы достраиваться до исправления ошибок на других языках и других типов" ошибок

Остальное — под катом.

Недавно столкнулся с задачей прикручивания достаточно необычного шрифта для мобильного веб клиента. Так как работа была под айфон, то я решил, что в этой задаче мне поможет css 3 и такая штука как @font-face. Пользу от такого способа решения задачи, я думаю, видят все, потому что:

• сохраняется поиск по тексту, потому что это текст, а не картинка;
• появляется возможность использовать онлайн-переводчики и разные фишки связанные с текстом;
• никто не отменяет для нас использование line-height, letter-spacing, text-shadow,text-align, и селекторов вида ::first-letter и ::first-line

О визуализация графов в вебе говорили здесь, навеяно этой статьей.

Под катом обзор JavaScript библиотек для рисования графов, диаграмм и прочей красоты.

Многие интернет провайдеры предоставляют для своих абонентов такой сервис, как торрент-ретрекер. Некоторые торрент-трекеры (в том числе и rutracker.org) в свои торрент-файлы добавляют информацию о таком таком универсальном ретрекер как retracker.local. Но в современных дистрибутивах (таких как Ubuntu, openSUSE и т.д.) этот адрес не резолвится правильно.

Проблема заключается в использовании сервиса avahi для анонсирования ресурсов компьютера в локальной сети, так как для этих целей используется зона .local. Чтобы решить эту проблему не обязательно избавляться от avahi. Достаточно указать, что если не удается найти поддомен, спросить об этом dns.

В серии статей от tyomitch «Компиляция» (тут, тут, тут, тут, тут и здесь) было рассмотрено построение транслятора игрушечного языка jsk, описанного в 4 части.
В качестве back-end для этого транслятора tyomitch предложил реализацию байт-кода и интерпретатор этого байт-кода.

На мой взгляд, более разумным подходом было бы использование существующих решений для backend, например llvm, и следуя принципу «Критика без конкретных предложений — критиканство», я предлагаю вариант реализации этого маленького языка jsk с llvm.

Что это даст для jsk? Настоящую компиляцию, то есть результатом будет исполняемый файл, который не зависит ни от каких runtime, возможность серьезной оптимизации, профилирования кода и автоматически получим документацию по back-end (что облегчит сопровождение).

Summary

Announced: 2010-05-20
Credits: 80sec
Affects: сайты на ngnix+php с возможностью загрузки файлов в директории с fastcgi_pass

Background

Зачастую How-To по настройке связки nginx с php-fpm / php-cgi есть подобные строчки:

location ~ \.php$ {
    fastcgi_pass 127.0.0.1:9000;
    fastcgi_index index.php;
    fastcgi_param SCRIPT_FILENAME /scripts$fastcgi_script_name;
    include fastcgi_params;
}

В наше время все большую популярность набирают генетические алгоритмы. Их используют для решения самых разнообразных задач. Где-то они работают эффективнее других, где-то программист просто решил выпендриться…

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

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

Как это все выглядит вы можете увидеть на следующем рисунке:

Перевод статьи Тима Ферриса из его блога.


(Учебник Дзюдо Окано Исао, который я использовал для изучения японской грамматики)

Изучение языка не должно быть сложным.

Принципы когнитивной нейронауки и управления временем могут быть применены для достижения свободного владения языком на разговорном уровне (в данном случае определяется как 95%+ процентов понимания и 100% выразительных возможностей) в течение 1-3 месяцев.

Перевод статьи Sara Golemon «Extension Writing Part I: Introduction to PHP and Zend».