Записки программиста

Мне Denis, в комментария на тему Приоритетные очереди 2, подсказал отличную тему, как бороться с перекрутами в системах управления рекламой, о чём сегодня и поговорим…

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

Почитал, подумал и пришёл к следующим мыслям.

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

Не первый раз сталкиваюсь с задачей, для которой я пока не придумал красивого и простого решения… Речь идёт о приоритетных очередях.

Для решения проблемы с выбором баннера, который надо показать на площадке, я знаю два решения. Первое решение — подсчёт суммы приоритетов всех баннеров, расстановка весов каждому из баннеров, а потом, случайным образом (с учётом приоритетов) выбор баннера. Такой вариант не нравится большим количеством вычислений и тем, что баннеры выбираются случайным образом, а не равномерно (на большом трафике статистика нормальная, но хочется иметь нормальную статистику и на маленьком трафике). Второй вариант — очереди. Формируется циклическая очередь, по которой бегаем. Математики мало, но есть свои проблемы. Читать дальше…

Написал собственный парсер HTML. Пока он не достаточно хорошо оптимизирован (знаю где можно ускорить), но при этом перелопатил HTML-ку в 721Мб (взял реальный HTML в 180К и продублировал его много раз) за 13 секунд без оптимизаций и за 10 секунд с оптимизацией -O3. Получается порядка 72 мегабайт в секуду. Весьма неплохо получилось, я прямо охуел, целью было 40Мб/сек

Парсер на входе получает HTML-ку, а на выходе выдаёт текст из допустимых тегов (можно указывать содержимое каких тегов нужно игнорировать). При этом он толерантен к ошибкам в документе и умеет обходить долбанные JavaScript в которых любят писать что-то типа document.write(”</script>”);

Осталось основательно потестить его на разных реальных HTML-ках и можно использовать…

Задался сегодня вопросом о том какой код со строками работает быстрее:

u_char c;
if (c == ' ' || c == '\t' || c == '\r' || c == '\n') {
......
}

или:

u_char c;
u_char delimiter[] = “…”;
if (delimiter[c]) {

}

И вот что получилось… Читать дальше…

Отстой полный! Я не нашёл HTML-парсера, который работал бы быстро, и при этом, мог перерабатывать не wellformated-документы…

Tidy оказался знатным тормозом, документ размеров в 180Кб, взятый с одного популярного сайта, он перелопачивал со скоростью порядка 6 документов в секунду, это ни в какие рамки не лезет для моих задач, где скорость должна исчисляться сотнями документов в секунду… Но зато перелопатил…

Libxml2 вообще отказался обрабатывать какие-либо документы… Опытным путём пришёл к выводу, что достаточно одной ошибки в документе чтобы он вернул ошибку…

Поиск в Google пока ничего не дал… Чувствуется придётся писать свой парсер…

Часто ловлю себя на мысли, что вот, придёт время, работать можно будет меньше, буду чаше прогуливаться по городу, читать книги, отдыхать… Но чем дальше, тем больше работы

Сейчас на мне две крупные разработки (не считая всяких мелочей) — разработка нового рекламного движка для videoclick.ru и разработка нового контекста для этого же проекта.

По рекламному движку сразу же начал “думать” большую распределённую систему, но получилось на столько сложно, что решил на время отложить эту сложность и реализовать на первое время односерверное решение. Благо в ближайший год трафик врядли привысит 30-40 миллионов запросов в сутки, а с таким трафиком легко справится один сервер. Зато потом, когда сроки не будут так поджимать, можно будет спокойно придумать и реализовать более красивую схему работы. Ещё один плюс данного подхода — на базе этой разработки можно будет быстро реализовать adboo, главное до РИФ-а успеть

По контектсту, начитавшись архитектурных решений больших систем типа google, спроектировал архитектуру под этот проект. Получилось неплохо, но в требуемые сроки с таким решением явно не уложусь. А потому, опять таки, решил реализовать для начала одно-серверное решение. Алгоритм поиска пересечения ключевых слов выдал порядка 1000 запросов в секунду на моём Mac Book Pro в однотредовом решении, что для начала очень неплохо. Засада случилась с парсингом html-документов. Собственное решение довольно часто садилось в лужу, выдавая неверный результат. Выяснил, что проблема связана с ошибками оформления html. Пошаманив, лужи стали попадаться реже, но хотелось бы совсем от них избавиться. Для этого погуглил и нашёл проект tidy, который должен избавить от всех проблем, но пока не интегрировал его, не знаю на сколько эта библиотека производительна, будем посмотреть…

А ещё у меня появилась идея кластерного решения для рекламных сетей, прообразом которой послужила технология map/reduce… Реализация обещает быть легко масштабируемой (при этом будет почти линейная масштабируемость производительности), отслеживание ограничений точным, без необходимости синхронизировать счётчики в одном месте. Но производительность должна быть меньше чем у “заточенного” решения. Пока эта идея отлёживается на полочке, как будет больше свободного времени, обязательно займусь ею плотно. Руки чешутся

Почему чукча не писатель? Да потому что он программист, у него нет времени и желания писать посты в блоге

Несколько раз блог создавался и удалялся… Последняя версия оставлена в покое, но посты с периоичностью раз в пол года — это хуже чем отсутствие блога… Читать дальше…