Привет. Ей! Не говорите “Да блин! Я знаю, чем отличается список от вектора, мне не нужна эта статья”. Прошу, загляните под кат и освежите свои знания. Я надеюсь, однако, что вы сможете почерпнуть из этой статьи намного больше и, некоторые, возможно, наконец-то разберутся, почему существует так много типов данных для коллекций объектов.
Читать полностью »
Списки с пропусками — это структура данных, которая может применяться вместо сбалансированных деревьев. Благодаря тому, что алгоритм балансировки вероятностный, а не строгий, вставка и удаление элемента в списках с пропусками реализуется намного проще и значительно быстрее, чем в сбалансированных деревьях.
Списки с пропусками — это вероятностная альтернатива сбалансированным деревьям. Они балансируются с использованием генератора случайных чисел. Несмотря на то, что у списков с пропусками плохая производительность в худшем случае, не существует такой последовательности операций, при которой бы это происходило постоянно(примерно, как в алгоритме быстрой сортировки со случайным выбором опорного элемента). Очень маловероятно, что эта структура данных значительно разбалансируется(например, для словаря размером более 250 элементов, вероятность того, что поиск займёт в три раза больше ожидаемого времени меньше одной миллионной).
Балансировать структуру данных вероятностно проще, чем явно обеспечивать баланс. Для многих задач списки пропуска — это более естественное представление данных по сравнению с деревьями. Алгоритмы получаются более простыми для реализации и, на практике, более быстрыми по сравнению со сбалансированными деревьями. Кроме того, списки с пропусками очень эффективно используют память. Они могут быть реализованы так, чтобы на один элемент приходился в среднем примерно 1.33 указатель(или даже меньше) и не требуют хранения для каждого элемента дополнительной информации о балансе или приоритете.
Читать полностью »
Каждый, кто пытался запрограммировать хотя бы простейший редактор текста на низком уровне, сталкивался с задачей организации памяти для хранения редактируемого текста. Структура данных для хранения текста должна удовлетворять следующим требованиям:
Удовлетворить эти требования одновременно непросто. Если рассмотреть широкоизвестные структуры данных, такие как массивы, списки, деревья, стеки, очереди, кольцевые буфера — то такой структуры, которая бы позволила эффективно выполнить оба требования, не встречается. В случае массива имеем незначительные накладные расходы по памяти, но операция вставки имеет сложность O(n), где n — размер редактируемого текста. В случае списка сложность вставки и удаления составляет O(1), однако накладные расходы по памяти в несколько раз превышают размер собственно текста. Деревья, кучи, кольцевые буфера, ассоциативные массивы и прочие структуры и вовсе неприменимы для хранения текста в редакторе.
Встречаются гибридные решения, когда текст хранится в наборе массивов, которые, в свою очередь, объединены в список. Казалось бы, такой подход позволяет объединить преимущества массивов и списков (быстрая вставка/удаление при низких накладных расходах по памяти). Однако такое решение сложно в реализации. Также оно приводит к фрагментации памяти.
Предлагаю вашему вниманию эффективную структуру данных для хранения редактируемого текста, которая проста в реализации, имеет константные накладные расходы по памяти и быструю вставку/удаление в произвольном месте. Также она позволяет эффективно редактировать файлы, которые целиком не умещаются в оперативную память.
Несмотря на то, что эта структура данных была открыта давно и использовалась в текстовых редакторах на старых ЭВМ в 8-битную эпоху, это тайное знание предков было в значительной мере утеряно и в современных редакторах встречается редко. Попробуйте открыть файл, состоящий из одной строки мегабайт на 10, в Notepad или Far. Вставка и удаление символов будет длиться секундами.
Читать полностью »
Данный пост является переводом и предназначен для новичков. Ну или для тех, кто забыл лекции с начальных курсов своих вузов. Скорее всего, данный материал уже попадался на хабре в той или иной модификации, но здесь упор на PHP и его особенности.
Структуры данных или Абстрактный Тип Данных (ADT) — это модель, определенная как некий набор операций, которые могут быть применены к самой себе и ограничена тем, какой результат дают эти операции.
Большинство из нас сталкиваются со стеком и очередью в повседневной жизни, но что общего между очередью в супермакете и структурой данных? В этом мы и попробуем разобраться в данной статье, где также будут описаны деревья.
Мы в Буруках любим не только людей и цифры. Мы также без устали совершенствуемся во владении нашим основным инструментом, языком Python. Ссылка для тех, кто хочет совершенствоваться с нами. В этой статье-переводе автор разбирает устройство namedtuple и по ходу рассказывает об одной из основных концепций языка.
Пару дней назад я был на пути в Сан-Франциско. Интернета в самолёте не было, поэтому я читал исходники стандартной библиотеки Python 2.7. Реализация namedtuple показалась мне особенно интересной, наверное, потому, что на деле всё гораздо проще, чем я думал раньше.
Вот здесь лежат исходники. Если вы никогда раньше не знали о namedtuple, то рекомендую ознакомиться с этой функцией.
Читать полностью »
Начну статью с того, что расскажу, как я познакомился с этой изящной конструкцией. Занимаясь олимпиадным программированием, мы с моим преподавателем решали много интересных задач. И вот однажды мне попалась следующая задача:
Распечатать в порядке возрастания все несократимые дроби, знаменатель которых не превосходит 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"
А теперь посмотрим как может быть устроен индекс справочника, и разберёмся для чего он нужен.
Читать полностью »