Всем привет! Недавние события связанные со стартом продаж Raspberry Pi приверли к тому, что главный продажный сайт этого уникального девайса лёг и лежит по сей день. Чтобы не пропустить момент «поднятия с колен», в срочном порядке был реанимирован и допилен один старый, но полезный проект — Whydown.
stab @stab
User
LogLog — находим число уникальных элементов
5 min
30KЗдравствуй, Хабр! Мы с тобой уже побаловались фильтрами Блума и MinHash. Сегодня разговор пойдёт о ещё одном вероятностном-рандомизированном алгоритме, который позволяет с минимальными затратами памяти определить примерное число уникальных элементов в больших объёмах данных.
Для начала, поставим себе задачу: предположим, что у нас имеется большой объём текстовых данных — скажем, плоды литературного творчества небезызвестного Шекспира, и нам необходимо подсчитать количество различных слов встречающихся в этом объёме. Типичное решение — счётчик с урезанной хеш-таблицей, где ключами будут слова без ассоциированных с ними значений.
Способ всем хорош, но требует относительно большой объём памяти для своей работы, ну а мы с вами, как известно, неугомонные гении эффективности. Зачем много, если можно мало — примерный размер словарного запаса упомянутого выше Шекспира, можно вычислить используя всего 128 байт памяти.
Для начала, поставим себе задачу: предположим, что у нас имеется большой объём текстовых данных — скажем, плоды литературного творчества небезызвестного Шекспира, и нам необходимо подсчитать количество различных слов встречающихся в этом объёме. Типичное решение — счётчик с урезанной хеш-таблицей, где ключами будут слова без ассоциированных с ними значений.
Способ всем хорош, но требует относительно большой объём памяти для своей работы, ну а мы с вами, как известно, неугомонные гении эффективности. Зачем много, если можно мало — примерный размер словарного запаса упомянутого выше Шекспира, можно вычислить используя всего 128 байт памяти.
+79
MinHash — выявляем похожие множества
4 min
26KКатегорически приветствую! В прошлый раз я писал о вероятностном алгоритме определения принадлежности элемента множеству, в этот раз будет про вероятностную оценку похожести. Не надо большого ума, чтобы додуматься до следующего показателя схожести двух множеств А и Б:
То есть, количество элементов в пересечении делённое на количество элементов в объединении. Эта оценка называется коэффициентом Жаккара (Jaccard, поэтому «J»), коэффициент равен нулю, когда множества не имеют общих элементов, и единице, когда множества равны, в остальных случаях значение где-то посередине.
То есть, количество элементов в пересечении делённое на количество элементов в объединении. Эта оценка называется коэффициентом Жаккара (Jaccard, поэтому «J»), коэффициент равен нулю, когда множества не имеют общих элементов, и единице, когда множества равны, в остальных случаях значение где-то посередине.
+30
«Aliketo» — ищет похожие вещи, и даже иногда находит, но только на английском
1 min
1.1KПривет, Хабр!
Блог «Я безумный» зачем-то переименовали в «Подсознание», поэтому писать буду здесь. Как-то раз я не мог вспомнить название фильма, но точно помнил названия пары других, которые были на него похожи. Появилась идея зарегистрироваться на каком-нибудь рекомендательном киносервисе, затем, поставить известной мне паре фильмов наивысшие возможные оценки. Ну а дальше, уповать на то, что сервис порекомендует мне похожие фильмы и среди них будет тот, название которого я забыл.
Регистрироваться в подобном сервисе мне стало лениво потому, что всё что на самом деле мне было нужно — это просто указать пару названий фильмов и получить список похожих. Никакие регистрации-оценки-рекомендации не нужны. Так и родилась идея сделать сервис, который по паре строчек текста мог бы определить принадлежность этих строк к какому-либо множеству и показать это множество пользователю.
Естественно, основная проблема — где достать данные по множествам, ответ — получить их от самих пользователей. Но беда в том, что первые пользователи сервиса обречены на бесполезные попытки найти хоть какие-то ответы на свои запросы. Так что, всё-таки нужно где-то заранее добыть эти множества. Для английского языка, я это худо-бедно, но сделал, а вот для русского не получилось.
Если вы владеете английским, попробуйте что-нибудь поискать, другое что-нибудь непременно найдётся. Из русских множеств, сервис знает только о «хабр, лепра, дёрти» и «мир, труд, май», но ничто не мешает вам эти знания расширить. Ах да, ссылка — aliketo.com.
Весёлых выходных!
UPDATE: Вижу, что ищут одной строчкой «мир, труд», так не работает. Так работает:
мир
труд
Блог «Я безумный» зачем-то переименовали в «Подсознание», поэтому писать буду здесь. Как-то раз я не мог вспомнить название фильма, но точно помнил названия пары других, которые были на него похожи. Появилась идея зарегистрироваться на каком-нибудь рекомендательном киносервисе, затем, поставить известной мне паре фильмов наивысшие возможные оценки. Ну а дальше, уповать на то, что сервис порекомендует мне похожие фильмы и среди них будет тот, название которого я забыл.
Регистрироваться в подобном сервисе мне стало лениво потому, что всё что на самом деле мне было нужно — это просто указать пару названий фильмов и получить список похожих. Никакие регистрации-оценки-рекомендации не нужны. Так и родилась идея сделать сервис, который по паре строчек текста мог бы определить принадлежность этих строк к какому-либо множеству и показать это множество пользователю.
Естественно, основная проблема — где достать данные по множествам, ответ — получить их от самих пользователей. Но беда в том, что первые пользователи сервиса обречены на бесполезные попытки найти хоть какие-то ответы на свои запросы. Так что, всё-таки нужно где-то заранее добыть эти множества. Для английского языка, я это худо-бедно, но сделал, а вот для русского не получилось.
Если вы владеете английским, попробуйте что-нибудь поискать, другое что-нибудь непременно найдётся. Из русских множеств, сервис знает только о «хабр, лепра, дёрти» и «мир, труд, май», но ничто не мешает вам эти знания расширить. Ах да, ссылка — aliketo.com.
Весёлых выходных!
UPDATE: Вижу, что ищут одной строчкой «мир, труд», так не работает. Так работает:
мир
труд
+4
Фильтр Блума
3 min
62KИ снова здравствуйте! Сегодня я поведаю о фильтре Блума — структуре данных гениальной в своей простоте. По сути, этот фильтр реализует вероятностное множество всего с двумя операциями: добавление элемента к множеству и проверка принадлежности элемента множеству. Множество вероятностное потому, что последняя операция на вопрос «принадлежит ли этот элемент множеству?» даёт ответ не в форме «да/нет», а в форме «возможно/нет».
+82
«Просконс» — выбираем электронику
1 min
934Шалом, Хабр! Таки отважился представить тебе своё детище — результат непосильных трудов и недосыпания. Что же оно такое?
Представьте, что вы решили купить какой-либо девайс. Полистав обзоры, нашли несколько кандидатов на роль будущей покупки. Сходили на Маркет, прочитали десяток-другой однотипных отзывов — надоело. Сходили на форум, скажем, iXBT — на пятой странице флейма отчаялись узнать что-либо полезное. Подождите, не совершайте покупку вслепую! Возможно, вам сможет помочь Просконс.
Представьте, что вы решили купить какой-либо девайс. Полистав обзоры, нашли несколько кандидатов на роль будущей покупки. Сходили на Маркет, прочитали десяток-другой однотипных отзывов — надоело. Сходили на форум, скажем, iXBT — на пятой странице флейма отчаялись узнать что-либо полезное. Подождите, не совершайте покупку вслепую! Возможно, вам сможет помочь Просконс.
+47
Вышел SDK для Windows 7 и .NET 4.0
1 min
24KИз нового:
Скачать
Если у вас ещё не установлен .NET Framework 4.0, рекомендуется установить перед тем как.
- Размер уменьшили до менее чем 600-та Мбайт, что есть одна треть от размера Windows 7 RTM SDK.
- Опции в установщике раскидали по тематикам: .NET, натив, общее.
- Новый движок справки. Теперь можно скачивать кусками только нужное, а не всё целиком и не париться с накатыванием апдейтов, они ставятся сами. Думаю, все, кто видел VS2010, эту справку уже успели пощупать.
- Компилеры, само собой, обновили до идущих вместе с VS2010.
- Новый MS Build версии 4 точка 0. Утверждают, что он теперь используется для всех языков. Раньше тоже вроде для всех использовался.
Скачать
Если у вас ещё не установлен .NET Framework 4.0, рекомендуется установить перед тем как.
+17
Галерея эффектов кэшей процессоров
10 min
25KTranslation
Почти все разработчики знают, что кэш процессора — это такая маленькая, но быстрая память, в которой хранятся данные из недавно посещённых областей памяти — определение краткое и довольно точное. Тем не менее, знание «скучных» подробностей относительно механизмов работы кэша необходимо для понимания факторов влияющих на производительность кода.
В этой статье мы рассмотрим ряд примеров иллюстрирующих различные особенности работы кэшей и их влияние на производительность. Примеры будут на C#, выбор языка и платформы не так сильно влияет на оценку производительности и конечные выводы. Естественно, в разумных пределах, если вы выберите язык, в котором чтение значения из массива равносильно обращению к хеш-таблице, никаких результатов пригодных к интерпретации вы не получите. Курсивом идут примечания переводчика.
В этой статье мы рассмотрим ряд примеров иллюстрирующих различные особенности работы кэшей и их влияние на производительность. Примеры будут на C#, выбор языка и платформы не так сильно влияет на оценку производительности и конечные выводы. Естественно, в разумных пределах, если вы выберите язык, в котором чтение значения из массива равносильно обращению к хеш-таблице, никаких результатов пригодных к интерпретации вы не получите. Курсивом идут примечания переводчика.
+173
Information
- Rating
- Does not participate
- Date of birth
- Registered
- Activity