Всем привет! Недавние события связанные со стартом продаж Raspberry Pi приверли к тому, что главный продажный сайт этого уникального девайса лёг и лежит по сей день. Чтобы не пропустить момент «поднятия с колен», в срочном порядке был реанимирован и допилен один старый, но полезный проект — Whydown.

Здравствуй, Хабр! Мы с тобой уже побаловались фильтрами Блума и MinHash. Сегодня разговор пойдёт о ещё одном вероятностном-рандомизированном алгоритме, который позволяет с минимальными затратами памяти определить примерное число уникальных элементов в больших объёмах данных.

Для начала, поставим себе задачу: предположим, что у нас имеется большой объём текстовых данных — скажем, плоды литературного творчества небезызвестного Шекспира, и нам необходимо подсчитать количество различных слов встречающихся в этом объёме. Типичное решение — счётчик с урезанной хеш-таблицей, где ключами будут слова без ассоциированных с ними значений.

Способ всем хорош, но требует относительно большой объём памяти для своей работы, ну а мы с вами, как известно, неугомонные гении эффективности. Зачем много, если можно мало — примерный размер словарного запаса упомянутого выше Шекспира, можно вычислить используя всего 128 байт памяти.

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



То есть, количество элементов в пересечении делённое на количество элементов в объединении. Эта оценка называется коэффициентом Жаккара (Jaccard, поэтому «J»), коэффициент равен нулю, когда множества не имеют общих элементов, и единице, когда множества равны, в остальных случаях значение где-то посередине.

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

Блог «Я безумный» зачем-то переименовали в «Подсознание», поэтому писать буду здесь. Как-то раз я не мог вспомнить название фильма, но точно помнил названия пары других, которые были на него похожи. Появилась идея зарегистрироваться на каком-нибудь рекомендательном киносервисе, затем, поставить известной мне паре фильмов наивысшие возможные оценки. Ну а дальше, уповать на то, что сервис порекомендует мне похожие фильмы и среди них будет тот, название которого я забыл.

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

Естественно, основная проблема — где достать данные по множествам, ответ — получить их от самих пользователей. Но беда в том, что первые пользователи сервиса обречены на бесполезные попытки найти хоть какие-то ответы на свои запросы. Так что, всё-таки нужно где-то заранее добыть эти множества. Для английского языка, я это худо-бедно, но сделал, а вот для русского не получилось.

Если вы владеете английским, попробуйте что-нибудь поискать, другое что-нибудь непременно найдётся. Из русских множеств, сервис знает только о «хабр, лепра, дёрти» и «мир, труд, май», но ничто не мешает вам эти знания расширить. Ах да, ссылка — aliketo.com.

Весёлых выходных!

UPDATE: Вижу, что ищут одной строчкой «мир, труд», так не работает. Так работает:

мир
труд

И снова здравствуйте! Сегодня я поведаю о фильтре Блума — структуре данных гениальной в своей простоте. По сути, этот фильтр реализует вероятностное множество всего с двумя операциями: добавление элемента к множеству и проверка принадлежности элемента множеству. Множество вероятностное потому, что последняя операция на вопрос «принадлежит ли этот элемент множеству?» даёт ответ не в форме «да/нет», а в форме «возможно/нет».

Шалом, Хабр! Таки отважился представить тебе своё детище — результат непосильных трудов и недосыпания. Что же оно такое?

Представьте, что вы решили купить какой-либо девайс. Полистав обзоры, нашли несколько кандидатов на роль будущей покупки. Сходили на Маркет, прочитали десяток-другой однотипных отзывов — надоело. Сходили на форум, скажем, iXBT — на пятой странице флейма отчаялись узнать что-либо полезное. Подождите, не совершайте покупку вслепую! Возможно, вам сможет помочь Просконс.

Из нового:

• Размер уменьшили до менее чем 600-та Мбайт, что есть одна треть от размера Windows 7 RTM SDK.
• Опции в установщике раскидали по тематикам: .NET, натив, общее.
• Новый движок справки. Теперь можно скачивать кусками только нужное, а не всё целиком и не париться с накатыванием апдейтов, они ставятся сами. Думаю, все, кто видел VS2010, эту справку уже успели пощупать.
• Компилеры, само собой, обновили до идущих вместе с VS2010.
• Новый MS Build версии 4 точка 0. Утверждают, что он теперь используется для всех языков. Раньше тоже вроде для всех использовался.

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

Скачать

Если у вас ещё не установлен .NET Framework 4.0, рекомендуется установить перед тем как.

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

В этой статье мы рассмотрим ряд примеров иллюстрирующих различные особенности работы кэшей и их влияние на производительность. Примеры будут на C#, выбор языка и платформы не так сильно влияет на оценку производительности и конечные выводы. Естественно, в разумных пределах, если вы выберите язык, в котором чтение значения из массива равносильно обращению к хеш-таблице, никаких результатов пригодных к интерпретации вы не получите. Курсивом идут примечания переводчика.