Пока результат примерно такой: ????????????????????????????
# UPD предвидеться.
# UPD предвидеться.
Префиксные деревья в Python
6 мин
Доделал на днях питонью библиотеку datrie, реализующую префиксное дерево (см. википедию или хабр), спешу поделиться.
Если вкратце, то можно считать, что datrie.Trie — это замена стандартному питоньему dict, которая при определенных условиях (ключи — строки) занимает меньше памяти, имеет сравнимую скорость получения отдельного элемента и поддерживает дополнительные операции (получение всех префиксов данной строки, получение всех строк, начинающихся с данной строки и др.), которые работают примерно так же быстро, как и «словарные» операции.
Работает под Python 2.6-3.3, поддерживает юникод, лицензия LGPL.
Если вкратце, то можно считать, что datrie.Trie — это замена стандартному питоньему dict, которая при определенных условиях (ключи — строки) занимает меньше памяти, имеет сравнимую скорость получения отдельного элемента и поддерживает дополнительные операции (получение всех префиксов данной строки, получение всех строк, начинающихся с данной строки и др.), которые работают примерно так же быстро, как и «словарные» операции.
Работает под Python 2.6-3.3, поддерживает юникод, лицензия LGPL.
Сжатые префиксные деревья
8 мин
Туториал
Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В этом недавнем посте рассматривается «питонья библиотека datrie», являющаяся Cython-оберткой библиотеки libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (АВЛ-дерево) и сжатого префиксного дерева. 
Trie, или нагруженное дерево
4 мин
Здравствуй, Хабрахабр. Сегодня я хочу рассказать о такой замечательной структуре данных как словарь на нагруженном дереве, известной также как префиксное дерево, или trie.
Нагруженное дерево — структура данных реализующая интерфейс ассоциативного массива, то есть позволяющая хранить пары «ключ-значение». Сразу следует оговорится, что в большинстве случаев ключами выступают строки, однако в качестве ключей можно использовать любые типы данных, представимые как последовательность байт (то есть вообще любые).
Что это ?
Нагруженное дерево — структура данных реализующая интерфейс ассоциативного массива, то есть позволяющая хранить пары «ключ-значение». Сразу следует оговорится, что в большинстве случаев ключами выступают строки, однако в качестве ключей можно использовать любые типы данных, представимые как последовательность байт (то есть вообще любые).
Максимальное XOR
6 мин
Здравствуй, Хабр. И сразу к делу.
Задача:
Есть два целых числа: L и R. Нужно найти максимальное значение A xor B на промежутке [L; R], где L ≤ A ≤ B ≤ R.
Казалось бы ничего сложного. Сразу напрашивается решение простым перебором.
А что, если в интервале будет 1000000 чисел. Возьмем L = 1, а R = 1000001. Сколько времени понадобится cреднестатистическому компьютеру для того, чтобы посчитать максимальное значение xor на этом интервале? Моему ноутбуку потребовалось 1699914 миллисекунд.
Существует решение, которое работает значительно быстрее, именно о нем и пойдет речь в этой статье.
Задача:
Есть два целых числа: L и R. Нужно найти максимальное значение A xor B на промежутке [L; R], где L ≤ A ≤ B ≤ R.
Казалось бы ничего сложного. Сразу напрашивается решение простым перебором.
Развернуть
Сложность этого решения O(n2).public int BruteForce(int one, int two)
{
int maxXor = 0;
while (one < two)
{
int oneTemp = one + 1;
while (oneTemp <= two)
{
int curXor = one ^ oneTemp;
if (maxXor < curXor) maxXor = curXor;
oneTemp++;
}
one++;
}
return maxXor;
}
А что, если в интервале будет 1000000 чисел. Возьмем L = 1, а R = 1000001. Сколько времени понадобится cреднестатистическому компьютеру для того, чтобы посчитать максимальное значение xor на этом интервале? Моему ноутбуку потребовалось 1699914 миллисекунд.
Существует решение, которое работает значительно быстрее, именно о нем и пойдет речь в этой статье.
Низкоуровневая реализация префиксного дерева trie на PHP
4 мин
Предисловие
Описанная здесь реализация trie на PHP делает пока слишком жирный словарь, который соответственно довольно долго загружается в память, что нивелирует довольно неплохую скорость её работы. Скорость поиска составляет ~80 тыс. слов в секунду. Словарь сделан из списка лемм словаря opencorpora.org и включает в себя 389844 слова. В несжатом виде словарь весит ~150мб, а сжатый gzip ~6мб. Однако довольно неплохие результаты быстродействия доказывают, что на чистом PHP можно сделать вполне работоспособное префиксное дерево trie.
Как сделать расширение на PHP7 сложнее, чем «hello, world», и не стать красноглазиком. Часть 2
8 мин
Туториал
Краткое содержание первой части
В первой части я сделал болванку расширения, заставил ее правильно работать в IDE Clion, написал функцию-аналог my_array_fill() и проверил ее работоспособность в php.
Что теперь?
Теперь я запилю код библиотеки libtrie в наше расширение.
Немного расскажу как можно заставить работать старые php5 расширения в php7.
Дальше я сделаю несколько основных функций из этой библиотеки в php и проверю, что получилось.
pymorphy2
16 мин
В далеком 2009 году на хабре уже была статья "Кузявые ли бутявки.." про pymorphy — морфологический анализатор для русского языка на Python (штуковину, которая умеет склонять слова, сообщать информацию о части речи, падеже и т.д.)
В 2012м я начал потихоньку делать pymorphy2 (github, bitbucket) — думаю, самое время представить эту библиотеку тут: pymorphy2 может работать в сотни раз быстрее, чем pymorphy (втч без использования C/C++ расширений) и при этом требовать меньше памяти; там лучше словари, лучше качество разбора, лучше поддержка буквы ё, проще установка и более «честный» API. Из негатива — не все возможности pymorphy сейчас реализованы в pymorphy2.
Эта статья о том, как pymorphy2 создавался (иногда с довольно скучными техническими подробностями), и сколько глупостей я при этом наделал; если хочется просто все попробовать, то можно почитать документацию.
В 2012м я начал потихоньку делать pymorphy2 (github, bitbucket) — думаю, самое время представить эту библиотеку тут: pymorphy2 может работать в сотни раз быстрее, чем pymorphy (втч без использования C/C++ расширений) и при этом требовать меньше памяти; там лучше словари, лучше качество разбора, лучше поддержка буквы ё, проще установка и более «честный» API. Из негатива — не все возможности pymorphy сейчас реализованы в pymorphy2.
Эта статья о том, как pymorphy2 создавался (иногда с довольно скучными техническими подробностями), и сколько глупостей я при этом наделал; если хочется просто все попробовать, то можно почитать документацию.
«Сделайте мне красиво!» Выпуск №26
1 мин
Вашему вниманию очередной выпуск подкаста о веб-разработке «Сделайте мне красиво!»
Наши ссылки: RSS и лента на rpod.ru
Show notes:
- Два новых браузера: IE9 и FF4. Первые впечатления ведущих
- Документация по-русски самых сложных моментов JS или «Все в сад!»
- Два статьи от John Resig про хранение словарей на клиенте (раз и два)
- Подробное и понятное описание storage в HTML5
- Новая версия Zen Coding v0.7
- Генератор css3 transitions: хорошее решение узкой задачи
Наши ссылки: RSS и лента на rpod.ru
«Сделайте мне красиво!» Выпуск №27
1 мин
Вашему вниманию очередной выпуск подкаста о веб-разработке «Сделайте мне красиво!»
Наши ссылки: RSS и лента на rpod.ru
Show notes:
- Как избежать самых распространенных ошибок с vendor prefixes
- Сеанс маркетинга IE9 с разоблачением
- Продолжение темы словарей в JS (статья John Resig + подробнее про succinct trie)
- TDD + JS: посмотреть как другие работают
- Raphaël — js-библиотека для векторной графики и векторные иконки для неё
- Рекорды FF4: не кантовать, развалится
- Чего не делают обычные люди: непрозрачные намеки
Наши ссылки: RSS и лента на rpod.ru
Алгоритм поиска наилучшего маршрута в linux
8 мин
В настоящее время в компьютерных сетях практически повсеместно используется протокол IP. Для того, чтобы отправить IP-пакет каждый маршрутизатор ищет в свой таблице маршрутизации наилучший маршрут для адреса назначения пакета. В данной статье я хочу описать алгоритм поиска наилучшего маршрута, реализованного в ядре linux.
Поиск анаграмм и сабанаграмм во всех словах языка
2 мин
Решение задач с анаграммами натолкнуло на мысль:
В найденном словаре больше 1,5 млн слов в различных формах
Можно сравнить каждое слово с каждым, но для 1,5 млн записей это долго и неоптимально.
В мире с бесконечной памятью можно сгенерировать подстроки всех перестановок каждого слова и проверить наш словарь на них
Но есть ли решение получше?
Сколько останется слов, если удалить все анаграммы и сабанграммы из словаря русского языка
В найденном словаре больше 1,5 млн слов в различных формах
Можно сравнить каждое слово с каждым, но для 1,5 млн записей это долго и неоптимально.
В мире с бесконечной памятью можно сгенерировать подстроки всех перестановок каждого слова и проверить наш словарь на них
Но есть ли решение получше?
Выпуск#38: ITренировка — актуальные вопросы и задачи от ведущих компаний
6 мин
Привет! Новая неделя — новый выпуск брейнтизиров. На этот раз, с собеседований в ИТ-компанию Accolite.
Кстати, ответы на задачки из прошлого выпуска уже опубликованы, проверяйте себя и свою смекалку.
Ну что, погнали!
Кстати, ответы на задачки из прошлого выпуска уже опубликованы, проверяйте себя и свою смекалку.
Ну что, погнали!
Naive Spellchecking, или поиск ближайших слов из словаря по метрике Левенштейна на Scala
6 мин
Туториал
Приветствую! В этой статье будет показан алгоритм поиска ближайших к заданному слов из корпуса в терминах метрики Левенштейна. Наивным spellchecking-ом назван потому, что не учитывает ни морфологии, ни контекста, ни вероятности появления скорректированного слова в предложении, однако в качестве первого приближения сойдет вполне. Также алгоритм может быть расширен на поиск ближайших последовательностей из любых других сравнимых объектов, нежели простой алфавит из Char-ов, и, после допиливания напильником, его можно приспособить и для учета вероятностей появления скорректированных слов. Но в данной статье сосредоточимся на базовом алгоритме для слов определенного алфавита, скажем, английского.
Код в статье будет на Scala.
Всех заинтересовавшихся прошу под кат.
Код в статье будет на Scala.
Всех заинтересовавшихся прошу под кат.
Immutable Trie: найди то, не знаю что, но быстро, и не мусори
9 мин
Про префиксное дерево (Trie) написано немало, в том числе и на Хабре. Вот пример, как оно может выглядеть:
И даже реализаций в коде, в том числе на JavaScript, для него существует немало — от «каноничной» by John Resig и разных оптимизированных версий до серии модулей в NPM.
Зачем же нам понадобилось использовать его для сервиса по сбору и анализу планов PostgreSQL, да еще и «велосипедить» какую-то новую реализацию?..
И даже реализаций в коде, в том числе на JavaScript, для него существует немало — от «каноничной» by John Resig и разных оптимизированных версий до серии модулей в NPM.
Зачем же нам понадобилось использовать его для сервиса по сбору и анализу планов PostgreSQL, да еще и «велосипедить» какую-то новую реализацию?..
Самый быстрый Индиан: Key/Value контейнер на базе Trie
8 мин
«Может показаться, что я ничего не делаю. Но на самом деле, на клеточном уровне, я очень занят»
Автор неизвестен
В 21 веке построение программ все чаще напоминает конструктор Lego. Этот подход подразумевает, что многие «кубики» придуманы до нас. Собственно их элементарность обманчиво подсказывает, что ресурс улучшений за многие годы здесь практически исчерпан и нам остается использовать то, что есть. Но, как не странно, по аналогии с биологией, элементарные «клетки» порой скрывают самые сложные и продуманные алгоритмы и именно здесь заключены все самые интересные баталии. В этом смысле программисты по многогранности индустрии, чем-то напоминают медиков. Здесь есть свои терапевты, ветеринары, хирурги и есть вот те ребята, которые на несколько строк кода могут потратить несколько месяцев работы.
«В компании Google, прямо сейчас, пока я говорю, в нашем парке серверов, 1% всех CPU занимаются вычислениями внутри хештаблиц. Пока я говорю, более 8% всей оперативной памяти серверов занимают хештаблицы. И это только то, что относится к С++, я не знаю ситуации по Java»
Matt Kulukundis, CppCon 2017
Префиксное дерево (trie)
3 мин
Перевод
В этой статье обсудим такую структуру данных, как «префиксное дерево» (оно же нагруженное дерево, бор, trie, prefix tree). Кратко рассмотрим основы и реализуем наиболее важные операции: вставку, поиск по ключу и префиксный поиск.
Префиксное дерево (trie) — вставка и поиск
4 мин
Перевод
Префиксное дерево (нагруженное дерево, trie) — структура данных для эффективного поиска. С его помощью сложность поиска можно довести до оптимального уровня — длины ключа. Вспомним, что в хорошо сбалансированном бинарном дереве поиска данные можно найти за время, пропорциональное M * log N, где M — максимальная длина строки, а N — количество ключей в дереве. В префиксном дереве — O(M), но увеличиваются требования к памяти. Подробнее о применении префиксных деревьев см. в этой статье.
Подсчёт слов
24 мин
В статье рассказывается о решении задачки с собеса в одну российскую IT-контору.
В первые месяцы ковидной эры так случилось, что на моей текущей на тот момент работе всем уполовинили зарплату и я, недолго думая, пошёл на рынок труда. На собесе в одну известную российскую IT-компанию я получил эту задачу. Задачку нужно было просто решить: решить корректно, не "убив" при этом скорость "так, чтобы совсем ужас был".
Уже за рамками "вступительного испытания" ради спортивного интереса можно было посоревноваться с авторским решением в скорости. Спустя примерно год после упомянутых событий у меня появилось свободное время, пришли новые идеи и я попытался найти предельно быстрое решение, о чём и пойдёт речь в статье.
Красивое дерево PATRICIA (Реализация на C++)
13 мин
Туториал
Забытое, сложное, изумительное, красивое дерево со звуком ломающихся коленок.