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

Вопрос: Почему поиск в python dict на больших объемах данных быстрее чем итерация по индексированному массиву?

Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!

На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) — так как в основе dict питона лежит структура под названием Hash Table.

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

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

Методов разбора существует множество (рекомендую следующий обзор Dick Grune, Ceriel J. H. Jacobs — Parsing Techniques: A Practical Guide, ISBN 0-13-651431-6). Причём реализации методов варьируются от полностью ручных до использования автоматизированных генераторов, таких как bison, antlr, lemon и других.
В то время, как ручное написание лексических и синтаксических (далее я буду называть из лексер и парсер) разборов позволяет достичь максимальной скорости и контроля (особенно над ошибками и способами их преодоления), использование генераторов позволяет сосредоточиться непосредственно на задаче, облегчает модификацию грамматики и бережёт время. Умение владеть такими инструментами позволяет чаще прибегать к DSL (Domain Specific Language) и вообще видеть возможность их применения.

Я хочу привести пример использования bison (парсер) и flex (лексер) в реальной жизни: от возникновения задачи, до её решения.

     Знание структуры машинных команд уже много лет не является обязательным, для того, чтобы человек мог назвать себя программистом. Естественно так было не всегда. До появления первых ассемблеров программирование осуществлялось непосредственно в машинном коде. Каторжная работа, сопряженная с большим количеством ошибок. Современные ассемблеры позволяют (в разумной степени) абстрагироваться от железа, метода кодирования команд. Что уж говорить о компиляторах высокоуровневых языков. Они поражают сложностью своей реализации и той простотой, с которой программисту позволяется преобразовывать исходный код в последовательность машинных команд (причем преобразовывать, в достаточной степени, оптимально). От программиста требуется лишь знание любимого языка/ IDE. Знание того, во что преобразует компилятор исходный листинг вовсе не обязательно.
Тем же, кому интересно взглянуть на краткое описание структуры кодирования машинных команд, пример реализации и исходный код дизассемблера для x86 архитектуры, добро пожаловать.

Доброго времени суток.
Многим web-программистам рано или поздно нужно работать с видео. Такая задача возникла и у меня.
В Интернете есть много статей на форумах и блогах, как на русскоязычных, так и на зарубежных сайтах. Но, проделавши, так же как и предлагалось в инструкциях — результата ожидаемого не дало. Что и послужило поводом для этой статьи. Думаю, она поможет таким же как и я многим начинающим.

Задача

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

Добрый день. Хочу предложить вам небольшую статью о своей работе с кинектом.

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

Помните этот пост? У меня он сразу попал в закладки, а уже на следующий день я с огромным удовольствием читал свежераспечатанную книгу. Сколько их (распечатанных книг) было — уже не помню. Но уверен, что не я один этим занимался. А что? Не всегда есть в продаже книга, которая нужна прям сейчас. Да и средства экономит.

Тот, кто пробовал сам распечатывать книги, знает, что процесс печати требует внимательности и аккуратности. Печатаем по 16 страниц (4 листа формата А4, по 2 страницы книги на каждой стороне листа) таким образом чтобы, сложив пополам эту стопку, получить тетрадку, в которой страницы идут по порядку, как в книге. Из этих тетрадок потом и будет сшиваться сама книга.

Привет, Хабраюзеры!

С Вами я, создатель и разработчик Playble.

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

Для справки:
Playble — это мультимедийная поисковая система в реальном времени, которая ищет торренты, фильмы онлайн, и музыку по крупнейшим русскоязычным сайтам.

Привет, %username%.

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

Введение

Для начала рассмотрим, как устроено стереоизображение и как на него смотреть.

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

Под катом — пример реализации алгоритма на биграммах, исходники и результаты его работы.

Привет, хабр!

О StartSSL я узнал от небезызвестного lissyara, в связи с чем ему очень благодарен.

Для начала расскажу, что же за зверь это. Как известно, SSL сертификаты выдаются центрами сертификации, чьи корневые сертификаты хранятся в хранилище сертификатов браузера\ОС (либо другого ПО, использующего SSL). Цена на большинство сертификатов зашкаливает, и платить приходится за каждый сертификат. Но у StartSSL весьма интересный подход — сами сертификаты у них бесплатные, вы платите только за проверку вашей личности.

Так же не может не радовать наличие русскоязычной поддержки.

2го сентября 2011 года в Royal Festival Holl лондонский филармонический оркестр исполнил композиции из популярных компьютерных игр. Это представление стало частью фестиваля Vision Sound Music

Видео анонса:



Под катом список композиций.

Похоже, что всё сегодня переходит в «облака», которые являются туманным термин для определения программных приложений и хранилищ данных, размещенных на удаленных серверах где-то далеко по всему Интернету. Так что, если всё наше ПО переходит на облака, то почему бы не перейти инструментам, используемым для создания этого ПО? Ну, а некоторые инструменты, есть там прямо сейчас. Черт, даже GitHub недавно добавил базовые возможности редактирования. В этой статье мы рассмотрим некоторые многообещающие Онлайн-IDE.

Доброго времени суток!
Когда-то, благодаря этому топику, был написан неплохой парсер для Лостфильма. Сейчас я хотел бы поделиться собственной доработкой скрипта, связанной с изменением формата ссылок на Лостфильме, добавлением проверки на обновление ленты и проверки скачанного.

Прежде всего, что-бы снизить нагрузку на RSS сервер, при запросе ленты с помощью wget нужно использовать «If-Modified-Since:». Тогда, при отсутствии обновлений, мы не будем качать и обрабатывать всю ленту. Такой подход снизит нагрузку на сервер (и немного на наш компьютер).
Используем следующий вариант команды:

# Подготовка заголовка If-Modified-Since
lastmod="$( grep -m 1 Last-Modified response.out )"

header="If-Modified-Since:"${lastmod#*:}


Вступление

Kango позволяет создавать расширения для популярных браузеров используя только JavaScript, причем код един для всех браузеров. На данный момент поддерживается Chrome, Firefox, Internet Explorer (в публичном доступе только версия с поддержкой Chrome и Firefox) и ведется работа над поддержкой Opera и Safari. Ниже будет рассмотрено как можно быстро создать простой кроссбраузерный Gmail Checker

Что должно получиться в итоге:

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

Как видно из заголовка, речь пойдет о двух программах:
1. Open Computers and Software Inventory
OCS-Inventory основан на распределяемых модулях, устанавливаемых на инвентаризируемые машины, которые отсылают подробную информацию о системе, подключенных устройствах и установленном ПО в выделенную базу данных.
Поддерживаются следующие OS: Microsoft Windows, Linux, *BSD, Sun Solaris, IBM AIX, HP-UX, MacOS X

2. GPLI — Guestion Libre de Parc Informatique
Проект предназначен для работы с базой данных IT и телекоммуникационного оборудования, установленного на предприятии. Также имеется возможность ведения учета расходных материалов и организации службы технической поддержки по расписанию и по заявкам пользователей.

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

Сейчас наличие нескольких подключений к интернет на одном, в том числе и домашнем сервере — не редкость. Городские локалки, ADSL, 3G модемы… Добавим к этому сети домашние локальные и внешние виртуальные (VPN), и получим ядрёную смесь интерфейсов, между которыми необходимо роутить трафик, балансировать трафик между разными каналами в интернет (когда они есть), и переключаться с нерабочих каналов на рабочие (когда они отваливаются).

Судя по постам в инете, большинство людей, столкнувшихся с этой ситуацией, очень плохо представляет себе, как это настраивается. Надо отметить, что в линухе действительно управление роутингом весьма сложное и запутанное — следствие эволюционного развития и поддержки (частичной) совместимости. Я хочу описать принципы настройки роутинга multihomed серверов на конкретном, достаточно сложном, примере: на сервере три физических сетевых интерфейса (один в домашнюю локалку и два к ADSL-модемам), два ADSL-подключения (ADSL-модемы в режиме bridge, так что pppd поднимает этот же сервер) к разным провайдерам (одно со статическим IP, второе с динамическим), плюс VPN на сервер компании — итого шесть интерфейсов.

Тема достаточно сложная, поэтому для понимания материала потребуется хотя бы минимальное понимание работы роутинга (что такое default route и gateway), файрвола (маркировка пакетов, отслеживание соединений, связь между разными таблицами и цепочками файрвола и роутингом), pppd (скрипты ip-up/ip-down) и протоколов IP и TCP.