Рубрика «структуры данных» - 9

На хабре часто можно встретить различные статьи о том как сделано то или то, с непосредственной реализацией, кодом, примерами, обоснованиями (пусть даже спорными). Кто-то выкладывает пример контролла, кто-то даёт практические советы по яваскрипту. Однако я не видел, чтобы кто-нибудь, рассказывал об организации структуры БД. Дальше каких-то школьных примеров это не заходит (если ошибаюсь поправьте и дайте ссылки). Нет, холивары SQL vs NoSQL меня не интересуют. По моему скромному убеждению — СУБД вторична в вопросах организации БД. Вопросы производительности конкретных СУБД становятся актуальными далеко не сразу. Какая бы ни была выбрана СУБД, под определённую задачу, к производительности предъявляется всего одно требование — производительность должна быть достаточной. А вот пути достижения этой самой достаточности, способы удобно и красиво разместить данные — чтобы быстро и легко их извлекать, организация справочников и индексов, ввода и вывода, способы масштабирования и/или изменения структуры БД в течении жизни, используемые методики, решённые и нерешённые проблемы, полезные рецепты и советы — это всё то, о чём я хочу поговорить.

Разработка структур БД очень интересный и нетривиальный процесс. В этой обширной области встречается мало живых примеров, которые можно посмотреть, обсудить. Неужели вам, разработчики БД, всегда всё ясно что и как делать? Давайте делиться знаниями, давайте спрашивать, рассказывать, обсуждать, узнавать. Какая разница таблица или объект или глобал — важно какой смысл вкладывается, какие связи выстраиваются, какими средствами эти связи реализовываются.

Я не работаю в интерсистемс, это указано в моём профайле только чтобы иметь возможность размещать статьи в их блог (отдельного хаба для MUMPS или COS на хабре нет). Так что описанные мной методы могут не совпадать с «заводскими» рекомендациями использования СУБД Cache и языка Cache Object Script.

Пару дней назад был опубликован перевод, в котором мой подход, к программированию БД, называли экстремальным — я с этим не совсем согласен. В комментариях, было как минимум три человека (Ogoun uaoleg 4dmonster), которые сказали, что им было бы интересно посмотреть на живое использование MUMPS и узнать почему не надо бояться глобалов. Для этих людей и всех тех, кому интересно обсудить затронутые мной темы, я и пишу данную статью.
Читать полностью »

Рассмотрим вариант реализации связных списков через замыкания.

Для обозначения списков будем использовать нотацию, похожую на Haskell: x:xs, где x — начало списка (head), xs — продолжение (tail).

Связные списки в функциональном стиле

В качестве языка реализации я выбрал JavaScript.

Конструируем список

Читать полностью »

Если Вы программируете на Си и Вам не хватает типизированных контейнеров, которые есть в языках высокого уровня, добро пожаловать под кат:
Читать полностью »

С этой структурой данных можно ознакомиться в этом посте и её модификацией для нахождения максимума в этом. Но я нигде не встречал реализацию с изменением элементов на отрезке, поэтому решил поделиться тем, что сумел получить самостоятельно.
Читать полностью »

С++ библиотека от Google с контейнерами map и set на B деревьяхОдин из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит различные контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).

Разница в том, что контейнеры в STL реализованы на чёрно-красных деревьях, а аналогичные контейнеры cpp-btree — на B-деревьях. При этом в определённых ситуациях достигается существенный выигрыш в использовании памяти (на элементах маленького размера) и в производительности (на больших размерах контейнера).

B-деревья известны как инструмент для работы с дисковой памятью: базами данных и файловой системой. Но те же свойства, которые дают выигрыш там, позволяют эффективнее использовать и оперативную память. Каждый узел чёрно-красного дерева содержит один элемент, требует три указателя плюс по биту информации на элемент для сбалансированности. Для сравнения, контейнеры на B-деревьях хранят несколько элементов на узел, поэтому уменьшают излишек указателей и экономят значительное количество памяти.
Читать полностью »

Общий привет.

Недавно, для шлифовки морфологического словаря, способного (предположительно) генерировать все возможные формы слова из инфинитива — мне понадобился достаточно объемный частотный словарь русского языка. Частотный словарь — вещь очень простая, слова в нем упорядочены по частоте, с которой они встречаются в анализируемом тексте.
Читать полностью »

Прежде чем читать эту статью, нужно понимать, что такое декартово дерево по неявному ключу (это тема не одной статьи, поэтому об этом лучше почитать тут). Сжатие пространста — метод, используемый для сжатия на отрезке данных. Например, вместо того, чтобы хранить множество {1, 1, 1, 2, 2, 2, 3, 1, 1} будем хранить {1 x 3, 2 x 3, 3 x 1, 1 x 2}.
Теперь попробуем сжимать пространство с помощью такого метода и иметь возможность выполнять онлайн операции с любым отрезком.
Читать полностью »

Пару недель назад, необходимо было освежить информацию в голове информацию по структурам данных и алгоритмам для собеседования. Первым делом полез на www.coursera.org, где хотел пробежаться по некоторым лекциям курса Алгоритмы, там же были две сводные таблички, которые в процессе изучения курса взял на заметку — отлично помогали запомнить сложность операций. Но, к моему удивлению, материалы пройденного курса стали недоступны. Быстрое гугление, в надежде, что кто-нибудь выложил лекции на торрентах, к сожалению, не дало результатов. В итоге, я нашел полную коллекцию слайдов по данному курсу. Спешу Читать полностью »

Привет читатели!

После затяжной паузы, я попробую продолжить визуализировать структуры данных в Java. В предыдущих статьях были замечены: ArrayList, LinkedList, HashMap. Сегодня заглянем внутрь к LinkedHashMap.

Структуры данных в картинках. LinkedHashMap

Из названия можно догадаться что данная структура является симбиозом связанных списков и хэш-мапов. Действительно, LinkedHashMap расширяет класс HashMap и реализует интерфейс Map, но что же в нем такого от связанных списков? Давайте будем разбираться.

Читать полностью »

Доделал на днях питонью библиотеку datrie, реализующую префиксное дерево (см. википедию или хабр), спешу поделиться.

Если вкратце, то можно считать, что datrie.Trie — это замена стандартному питоньему dict, которая при определенных условиях (ключи — строки) занимает меньше памяти, имеет сравнимую скорость получения отдельного элемента и поддерживает дополнительные операции (получение всех префиксов данной строки, получение всех строк, начинающихся с данной строки и др.), которые работают примерно так же быстро, как и «словарные» операции.

Работает под Python 2.6-3.3, поддерживает юникод, лицензия LGPL.

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js