С этой структурой данных можно ознакомиться в этом посте и её модификацией для нахождения максимума в этом. Но я нигде не встречал реализацию с изменением элементов на отрезке, поэтому решил поделиться тем, что сумел получить самостоятельно.
Читать полностью »
Метка «структуры данных» - 2
Дерево Фенвика с модификацией на отрезке
2013-02-27 в 10:39, admin, рубрики: Алгоритмы, дерево Фенвика, Программирование, структуры данных, метки: дерево Фенвика, Программирование, структуры данныхС++ библиотека от Google с контейнерами map и set на B-деревьях
2013-02-12 в 20:33, admin, рубрики: c++, Алгоритмы, Программирование, структуры данных, метки: b+ tree, структуры данных 
Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит различные контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).
Разница в том, что контейнеры в STL реализованы на чёрно-красных деревьях, а аналогичные контейнеры cpp-btree — на B-деревьях. При этом в определённых ситуациях достигается существенный выигрыш в использовании памяти (на элементах маленького размера) и в производительности (на больших размерах контейнера).
B-деревья известны как инструмент для работы с дисковой памятью: базами данных и файловой системой. Но те же свойства, которые дают выигрыш там, позволяют эффективнее использовать и оперативную память. Каждый узел чёрно-красного дерева содержит один элемент, требует три указателя плюс по биту информации на элемент для сбалансированности. Для сравнения, контейнеры на B-деревьях хранят несколько элементов на узел, поэтому уменьшают излишек указателей и экономят значительное количество памяти.
Читать полностью »
Создание частотного словаря на основе анализа библиотеки художественной литературы
2012-12-12 в 9:42, admin, рубрики: Компьютерная лингвистика, оптимизация кода, Песочница, Семантическая Сеть, структуры данных, метки: Компьютерная лингвистика, оптимизация кода, структуры данныхОбщий привет.
Недавно, для шлифовки морфологического словаря, способного (предположительно) генерировать все возможные формы слова из инфинитива — мне понадобился достаточно объемный частотный словарь русского языка. Частотный словарь — вещь очень простая, слова в нем упорядочены по частоте, с которой они встречаются в анализируемом тексте.
Читать полностью »
Декартовы деревья по неявному ключу + сжатие пространства
2012-12-03 в 8:21, admin, рубрики: Алгоритмы, Песочница, Программирование, структуры данных, метки: Алгоритмы, структуры данных Прежде чем читать эту статью, нужно понимать, что такое декартово дерево по неявному ключу (это тема не одной статьи, поэтому об этом лучше почитать тут). Сжатие пространста — метод, используемый для сжатия на отрезке данных. Например, вместо того, чтобы хранить множество {1, 1, 1, 2, 2, 2, 3, 1, 1} будем хранить {1 x 3, 2 x 3, 3 x 1, 1 x 2}.
Теперь попробуем сжимать пространство с помощью такого метода и иметь возможность выполнять онлайн операции с любым отрезком.
Читать полностью »
Алгоритмы и структуры данных — шпаргалка
2012-10-27 в 8:57, admin, рубрики: coursera, Алгоритмы, сортировки, структуры данных, Учебный процесс в IT, метки: coursera, Алгоритмы, сортировки, структуры данныхПару недель назад, необходимо было освежить информацию в голове информацию по структурам данных и алгоритмам для собеседования. Первым делом полез на www.coursera.org, где хотел пробежаться по некоторым лекциям курса Алгоритмы, там же были две сводные таблички, которые в процессе изучения курса взял на заметку — отлично помогали запомнить сложность операций. Но, к моему удивлению, материалы пройденного курса стали недоступны. Быстрое гугление, в надежде, что кто-нибудь выложил лекции на торрентах, к сожалению, не дало результатов. В итоге, я нашел полную коллекцию слайдов по данному курсу. Спешу Читать полностью »
Структуры данных в картинках. LinkedHashMap
2012-08-07 в 13:01, admin, рубрики: java, структуры данных, метки: java, структуры данныхПривет читатели!
После затяжной паузы, я попробую продолжить визуализировать структуры данных в Java. В предыдущих статьях были замечены: ArrayList, LinkedList, HashMap. Сегодня заглянем внутрь к LinkedHashMap.
Из названия можно догадаться что данная структура является симбиозом связанных списков и хэш-мапов. Действительно, LinkedHashMap расширяет класс HashMap и реализует интерфейс Map, но что же в нем такого от связанных списков? Давайте будем разбираться.
Префиксные деревья в Python
2012-07-17 в 11:24, admin, рубрики: python, python3, trie, структуры данных, метки: python, python3, trie, структуры данныхДоделал на днях питонью библиотеку datrie, реализующую префиксное дерево (см. википедию или хабр), спешу поделиться.
Если вкратце, то можно считать, что datrie.Trie — это замена стандартному питоньему dict, которая при определенных условиях (ключи — строки) занимает меньше памяти, имеет сравнимую скорость получения отдельного элемента и поддерживает дополнительные операции (получение всех префиксов данной строки, получение всех строк, начинающихся с данной строки и др.), которые работают примерно так же быстро, как и «словарные» операции.
Работает под Python 2.6-3.3, поддерживает юникод, лицензия LGPL.
Персистентные деревья отрезков
2012-04-24 в 17:51, admin, рубрики: Алгоритмы, персистентные структуры данных, Программирование, структуры данных, метки: персистентные структуры данных, структуры данныхВведение
Структуры данных можно разделить на две группы: эфемерные (ephemeral) и персистентные (persistent).
Эфемерными называются структуры данных, хранящие только последнюю свою версию.
Персистентные структуры, то есть те, которые сохраняют все свои предыдущие версии, в свою очередь можно разделить еще на две подгруппы: если структура данных, позволяет изменять только последнюю версию, она называется частично персистентной (partially persistent), если же позволяется изменять любую версию, такая структура считается полностью персистентной (fully persistent).
Далее будет рассмотрено дерево отрезков и его полностью персистентная версия.
Весь код доступен на GitHub.
Читать полностью »
Структура Radix Tree для сжатия данных
2012-03-31 в 15:45, admin, рубрики: c++, radix tree, Алгоритмы, исходники, сжатие данных, структуры данных, метки: radix tree, Алгоритмы, исходники, сжатие данных, структуры данных 
Этот топик повествует об использовании Radix Tree на практическом примере. Radix Tree или дерево остатков — это структура данных, формируемая по принципу хранение значений в листовом узле. Промежуточные узлы представляют собой элемент конечного значения. Это может быть бит для чисел, символ для строк или цифра для номера, как в примере ниже. Приведенный алгоритм сжатия с использованием Radix Tree используется в реальной embeded системе, для хранения параметров телефонного файрвола.
Читать полностью »