Однажды вечером, сразу после того, как я закончил разбираться с наследованием в JS, мне пришла в голову идея, что пора бы заняться чем-нибудь посложнее — например паттернами. На столе внезапно оказалась книжка Gof, а на экране ноутбука появился труд с названием «JavaScript patterns».

В общем, спустя пару вечеров, у меня появились описания и реализации на JavaScriptе самых основных паттернов — Decorator, Observer, Factory, Mediator, Memoization (не совсем паттерн, а скорее техника, но мне кажется что она прекрасно в этот ряд вписывается) и Singleton.

В апреле-мае 2011 года компания Яндекс проводила очередной тур конкурса Яндекс интернет математика. Тема тура: «Определение визуальной схожести изображений».
Я публиковал новость про объявление победителей и обещал в скором времени описать решение поставленной задачи нашей командой — LookLikeIt, которая заняла 12-е место в финальном рейтинге.

И вот, не совсем скорое время наступило!

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

Buffered Streams

//медленно
InputStream is = new FileInputStream(file);
int val;
while ((val = is.read()) != -1) {
}
//быстро
InputStream is = new BufferedInputStream(new FileInputStream(file));
int val;
while ((val = is.read()) != -1) {
}

Казалось бы — очевидная истина, неправда ли? Но как показал чужой код и опыт собеседования кандидатов, часть разработчиков определенно не понимает в чем преимущество буферизованных стримов. Кто до сих пор не разобрался — метод read() класса FileInputStream:

public native int read() throws IOException;

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

System.arraycopy(src, srcPos, dest, destPos, length);

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

Триггер — это хранимая процедура, которая не вызывается непосредственно, а исполняется при наступлении определенного события ( вставка, удаление, обновление строки ).
Поддержка триггеров в MySQL началась с версии 5.0.2

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

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

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

В качестве первого пришедшего в голову «интересного» была идея как-то визуализироать весь этот поток абсолютно бесполезной информации, который создается большинством пользователей твиттера, а тут еще как раз удачно в памяти всплыл Ball Pool.

Приветствую вас, хабрачитатели!

Продолжаю попытки визуализировать структуры данных в Java. В предыдущих сериях мы уже ознакомились с ArrayList и LinkedList, сегодня же рассмотрим HashMap.



HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Разрешение коллизий осуществляется с помощью метода цепочек.

Уверен, каждый из читателей, знает что такое шаблон проектирования “Singleton”, но не каждый знает как его программировать эффективно и правильно. Данная статья является попыткой агрегирования существующих знаний по этому вопросу.

Кроме того, можно рассматривать статью как продолжение замечательного исследования, публиковавшегося на Хабрахабре ранее.

Приветствую вас, хабражители!

Продолжаю начатое, а именно, пытаюсь рассказать (с применением визуальных образов) о том как реализованы некоторые структуры данных в Java.



В прошлый раз мы говорили об ArrayList, сегодня присматриваемся к LinkedList.

LinkedList — реализует интерфейс List. Является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. Реализует методы получения, удаления и вставки в начало, середину и конец списка. Позволяет добавлять любые элементы в том числе и null.

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

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

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

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

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

Приветствую вас, хабралюди!

Взбрело мне в голову написать несколько статей, о том как реализованы некоторые структуры данных в Java. Надеюсь, статьи будут полезны визуалам (картинки наше всё), начинающим java-визуалам а также тем кто уже умеет писать new ArrayList(), но слабо представляет что же происходит внутри.



Сегодня поговорим о ArrayList-ах

ArrayList — реализует интерфейс List. Как известно, в Java массивы имеют фиксированную длину, и после того как массив создан, он не может расти или уменьшаться. ArrayList может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта. Элементы ArrayList могут быть абсолютно любых типов в том числе и null.

При попытке отредактировать этот старый пост слетело всё форматирование. Может быть я его когда-нибудь исправлю.

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

Основные преимущества:

• Делая push из удалённой копии мы автоматически обновляем live-копию сайта
• Правки файлов на сервере не будут разрушать историю коммитов
• Простота, не нужны особые правила выполнения коммитов
• Можно применить к уже запущенному сайту, без повторного деплоя или перемещения файлов

Привет, %хаброюзер%!

Сегодня я поделюсь с вами своим опытом прохождения собеседований на вакансии PHP-программиста в «белокаменной»Москве.

    Действительно, в интернете сейчас можно найти достаточно много информации о настройке GIT и работе с ним, но недостаточно освещен вопрос коллективной разработки и «рабочего процесса» отдельно взятого проекта от начала и до конца.

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

Год назад мы с командой решили перейти с SVN на Git. Зачем это было надо — писать не буду, т.к. на эту тему уже и так много написано. А хочу я описать типичные алгоритмы работы, понятные человеку, который долгое время пользовался SVN. Ниже — памятка, написанная для команды год назад, чтобы легче было мигрировать. Надеюсь, кому-нибудь пригодится.

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

В данной статье описывается возможная реализация нечеткого поиска, которая была применена для поиска на сайте edatuda.ru.

Морфологический анализатор для русского языка — это что-то заумное? Программа, которая приводит слово к начальной форме, определяет падеж, находит словоформы — непонятно, как и подступиться? А на самом деле все не так и сложно. В статье — как я писал аналог mystem, lemmatizer и phpmorphy на Python, и что из этого получилось.

Прошли те времена, когда каждый форум на персональной страничке каждого Васисуалия Свердыщенко требовал отдельной регистрации.
Мы потихонечку привыкаем к тому, что оставить комментарий от имени своего OpenID/OAuth провайдера можно фактически везде. Также для всех популярных CMS давно написаны плагины сквозной авторизации Twitter/Facebook/Google/Яndex/Вконтакте. Кроме того есть DISQUS… Но что делать, если мы хотим предоставить пользователю стороннего сервиса какие-то дополнительные полномочия, не вынуждая его заводить отдельную учетную запись на нашем сайте? Особенно, если для нашей CMS пока нет чудо-плагина?
Я расскажу о том, как быстро и безболезненно прикрутить сквозную авторизацию к экзотической CMS и какие на этом пути встречаются подводные грабли.

Введение

Недавно наткнулся на статью, размещенную на Хабрахабре, посвященную сравнению изображений «Выглядит похоже». Как работает перцептивный хэш. Так как я сам достаточно долго занимался этой тематикой (являюсь автором программы AntiDupl), то мне захотелось поделиться здесь своим опытом по данному вопросу. В статье я приведу два варианта алгоритма сравнения похожих изображений — базовый и улучшенный. Все они были проверены автором на практике в рамках указанного выше проекта. Изложение мое будет вестись без строгих доказательств, сложных формул и специальной математической терминологии. Надеюсь, что читатели простят меня за это.

Базовый Алгоритм

Мера схожести изображений

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

Привет, Хабражитель!

Многие люди мечтают научиться писать программы, игры, но не получается по многим причинам. Я, изначально, не хотел ничего писать потому что не было интересной платформы, и я был еще слишком маленьким. Потом все изменилось. Наступила новая эра в телефонной индустрии – появился iPhone. Я сразу, как о нем услышал, загорелся желанием его приобрести. Платформа сразу понравилась, кнопок и стилуса нет – самое то для игр.
Программы я начал писать в ноябре 2009, если их можно назвать программами :). Многие спрашивают как я учился – на видео-уроках с YouTube, а как еще? Читать непонятные уроки по iPhone SDK? В тот момент я загорелся идеей учить таких же как я – начал записывать видео на YouTube новым для меня темам.
Если интересно: http://bit.ly/pdyoutube. Потом все пошло и поехало, сам стал лучше программировать и запоминалось все намного лучше. Не буду писать очень длинное вступление – перейдем к самому интересному.

Всегда хотел делать игры, но на пустом Xcode не очень удобно и понятно. Стал выбирать платформу (фреймворк) для разработки игр под iPhone, iPad. Мой выбор остановился на Cocos2D. Многие спросят почему – он очень простой в использовании, очень! Он еще и бесплатный и часто обновляемый!