Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

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

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

У нас есть некоторый диапазон чисел от 0 до N, надо написать две функции int alloc() и free(int). Первая выбирает один из свободных идентификаторов из диапазона [0, N), а вторая соответственно — «возвращает» его для повторного использования(полагаем, что число N достаточно мало, что бы идентификаторы могли закончится если их не возвращать, но больше чем число выделенных в каждый конкретный момент времени идентификаторов). При этом на «нижнем уровне» у нас есть только DHT. Нету блокировок, и, кроме того, от алгоритмов требуется отказоустойчивость — если какой-то из узлов кластера «сложится» во время выполнения алгоритма поведение системы должно быть предсказуемо. Если задача интересна, а также интересно узнать почему отказоустойчивый сервис с такой сигнатурой невозможно корректно использовать, и как надо исправить сигнатуру что бы это стало возможно — добро пожаловать под кат.

В далеком 2009 году на хабре уже была статья "Кузявые ли бутявки.." про pymorphy — морфологический анализатор для русского языка на Python (штуковину, которая умеет склонять слова, сообщать информацию о части речи, падеже и т.д.)

В 2012м я начал потихоньку делать pymorphy2 (github, bitbucket) — думаю, самое время представить эту библиотеку тут: pymorphy2 может работать в сотни раз быстрее, чем pymorphy (втч без использования C/C++ расширений) и при этом требовать меньше памяти; там лучше словари, лучше качество разбора, лучше поддержка буквы ё, проще установка и более «честный» API. Из негатива — не все возможности pymorphy сейчас реализованы в pymorphy2.

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

Если ты всегда мечтал написать свой язык программирования — добро пожаловать. Здесь ты наверняка найдёшь для себя что-нибудь интересное.

GitHub-юзер yawnt собрал чудесную подборку ссылок для любителей драконов, языков и прочих вкусных внутренностей. А знающие камрады в комментариях наверняка поделятся с тобой и другими яствами.

Пишет yawnt следующее:

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

Я не включил (и не собираюсь) в список ссылки на официальную документацию, т. к. считаю очевидным, что первым делом следует смотреть именно туда ;P.

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

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

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

Постановка задачи

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

1. Есть возможность удостовериться, что каждый подписант принадлежит к указанному кругу лиц.
2. Есть возможность проверить, что большинство подписей принадлежат разным лицам.
3. Нет возможности определить, кому именно принадлежит та или иная подпись.
4. Нет возможности определить, оставляло ли данное конкретное лицо свою подпись или нет.
5. Любой подписант может по своему желанию поставить вместо анонимной подписи персонализованную.
6. Любой анонимный подписант может впоследствии по своему желанию предоставить доказательства того, что именно он поставил подпись.

Система основана на асимметричной криптографии, алгоритмах цифровой подписи и сертификации ключей.

Можешь выбрать подходящую к заголовку поста картинку?

Тогда научи робота! Он тоже хочет.

Команда проекта Открытый корпус просит хабралюдей помочь разметить свободно доступный (CC-BY-SA) корпус текстов. Под катом мы расскажем о том, что такое корпус, зачем он нужен, как обстоят дела с корпусами в России и за рубежом, почему так плохо и какой у нас план.

Заключительная лекция курса «Сетевое программирование в UNIX», который подготовили специалисты SkyDNS и компании «Айдеко», получилась многогранной.

На лекции были рассмотрены две основных темы. Марк Коренберг («Айдеко») и Александр Патраков (SkyDNS) рассказали, как простыми модификациями можно ускорить работу цикла обработки событий и объяснили, как пользоваться флагом EPOLLET.

По работе мне периодически приходится визуализировать численные данные — в виде таблиц, диаграмм или графиков. Из последнего прочитанного по теме наиболее интересной показалась известная книга Тафти The Visual Display of Quantitative Information. Я решил сделать из неё краткие выписки по относящимся к моим задачам вопросам. Ключевое слово здесь — краткие. Максимум полезной информации на минимум текста (даже стиль изложения будет подчёркнуто лапидарным). Дополнительные сведения и собственные мысли буду скрывать под спойлер. Надеюсь, мой конспект будет полезен хабрасообществу; предлагаю также поделиться своими наработками и полезными ссылками.

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

Наша статья о машинном обучении объясняет одну из техник, которые применяются в поисковой машине тогда, когда возникает нужда в корректном разбиения текста на предложения. Решение такой задачи имеет принципиальное значение, например, при генерации сниппетов поисковыми системами или при построении базы контекстов словоупотребления. Сейчас эта технология встраивается в индексатор Поиска@Mail.Ru. Точность метода, по нашим наблюдениям — не менее 99%.
О том, как это работает, читайте в нашей статье.

Здравствуйте.

В контексте анализа данных из твиттера возникла задача обработки хештегов. Нужно было взять хештег и разбить его на отдельные слова (#habratopic => habra topic). Задача казалась примитивной, но, получается, я ее недооценил. Пришлось перебрать несколько алгоритмов пока не было найдено то, что надо.

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

Однажды мне пришлось наблюдать, как спамеры очень интересным образом обходят спам-фильтр. Вместо традиционного URL типа «example.com», ссылка выглядела так:
http://example．com
Ссылка с подобной изощрённой точкой работает в IE7, FF3, Opera 9.5, Safari 3, Google Chrome и не работает в IE6.

0. Присказка

В некотором царстве, в некотором государстве жил-был программист. Звали его, как полагается, Иван. Был он настоящим спецом, обладал всеми Тремя Великими Добродетелями Программиста, то есть был ленив, спесив и нетерпелив. Случилась в том царстве печаль великая: кризис. И выгнали Ваню с работы без выходного пособия. Горевал Ваня долго, а потом собрался с духом и разослал резюме по всему белу свету. Долго ли, коротко ли, вызвали Ваню на собеседование. Требований к соискателю было много, но главное — требовалось хорошо владеть регулярными выражениями. До собеседования — почти месяц, готовься — не хочу. Будучи человеком серьёзным, готовиться Иван решил обстоятельно. 3 недели и 3 дня он лежал на печи, почитывал Хабр и думал, как же неслыханно обстоятельно он будет готовиться. До собеседования остался 1 день. Ванюша мысленно обругал работодателей, которые назначают собеседование так скоро, что совсем подготовиться не успеваешь, слез с печи, сдал пивные бутылки и на вырученные деньги купил книжку по регексам. Читал он её до полного изнеможения, пока не отключился. Утром мы найдём сонную физиономию Ванюши лежащей, как на подушке, на этой самой книжке под Хабракатом.

В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

За последнюю неделю дважды объяснял людям как организована работа с памятью в х86, с целью чтобы не объяснять в третий раз написал эту статью.

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

Когда-то давно взбрела мне в голову идея: написать свой собственный поисковик. Было это очень давно, тогда я еще учился в ВУЗе, мало чего знал про технологии разработки больших проектов, зато отлично владел парой десятков языков программирования и протоколов, да и сайтов своих к тому времени было понаделано много.

Ну есть у меня тяга к монструозным проектам, да…

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

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

Под катом:

• Шифр Цезаря
• Шифр пар
• Шифр четырех квадратов
• Матричный шифр
• Шифр ADFGX
• Шифр Виженера

Введение

Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.

В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:

• Расстояние Левенштейна
• Расстояние Дамерау-Левенштейна
• Алгоритм Bitap с модификациями от Wu и Manber
• Алгоритм расширения выборки
• Метод N-грамм
• Хеширование по сигнатуре
• BK-деревья

А также проведу сравнительное тестирование качества и производительности алгоритмов.