Если Вы программируете на Си и Вам не хватает типизированных контейнеров, которые есть в языках высокого уровня, добро пожаловать под кат:
Читать полностью »
Рубрика «структуры данных» - 10
Автоматическая генерация типизированных структур данных для Си
2013-03-02 в 9:34, admin, рубрики: ruby, Алгоритмы, Программирование, структуры данных, метки: c++, ruby, Программирование, структуры данныхДерево Фенвика с модификацией на отрезке
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.
Структуры данных, используемые в Redis
2012-05-17 в 17:56, admin, рубрики: nosql, redis, Алгоритмы, структуры данных От переводчика:
Хочу представить вашему вниманию перевод ответа одного из разработчиков Redis, на вопрос о том, какие структуры данных используются внутри Redis. Оригинальную дискуссию вы можете найти на stackoverflow.
Я попробую ответить на вопрос, но начну с того, что на первый взгляд может показаться странным: если вы не интересуетесь внутренностями Redis, вы не должны заботиться о том, как реализованы структуры данных изнутри. Причина этому проста — сложность каждой команды Redis вы можете найти в документации, и если у вас есть набор операций и их вычислительная сложность, то единственное, что вам нужно, это некоторое представление об использовании памяти (и потому, что мы делаем много оптимизаций, в зависимости от данных, лучший способ получить эти последние цифры это тесты в реальных условиях)
Но поскольку вы спросили, вот внутренние реализации каждой структуры данных Redis:
- Строки реализованы с использованием библиотеки динамических строк C, так что мы не платим (говоря асимптотически) за выделение памяти в операциях добавления. Таким образом мы получаем сложность добавления O(N), вместо, например, квадратичной.
- Списки реализованы как связные списки.
- Множества и Хэши реализованы как хэш-таблицы.
- Упорядоченные множества реализованы как списки с пропусками (особый тип сбалансированных деревьев)