Многие, наверное, пытались найти построение дерева общего вида, но поисковик находил только бинарные… Двоичное дерево поиска, обход двоичного дерева и могие другие алгоритмы.
Да, действительно, дерево общего вида нигде не используется, обход медленный, варианты использования небольшие.
Так вот, я задался этим вопросом и теперь поясню как все-таки дерево строится. Итак, в идеале структура дерева общего вида должна хранить три переменные:
Читать полностью »
Каждый, кто пытался запрограммировать хотя бы простейший редактор текста на низком уровне, сталкивался с задачей организации памяти для хранения редактируемого текста. Структура данных для хранения текста должна удовлетворять следующим требованиям:
Удовлетворить эти требования одновременно непросто. Если рассмотреть широкоизвестные структуры данных, такие как массивы, списки, деревья, стеки, очереди, кольцевые буфера — то такой структуры, которая бы позволила эффективно выполнить оба требования, не встречается. В случае массива имеем незначительные накладные расходы по памяти, но операция вставки имеет сложность O(n), где n — размер редактируемого текста. В случае списка сложность вставки и удаления составляет O(1), однако накладные расходы по памяти в несколько раз превышают размер собственно текста. Деревья, кучи, кольцевые буфера, ассоциативные массивы и прочие структуры и вовсе неприменимы для хранения текста в редакторе.
Встречаются гибридные решения, когда текст хранится в наборе массивов, которые, в свою очередь, объединены в список. Казалось бы, такой подход позволяет объединить преимущества массивов и списков (быстрая вставка/удаление при низких накладных расходах по памяти). Однако такое решение сложно в реализации. Также оно приводит к фрагментации памяти.
Предлагаю вашему вниманию эффективную структуру данных для хранения редактируемого текста, которая проста в реализации, имеет константные накладные расходы по памяти и быструю вставку/удаление в произвольном месте. Также она позволяет эффективно редактировать файлы, которые целиком не умещаются в оперативную память.
Несмотря на то, что эта структура данных была открыта давно и использовалась в текстовых редакторах на старых ЭВМ в 8-битную эпоху, это тайное знание предков было в значительной мере утеряно и в современных редакторах встречается редко. Попробуйте открыть файл, состоящий из одной строки мегабайт на 10, в Notepad или Far. Вставка и удаление символов будет длиться секундами.
Читать полностью »
Начну статью с того, что расскажу, как я познакомился с этой изящной конструкцией. Занимаясь олимпиадным программированием, мы с моим преподавателем решали много интересных задач. И вот однажды мне попалась следующая задача:
Распечатать в порядке возрастания все несократимые дроби, знаменатель которых не превосходит n, n<=100.
Прочитав условие задачи до конца, она не показалась мне сложной (она таковой и не является). Первое, что пришло мне в голову это просто перебрать все знаменатели от 2 до n и для каждого знаменателя перебрать числители от 1 до знаменателя, при условии, что числитель и знаменатель взаимно просты. Ну, а за тем отсортировать их по возрастанию.
Такое решение верно и задача прошла все назначенные ей тесты. Однако, мой преподаватель сказал, что задачу можно решить намного красивее (он уже сталкивался с этой конструкцией). Так я и познакомился с этой замечательной конструкцией — деревом Штерна-Броко.
Читать полностью »
Периодически проверяя нет ли реализации того или иного стандартного алгоритма в jdk, пришла мысль составить подобный обзор. Также интересны были причины наличия/отсутствия многих известных структур данных.
Формат обзора — только ключевые свойства и особенности структур и алгоритмов в составе jdk, подробности и детали — расписаны в javadoc или легко найти в исходниках.
Надеюсь на конструктивную критику и коллективный разум если что упустил.
Хватит вступлений, итак, давайте рассмотрим что включает в себя текущий jdk 7 и почему. Читать полностью »
Картинка для привлечения внимания демонстрирующая пример предстоящей «вложенности» камеры с парашютом в ранец.
Часть 1
Часть 2
Часть 3
В прошлый раз мы остановились на том, что у нас есть метод create(), который на основании глобала правил ^RuleDictionary создаёт элементы справочника. Нами был разобран пример создания элементов простейшего, одноуровневого справочника. Сегодня, рассмотрим каким образом, с помощью наших глобалов и методов, можно создавать вложенные структуры.
В коде программы, были использованы «прозрачные» переменные t и map, которые явно не передаются в методы, но доступны внутри них. Мне подсказали, что это не самый лучший способ демонстрации работы, особенно учитывая то, что для большинства, синтаксис Caché Object Script — нов. Поэтому, перед тем как приступить к вложенным структурам, внесём некоторые изменения в программу.
Слово «Живые», в названии статьи, означает, что механизмы, код и данные, из этих статей, используются в рабочем проекте.
Возможно, вам будет интересно посмотреть на некоторые варианты решений разработки БД (структур, механизмов).
На картинке изображён кусок кода, описывающего глобал правил справочника.
CRUD методы, в процессе своей работы, постоянно обращаются к этим правилам чтобы узнать, какие именно действия необходимо выполнить.
Ранее, мы остановились на том, что у нас есть следующие глобалы:
^Dictionary("Vehicle","TransmissionType",1,0,"UpdateTime")="62086,66625"
^Dictionary("Vehicle","TransmissionType",1,0,"uid")=888
^Dictionary("Vehicle","TransmissionType",2,0,"UpdateTime")="62086,66625"
^Dictionary("Vehicle","TransmissionType",2,0,"uid")=888
^NameDictionaryElement(1,"partUri",0)="akp"
^NameDictionaryElement(1,"partUri",0,"UpdateTime")="62086,66625"
^NameDictionaryElement(1,"ru",0)="АКП"
^NameDictionaryElement(1,"ru",0,"UpdateTime")="62086,66625"
^NameDictionaryElement(2,"partUri",0)="meh"
^NameDictionaryElement(2,"partUri",0,"UpdateTime")="62086,66625"
^NameDictionaryElement(2,"ru",0)="МЕХ"
^NameDictionaryElement(2,"ru",0,"UpdateTime")="62086,66625"
^IndexDictionary("Vehicle","TransmissionType","name","partUri","akp",1)=1
^IndexDictionary("Vehicle","TransmissionType","name","partUri","meh",2)=1
^IndexDictionary("Vehicle","TransmissionType","name","ru","акп",1)=1
^IndexDictionary("Vehicle","TransmissionType","name","ru","мех",2)=1
^IndexDictionary("Vehicle","TransmissionType","uid",888,1)=1
^IndexDictionary("Vehicle","TransmissionType","uid",888,2)=1
^RefsDictionary(1,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""name"",""partUri"",""akp"",1)")=1
^RefsDictionary(1,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""name"",""ru"",""акп"",1)")=1
^RefsDictionary(1,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""uid"",888,1)")=1
^RefsDictionary(2,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""name"",""partUri"",""meh"",2)")=1
^RefsDictionary(2,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""name"",""ru"",""мех"",2)")=1
^RefsDictionary(2,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""uid"",888,2)")=1
set ^Dictionary("Vehicle","TransmissionType",1,0,"UpdateTime")="62086,66625"
set ^Dictionary("Vehicle","TransmissionType",1,0,"uid")=888
set ^Dictionary("Vehicle","TransmissionType",2,0,"UpdateTime")="62086,66625"
set ^Dictionary("Vehicle","TransmissionType",2,0,"uid")=888
set ^NameDictionaryElement(1,"partUri",0)="akp"
set ^NameDictionaryElement(1,"partUri",0,"UpdateTime")="62086,66625"
set ^NameDictionaryElement(1,"ru",0)="АКП"
set ^NameDictionaryElement(1,"ru",0,"UpdateTime")="62086,66625"
set ^NameDictionaryElement(2,"partUri",0)="meh"
set ^NameDictionaryElement(2,"partUri",0,"UpdateTime")="62086,66625"
set ^NameDictionaryElement(2,"ru",0)="МЕХ"
set ^NameDictionaryElement(2,"ru",0,"UpdateTime")="62086,66625"
set ^IndexDictionary("Vehicle","TransmissionType","name","partUri","akp",1)=1
set ^IndexDictionary("Vehicle","TransmissionType","name","partUri","meh",2)=1
set ^IndexDictionary("Vehicle","TransmissionType","name","ru","акп",1)=1
set ^IndexDictionary("Vehicle","TransmissionType","name","ru","мех",2)=1
set ^IndexDictionary("Vehicle","TransmissionType","uid",888,1)=1
set ^IndexDictionary("Vehicle","TransmissionType","uid",888,2)=1
set ^RefsDictionary(1,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""name"",""partUri"",""akp"",1)")=1
set ^RefsDictionary(1,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""name"",""ru"",""акп"",1)")=1
set ^RefsDictionary(1,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""uid"",888,1)")=1
set ^RefsDictionary(2,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""name"",""partUri"",""meh"",2)")=1
set ^RefsDictionary(2,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""name"",""ru"",""мех"",2)")=1
set ^RefsDictionary(2,"^|""MONTOLOGY""|IndexDictionary(""Vehicle"",""TransmissionType"",""uid"",888,2)")=1
В прошлой статье мы рассмотрели пример справочника на MUMPS (Caché Object Script). Были разобраны структуры глобалов и метод retrieve. Мы научились простейшей операции — получению имени элемента по известному идентификатору. Рассматриваемые структуры были одноуровневыми. Опросы и комментарии, после статьи, показали, что тема в целом интересна. Сегодня рассмотрим примеры построения индексов для справочников. Все коды/идентификаторы/имена глобалов — настоящие. Основная идея данных статей — обмен знаниями/опытом разработки и проектирования живых баз данных.
Вкратце напомню основные моменты первой части:
По просьбе 4dmonster в примерах будут публиковаться полные версии команд. (wrtie вместо w и т.д.)
Освежим в памяти имеющиеся глобалы с данными:
^Dictionary("Vehicle","TransmissionType",1,0,"UpdateTime")="62086,66625"
^Dictionary("Vehicle","TransmissionType",1,0,"uid")=888
^Dictionary("Vehicle","TransmissionType",2,0,"UpdateTime")="62086,66625"
^Dictionary("Vehicle","TransmissionType",2,0,"uid")=888
^NameDictionaryElement(1,"partUri",0)="akp"
^NameDictionaryElement(1,"partUri",0,"UpdateTime")="62086,66625"
^NameDictionaryElement(1,"ru",0)="АКП"
^NameDictionaryElement(1,"ru",0,"UpdateTime")="62086,66625"
^NameDictionaryElement(2,"partUri",0)="meh"
^NameDictionaryElement(2,"partUri",0,"UpdateTime")="62086,66625"
^NameDictionaryElement(2,"ru",0)="МЕХ"
^NameDictionaryElement(2,"ru",0,"UpdateTime")="62086,66625"
Глобал ^Dictionary — содержит все элементы справочников и их свойства, глобал ^NameDictionaryElement — содержит названия элементов справочников на всех языках.
set ^Dictionary("Vehicle","TransmissionType",1,0,"UpdateTime")="62086,66625"
set ^Dictionary("Vehicle","TransmissionType",1,0,"uid")=888
set ^Dictionary("Vehicle","TransmissionType",2,0,"UpdateTime")="62086,66625"
set ^Dictionary("Vehicle","TransmissionType",2,0,"uid")=888
set ^NameDictionaryElement(1,"partUri",0)="akp"
set ^NameDictionaryElement(1,"partUri",0,"UpdateTime")="62086,66625"
set ^NameDictionaryElement(1,"ru",0)="АКП"
set ^NameDictionaryElement(1,"ru",0,"UpdateTime")="62086,66625"
set ^NameDictionaryElement(2,"partUri",0)="meh"
set ^NameDictionaryElement(2,"partUri",0,"UpdateTime")="62086,66625"
set ^NameDictionaryElement(2,"ru",0)="МЕХ"
set ^NameDictionaryElement(2,"ru",0,"UpdateTime")="62086,66625"
А теперь посмотрим как может быть устроен индекс справочника, и разберёмся для чего он нужен.
Читать полностью »
На хабре часто можно встретить различные статьи о том как сделано то или то, с непосредственной реализацией, кодом, примерами, обоснованиями (пусть даже спорными). Кто-то выкладывает пример контролла, кто-то даёт практические советы по яваскрипту. Однако я не видел, чтобы кто-нибудь, рассказывал об организации структуры БД. Дальше каких-то школьных примеров это не заходит (если ошибаюсь поправьте и дайте ссылки). Нет, холивары SQL vs NoSQL меня не интересуют. По моему скромному убеждению — СУБД вторична в вопросах организации БД. Вопросы производительности конкретных СУБД становятся актуальными далеко не сразу. Какая бы ни была выбрана СУБД, под определённую задачу, к производительности предъявляется всего одно требование — производительность должна быть достаточной. А вот пути достижения этой самой достаточности, способы удобно и красиво разместить данные — чтобы быстро и легко их извлекать, организация справочников и индексов, ввода и вывода, способы масштабирования и/или изменения структуры БД в течении жизни, используемые методики, решённые и нерешённые проблемы, полезные рецепты и советы — это всё то, о чём я хочу поговорить.
Разработка структур БД очень интересный и нетривиальный процесс. В этой обширной области встречается мало живых примеров, которые можно посмотреть, обсудить. Неужели вам, разработчики БД, всегда всё ясно что и как делать? Давайте делиться знаниями, давайте спрашивать, рассказывать, обсуждать, узнавать. Какая разница таблица или объект или глобал — важно какой смысл вкладывается, какие связи выстраиваются, какими средствами эти связи реализовываются.
Я не работаю в интерсистемс, это указано в моём профайле только чтобы иметь возможность размещать статьи в их блог (отдельного хаба для MUMPS или COS на хабре нет). Так что описанные мной методы могут не совпадать с «заводскими» рекомендациями использования СУБД Cache и языка Cache Object Script.
Пару дней назад был опубликован перевод, в котором мой подход, к программированию БД, называли экстремальным — я с этим не совсем согласен. В комментариях, было как минимум три человека (Ogoun uaoleg 4dmonster), которые сказали, что им было бы интересно посмотреть на живое использование MUMPS и узнать почему не надо бояться глобалов. Для этих людей и всех тех, кому интересно обсудить затронутые мной темы, я и пишу данную статью.
Читать полностью »
Рассмотрим вариант реализации связных списков через замыкания.
Для обозначения списков будем использовать нотацию, похожую на Haskell: x:xs, где x — начало списка (head), xs — продолжение (tail).
В качестве языка реализации я выбрал JavaScript.
Если Вы программируете на Си и Вам не хватает типизированных контейнеров, которые есть в языках высокого уровня, добро пожаловать под кат:
Читать полностью »