Нет, я не буду рассказывать с какими параметрами нужно генерировать радужные таблицы, или как придумывать «стойкие» пароли. Сама по себе тематика немного устарела и едва ли поможет в отвлеченных вопросах. Но, как оказалось, в основу «радужных таблиц» положен замечательный способ (я бы не стал называть его методом или алгоритмом) размена времени на память, то бишь «time-memory trade off». Это не первый (и, наверное, не последний) топик про предвычисления, но, надеюсь, он Вам понравится.
Руслан @ruzzz
User
Рекомендации друзей для социальных сетей
2 min
1.7KНе давно писал как можно рекомендовать товар в Интернет-магазинах или других местах, используя информацию о пользователе. Сейчас хочу показать алгоритм, который позволяет рекомендовать друзей, например в социальных сетях.
Первый шаг, представим информацию о пользователя в интервальной шкале и рекомендуем пользователю друзей используя коэффициент корреляции Пирсона, который будет измеряет степень линейной зависимости между двумя интервальными переменными. Например, у нас есть 4 пользователя: Дима, Анна, Петя и Саша. Мы знаем о них информацию, которую представляем в виде чисел в массиве (интересы, блоги, возраст и т.д.)
Первый шаг, представим информацию о пользователя в интервальной шкале и рекомендуем пользователю друзей используя коэффициент корреляции Пирсона, который будет измеряет степень линейной зависимости между двумя интервальными переменными. Например, у нас есть 4 пользователя: Дима, Анна, Петя и Саша. Мы знаем о них информацию, которую представляем в виде чисел в массиве (интересы, блоги, возраст и т.д.)
+20
Эффективная сегментация изображений на графах
10 min
41K![Segmentation example](https://habrastorage.org/getpro/habr/post_images/92c/193/6e6/92c1936e6ddd96f4b2718f8beb509a5f.jpg)
Сегментация изображений и выделение границ объектов (edge detection) играют важную роль в системах Computer Vision и применяются для задач распознавания сцен и выделения (определения) объектов. По большому счету, это такой же инструмент, как, например, сортировка, предназначенный для решения более высокоуровневых задач. И поэтому понимание устройства данного класса алгоритмов не будет лишним при построении подобных систем с учетом предъявляемых требований (в плане качество/производительность) и специфики поставленных задач.
В данной статье кратко описан алгоритм «Efficient Graph-Based Image Segmentation» авторов Pedro F. Felzenszwalb (MIT) и Daniel P. Huttenlocher (Cornell University), опубликованный в 2004 году. Да, алгоритм относительно старенький, но, несмотря на это, он до сих пор остается весьма популярным, демонстрируя неплохие результаты в плане производительности.
Под катом – большая смесь картинок и текста, не требовательная к текущему уровню знаний тематики. Любопытство приветствуется.
+162
Алгоритм коллаборативной фильтрации
2 min
16KКоллаборативная фильтрация (англ. collaborative filtering) — это метод, который даёт автоматические прогнозы исходя из наколенной информации о интересах и вкусах пользователей.
Чаще всего можно рекомендовать музыку или книги уже имея какие-то данные о пользователе. Например, Amazon или Ozon запоминают, что я ищу или куда ходил и из этих данных строит мне рекомендацию. Но лучше, чтобы пользователь сам вводил их в свой профиль, можно даже ему рассказать, что у вас эта система стоит и чтобы он сам мог выбирать что ему дать в следующий раз.
Чаще всего можно рекомендовать музыку или книги уже имея какие-то данные о пользователе. Например, Amazon или Ozon запоминают, что я ищу или куда ходил и из этих данных строит мне рекомендацию. Но лучше, чтобы пользователь сам вводил их в свой профиль, можно даже ему рассказать, что у вас эта система стоит и чтобы он сам мог выбирать что ему дать в следующий раз.
+29
Написание простейшего SOCKS4 сервера на языке Assembler
8 min
10K Какое то время тому назад захотелось мне попробовать реализовать прокси сервер для собственных нужд, да такой, который можно было бы в дальнейшем использовать, а также, чтобы размер его был минимален. Естественным вариантом для меня стала реализация с использованием ассемблера. Программка получилась небольшая, удобная и в дальнейшем я очень часто ей пользовался. А вот теперь, по прошествии лет, хотелось бы показать простейшую реализацию одного протокола, SOCKS4. Данный протокол был создан для того, чтобы клиенты, находящиеся в локальной сети за межсетевым экраном могли обращаться во внешнюю сеть. В то же время запросы клиентов в таком случае есть возможность контролировать :) Самым первым, что нужно, при реализации – прочитать документацию с описанием данного протокола, так как мы хотим, чтобы наш протокол понимался стандартными программами, без “подтачивания напильником”. Итак, документация :
Описание протокола SOCKS
SOCKS: A protocol for TCP proxy across firewalls
Теперь, вооружившись описанием, приступим. Работа прокси сервера состоит в том, чтобы принять от клиента запрос в определенном формате, сформировать сокет и подключить его по адресу запрошенному клиентом, после чего обеспечить обмен данными между двумя сокетами, до их закрытия со стороны сервера, либо клиента. Приступим к реализации.
Описание протокола SOCKS
SOCKS: A protocol for TCP proxy across firewalls
Теперь, вооружившись описанием, приступим. Работа прокси сервера состоит в том, чтобы принять от клиента запрос в определенном формате, сформировать сокет и подключить его по адресу запрошенному клиентом, после чего обеспечить обмен данными между двумя сокетами, до их закрытия со стороны сервера, либо клиента. Приступим к реализации.
+24
Визуализация данных в вебе 3: Flash / Flex
2 min
6.2KДобрый день!
Продолжаем говорить о визуализации данных в вебе. На сей раз поговорим о Flash / Flex библиотеках и компонентах.
Предыдущие топики:
Продолжаем говорить о визуализации данных в вебе. На сей раз поговорим о Flash / Flex библиотеках и компонентах.
Предыдущие топики:
- Изумительные диаграммы с новым Chart контролом
- Визуализация направленных графов в вебе
- Список Javascript библиотек для рисования графиков и диаграмм — habrahabr.ru/blogs/javascript/79960 (публикация в блоге — msug.vn.ua/blogs/2257.aspx)
- Список Javascript библиотек для рисования графиков и диаграмм 2 — habrahabr.ru/blogs/javascript/80027 (публикация в блоге — msug.vn.ua/blogs/2276.aspx)
+34
RTM Context Autocomplete Menu
5 min
1.9KОднажды я зашел на rememberthemilk.com и понял, что хочу такое же контекстное autocomplete меню в свой проект. В результате получился небольшой jquery плагин, который хочу презентовать в этом посте. Работает в ie6+, opera, safari, firefox, chrome (тестировал в последних версиях). В кратце расскажу в чем суть «контекстного» меню в RTM-стиле.
Это меню присоединяется к input-элементу, но, в отличие от обычных autocomplete меню, оно «всплывает» не для ввода всего значения элемента, а для какой-то логической части поля ввода. При этом меню позиционируется непосредственно под автодополняемым текстом. Вот как это выглядит:
![image](https://habrastorage.org/getpro/habr/post_images/f86/58e/f09/f8658ef09e562bc800d1ba977bc8a469.png)
Лицензия проекта — MIT / beerware.
Скачать библиотеку с примерами можно тут: js-context-autocomplete.googlecode.com/files/js-autocomplete-v5.tar
Последнюю ревизию забираем тут: svn checkout js-context-autocomplete.googlecode.com/svn/trunk js-context-autocomplete-read-only
Кому интересно поучаствовать в проекте — пишите в личку.
Временное online-demo (upd)
Под катом интересные моменты реализации, описание функциональности, примеры, список известных багов и фич для реализации.
Это меню присоединяется к input-элементу, но, в отличие от обычных autocomplete меню, оно «всплывает» не для ввода всего значения элемента, а для какой-то логической части поля ввода. При этом меню позиционируется непосредственно под автодополняемым текстом. Вот как это выглядит:
![image](https://habrastorage.org/getpro/habr/post_images/f86/58e/f09/f8658ef09e562bc800d1ba977bc8a469.png)
Лицензия проекта — MIT / beerware.
Скачать библиотеку с примерами можно тут: js-context-autocomplete.googlecode.com/files/js-autocomplete-v5.tar
Последнюю ревизию забираем тут: svn checkout js-context-autocomplete.googlecode.com/svn/trunk js-context-autocomplete-read-only
Кому интересно поучаствовать в проекте — пишите в личку.
Под катом интересные моменты реализации, описание функциональности, примеры, список известных багов и фич для реализации.
+62
Divine Project – автоматическое создание сайта из PSD шаблона
1 min
12K![image](http://pic.co.ua/images/12592707313114d63147f9491e4397a03c74f66a1d.jpg)
Это мой первый пост, а потому попрошу сильно не ругать =)
Я думаю, кто-то из вас рано или поздно сталкивался с задачей сделать для своего сайта уникальный дизайн, но, увы, это не так просто осуществить, как хотелось бы. Но с помощью DIVINE всё становиться гараздо проще. Дизайнерам теперь не нужно владеть HTML, CSS и понятием о том, как устроены темы для WordPress
+31
Что такое Pimpl по версии Qt, и с чем его едят!
12 min
39KВступление.
Часто в документации от Qt встречается термин Pimpl. Кроме того, те кто хоть немного копался в исходном коде Qt часто видел такие макросы как: Q_DECLARE_PRIVATE, Q_D. А также встречал так называемые приватные заголовочные файлы, название которых заканчивается на "_p.h".
В этой статье я попробую приоткрыть ширму за всей это структурой.
Pimpl, что это?
Pimpl — Pointer to private implementation. Это одно из названий паттерна программирования. Еще его называют чеширским котом — «Cheshire Cat» (это название мне больше нравится). В чем суть этого паттерна? Основная идея этого паттерна — это вынести все приватные члены класса и, в не которых случаях, функционала в приватный класс.
Отсюда название «чеширский кот» — видно только улыбку, а все остальное остается невидимым, но оно несомненно есть :-) Кто не помнит этого замечательного кота, может обратится к первоисточнику, к книге Льюиса Кэрролла «Алиса в стране чудес». Очень интересная книга, особенно если читать в оригинале.
Что это дает?
+44
Верстка повторяющихся блоков
3 min
14KДовольно часто при верстке сайта возникает необходимость размещать блоки одинаковой ширины, но разной высоты в контейнере с переменной шириной (читай резиновом). Плюс на этот список может применяться фильтр, который JS-ом скрывает или показывает элементы списка, при этом он не должен разрушать «строки», верстку, или образовывать дыры, поэтому решения на таблицах не катят сразу. Простейший пример — каталог товаров:
![](https://habrastorage.org/getpro/habr/post_images/6b6/aab/c96/6b6aabc96087f1dd4bf6376da1a415e7.jpg)
![](https://habrastorage.org/getpro/habr/post_images/6b6/aab/c96/6b6aabc96087f1dd4bf6376da1a415e7.jpg)
+81
Многопоточность, общие данные и мьютексы
5 min
58KВведение
При написании многопоточных приложений почти всегда требуется работать с общими данными, одновременное изменение которых может привести к очень неприятным последствиям.
Для блокировки общих данных от одновременного доступа необходимо использовать объекты синхронизации.
В данном топике рассмотренна методика работы с мютексами, существенно уменьшающая количество потенциальных ошибок связанных с созданием/удалением и захватом/освобождением.
Неудаление мютекса приводит к утечке памяти, незахват — к некорректным данным, а неосвобождение — к блокировке всех функций, работающих с общими данными.
Ниже рассматривается работа с мютексами в Windows и Unix, подобная идея может быть использована при работе с другими объектами синхронизации.
Эта идея является частным случаем методики «Выделение ресурса — есть инициализация (RAII)».
+26
Как устроена смарт-карта
3 min
35KДолгое время работая со смарт-картами, я сам имел не очень чёткое представление об их внутренностях. Вот получив некий документ, описывающий структуру и схему работы смарт-карты делюсь этой информацией.
+52
Безопасное хранение секретов
4 min
8.2K![]() |
Расскажу об одном из портативных, кроссплатформенных методов хранения секретов на накопителях, в основе которого лежит только открытое, свободно распространяемое ПО. |
Никогда не мог запомнить все логины, пароли и прочие коды доступа ко всем моим учетным записям. Порой регистрационное имя и заветный код необходимы в самый неподходящий момент, поэтому я таскаю их на флэшке. Для того, чтобы не рвать на себе волосы при потере заветного накопителя информации я и написал скриптики, речь о которых пойдет ниже.
+14
Пузырьки, кэши и предсказатели переходов
6 min
10KЭта заметка написана по мотивам одного любопытного поста, краткий коммент её же автора к которому сподвиг меня разобраться в происходящем поподробнее. Предлагается сравнить две вариации алгоритма сортировки пузырьком. Первая из них – обычный пузырёк, с небольшой оптимизацией — внутренний цикл можно закончить немного раньше, зная, что оставшаяся часть массива уже отсортирована:
Во втором варианте внутренний цикл проходит по другой части массива, однако алгоритмически этот вариант эквивалентен первому (подробности ниже):
Запускаем (код), например, для N=100 000 на массиве int'ов, и получаем около 30 секунд в первом случае, и меньше 10 секунд — во втором, то есть отличие в 3 раза! Откуда же тогда берётся такая разница?
for (i=0; i<N; i++)
for (j=0; j<N - (i+1); j++)
if (a[j] > a[j+1])
swap(a[j], a[j+1]);
Во втором варианте внутренний цикл проходит по другой части массива, однако алгоритмически этот вариант эквивалентен первому (подробности ниже):
for (i=0; i<N-1; i++)
for (j=i; j>=0; j--)
if (a[j] > a[j+1])
swap(a[j], a[j+1]);
Запускаем (код), например, для N=100 000 на массиве int'ов, и получаем около 30 секунд в первом случае, и меньше 10 секунд — во втором, то есть отличие в 3 раза! Откуда же тогда берётся такая разница?
+143
Создание плагина для браузера с помощью NPAPI
6 min
25KNPAPI это набор API, позволяющий создавать плагины для Firefox, Chrome, Safari, Opera. В этой статье я хочу дать первоначальные сведения о создании плагина на базе NPAPI. Будет приведен пример плагина под Windows, но и разработчикам на Mac и Unix статья будет полезной, т.к. описывает общий подход к созданию плагинов, использующих NPAPI.
NPAPI плагин это модуль, который «цепляется» к браузеру и отвечает за обработку определенного content type (например application/x-shockwave-flash).
О том как появился и менялся NPAPI вы можете прочитать на странице в Wikipedia
Полное описание API можно получить на странице Gecko_Plugin_API_Reference
NPAPI плагин это модуль, который «цепляется» к браузеру и отвечает за обработку определенного content type (например application/x-shockwave-flash).
О том как появился и менялся NPAPI вы можете прочитать на странице в Wikipedia
Полное описание API можно получить на странице Gecko_Plugin_API_Reference
+32
Быстрое определение местоположения по ip в postgresql
3 min
14KВ этом топике я хочу рассказать о задаче, очень часто встречающейся в веб-проектах — определение местоположения по ip-адресу. Начну с того, что для того, чтобы определить местоположение пользователя — нужна некая geoip база. Приведу здесь два популярных бесплатных варианта:
IpGeoBase — очень хорошая бесплатная база, но, к сожалению, только по российским ip-адресам.
MaxMind — огромная база по ip-адресам всех стран. Предоставляют бесплатную lite-версию базы. Точность базы по российским ip-адресам не настолько хороша, как у IpGeoBase. Также предоставляют некое API для работы со своей базой, которое позволяет производить выборки очень быстро.
Допустим вы скачали эти базы и залили их в таблицы вашей БД Postgresql (сама закачка — несколько out of scope, если у кого-то возникнет желание — я могу в будущем рассказать о том, что такое команда COPY и с чем ее едят). В общем случае вы получите таблицу такой структуры:
Здесь:
startip — это начало блока ip-адресов в формате long
endip — конец блока ip-адресов в формате long
location_id — идентификатор локации (город, регион, страна и т.д., maxmind даже координаты содержит).
IpGeoBase — очень хорошая бесплатная база, но, к сожалению, только по российским ip-адресам.
MaxMind — огромная база по ip-адресам всех стран. Предоставляют бесплатную lite-версию базы. Точность базы по российским ip-адресам не настолько хороша, как у IpGeoBase. Также предоставляют некое API для работы со своей базой, которое позволяет производить выборки очень быстро.
Допустим вы скачали эти базы и залили их в таблицы вашей БД Postgresql (сама закачка — несколько out of scope, если у кого-то возникнет желание — я могу в будущем рассказать о том, что такое команда COPY и с чем ее едят). В общем случае вы получите таблицу такой структуры:
startip | endip | location_id |
---|---|---|
2130706433 | 2130706433 | 1 |
Здесь:
startip — это начало блока ip-адресов в формате long
endip — конец блока ip-адресов в формате long
location_id — идентификатор локации (город, регион, страна и т.д., maxmind даже координаты содержит).
+35
Использование V8
9 min
28KV8 — это движок JavaScript от Google, который используется в браузере Chrome. Он быстрый и доступен в исходных кодах (С++) для Linux (точнее для gcc) и под Windows.
В свете роста популярности использования V8 я решил поделиться своим (годичным) опытом его использования на платформе Windows в качестве серверного скриптового движка.
Часть 1. Введение и простейшая программа, использующая V8.
В свете роста популярности использования V8 я решил поделиться своим (годичным) опытом его использования на платформе Windows в качестве серверного скриптового движка.
Часть 1. Введение и простейшая программа, использующая V8.
+35
+61
Мой защищённый контейнер
3 min
3KПри разработке проекта на C++ возникла необходимость создать защищённый контейнер. Вернее, кросс-платформенные на уровне исходного кода классы, поддерживающие защищённое хранение информации от нескольких байт до гигабайтов, что делает необходимым поддержку потокового шифрования/дешифрования.
Не имея альтернативы нанять на данном этапе профессионального криптографа, приступил к созданию велосипеда.
Данная статья написана для открытого обсуждения предлагаемых решений людьми, близкими к криптографии, а также для тех, кто будет проходить этот путь с нуля, как экономия их времени и сил.
Не имея альтернативы нанять на данном этапе профессионального криптографа, приступил к созданию велосипеда.
Данная статья написана для открытого обсуждения предлагаемых решений людьми, близкими к криптографии, а также для тех, кто будет проходить этот путь с нуля, как экономия их времени и сил.
+4
HTML parser Jquery style
1 min
7.6KНаткнулся на вот такой полезный класс, любителям chained вызовов и jquery понравится очень!
PHP Simple HTML DOM Parser:
simplehtmldom.sourceforge.net
Примеры:
// Find all anchors, returns a array of element objects
$ret = $html->find('a');
// Find (N)th anchor, returns element object or null if not found (zero based)
$ret = $html->find('a', 0);
// Find all which attribute id=foo
$ret = $html->find('div[id=foo]');
// Find all with the id attribute
$ret = $html->find('div[id]');
// Find all element has attribute id
$ret = $html->find('[id]');
// or
echo $html->getElementById(«div1»)->childNodes(1)->childNodes(1)->childNodes(2)->getAttribute('id');
simplehtmldom.sourceforge.net/manual.htm — документация и больше примеров
PHP Simple HTML DOM Parser:
simplehtmldom.sourceforge.net
Примеры:
// Find all anchors, returns a array of element objects
$ret = $html->find('a');
// Find (N)th anchor, returns element object or null if not found (zero based)
$ret = $html->find('a', 0);
// Find all which attribute id=foo
$ret = $html->find('div[id=foo]');
// Find all with the id attribute
$ret = $html->find('div[id]');
// Find all element has attribute id
$ret = $html->find('[id]');
// or
echo $html->getElementById(«div1»)->childNodes(1)->childNodes(1)->childNodes(2)->getAttribute('id');
simplehtmldom.sourceforge.net/manual.htm — документация и больше примеров
+1
Information
- Rating
- Does not participate
- Registered
- Activity