Двоичное дерево, двоичное дерево поиска, двоичная куча, B-дерево

Публикация № 705641

Разработка - Математика и алгоритмы

В большинстве реляционных СУБД в качестве структуры данных для индексов (та или иная их реализация) используются именно деревья. И не просто деревья, а сбалансированные деревья поиска. В этой статье как раз о них.

В большинстве реляционных СУБД в качестве структуры данных для индексов (та или иная их реализация) используются именно деревья. И не просто деревья, а сбалансированные деревья поиска. В этой статье как раз о них.

Сами по себе деревья бесполезны, если мы не можем выполнять с ними определенные операции. К таким операциям обычно относят: поиск элемента, поиск минимального (максимального) элемента, вставка, удаление. В разрезе этих операций мы и рассмотрим каждое из 4 деревьев отдельно. Каждое дерево имеет свои особенности, связанные как правило с организацией хранения данных, но при этом они все связаны между собой:

  • Двоичное дерево поиска и двоичная куча - это частный случай обычного двоичного дерева;
  • B-дерево - это разновидность дерева поиска. Как правило не является двоичным деревом.

Теперь рассмотрим каждое дерево отдельно.

Двоичное дерево

Двоичное дерево (binary tree) - дерево, в котором каждый узел имеет не более двух потомков. Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. В двоичном дереве могут храниться любые данные, в любом порядке.

Пример двоичного дерева:

Бинарное дерево

Особый интерес из себя не представляет, нужно только для понимания что такое вообще двоичное дерево. Нас интересуют следующие два дерева, которые являются его разновидностью.

Двоичное дерево поиска (binary search tree)

Двоичное дерево поиска - это двоичное дерево, для которого выполняются следующие дополнительные условия:

  • Оба поддерева — левое и правое — являются двоичными деревьями поиска.
  • У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
  • В то время, как значения ключей данных у всех узлов правого поддерева (того же узла X) больше, нежели значение ключа данных узла X.

Пример дерева:

Двоичное дерево поиска

Структура дерева зависима от порядка заполнения ключей. Если мы будем заполнять предварительно отсортированными массивом ключей (например: 10; 20; 30; 40), то мы получим экстремально сбалансированное дерево. Т.е. дерево, у которого высота равна количеству элементов.

Поиск элемента

Поиск начинается с корня. При этом значение каждого узла сравнивается с искомым значением:

  • Если искомое значение равно значению узла, то поиск завершен.
  • Если искомое значение меньше значения узла, то переходим к обработке левого дерева.
  • Если искомое значение больше значения узла, то переходим к обработке правого дерева.

Для поиска ключа 23 мы нужно 4 итерации (начинаем с корня, ключ расположен на 4 уровне):

Поиск в двоичном дереве поиска

Добавление элемента

Добавление аналогично поиску элемента, только если отсутствует дочерний узел нужно создать его, вставляя добавляемый элемент. Добавим ключ 7 в дерево:

Добавление ключа 7 в двоичном дереве поиска

Удаление элемента

А вот операция удаления уже сложнее. Нужно сначала найти нужный нам ключ, а потом уже обработать его. Всего возможны 3 варианта:

  1. узел не имеет дочерних узлов;
  2. узел имеет один дочерний узел;
  3. узел имеет два дочерних узла.

Если узел не имеет дочерних узлов, то просто удаляем его. Удалим ключ 23:

Удаление ключа в двоичном дереве поиска. Нет дочерних узлов

Если узел имеет только один дочерний узел, то заменяем связь с родителем узла на дочерний узел. Удалим узел 11:

Удаление ключа в двоичном дереве поиска. Один дочерний узел

Если же узел имеет два дочерних узла, тогда надо найти следующий элемент в правом дочернем узле (т.е. минимальный узел, который не имеет дочерних узлов). Удалим узел 21:

Удаление узла в двоичном дереве поиска. Два дочерних узла

Двоичная куча (binary heap)

Двоичная куча - двоичное дерево, для которого выполнены три условия:

  • Значение в любой вершине не меньше, чем значения её потомков.
  • Глубина листьев (расстояние до корня) отличается не более чем на 1 уровень.
  • Последний уровень заполняется слева направо.

Существуют также кучи, где значение в любой вершине, наоборот, не больше, чем значения её потомков. Структура данных как двоичная куча используется в основном в алгоритмах сортировки.

Пример двоичной кучи:

Двоичная куча

Над кучей можно выполнять следующие операции:

  • Добавить элемент в кучу;
  • Исключить максимальный элемент из кучи;
  • Изменить значение любого элемента.

Добавление элемента

Добавление элемента всегда происходит последовательно в первый незаполненный узел, начиная сверху вниз и перемещаясь слева направо по уровню. Добавим в кучу ключ 16:

Добавление элемента в двоичную кучу

Для удобства на картинке все узлы пронумерованы, начиная с единицы (корневой узел). В нашем случае самым крайним и свободным узлом оказался узел под номером 12. Туда-то мы и записали свое значение.

Если бы на 4-ом уровне дерева все узлы были заполнены (т.е. узлы с номерами от 8 до 15), тогда мы бы добавили левый дочерний узел к элементу 8, как самому левому узлу 4-го уровня, при этом бы образовался новый 5-ый уровень.

При этом необходимо выполнить условие, что элемент родительского узла должен быть всегда больше элемента дочернего. Поэтому, если наше значение меньше значения родителя, то необходимо родителя и потомка поменять местами:

Добавление элемента в двоичную кучу

Двигаемся вверх по дереву, пока значение нашего узла не станет меньше значения родителя.

Исключение максимального элемента

Т.к. самым максимальным узлом кучи является корневой элемент, то необходимо удалить именно его. На его место записывается самый последний элемент дерева (нумерация элементов сверху вниз, слева направо):

Исключение максимального элемент двоичной кучи

Если при этом нарушилось свойство кучи и значение узла стало меньше значения одного из дочерних узлов (или обоих), то меняем местами значение текущего узла и дочернего. Сравнение нужно делать сперва с левым дочерним узлом, затем с правым. Рекурсивно продолжать сравнение, спускаясь вниз по измененным узлам.

В нашем примере ключ 10 меньше 22 и 17, но т.к. узел с ключом 22 находится левее, то берем именно его. Далее опять сравниваем с дочерними узлами - 10 меньше 11, поэтому меняем с этим узлом. На 4-ом уровне ключ 10 уже больше 7 и 2, поэтому прекращаем операцию.

Исключение максимального элемент двоичной кучи

Изменение значения элемента

При изменении элемента кучи возможны два варианта:

  • новое значение меньше значения исходного элемента. В этом случае необходимо менять местами дочерний и текущий узел, спускаясь вниз по дереву до тех пор, пока выполняется условие, что значение родительского узла больше значения дочернего узла (т.е. алгоритм тот же, что при исключении максимального элемента из дерева).
  • новое значение больше значения исходного элемента. В этом случае нужно менять местами текущий и родительский узел, поднимаясь вверх по дереву, до тех пор, пока значение родительского узла не будет больше значения текущего узла (алгоритм аналогичен добавлению нового элемента).

B-дерево (B-tree)

B-дерево - дерево, которое является разновидностью двоичного дерева поиска. Особенностями В-деревьев является:

  • сбалансированность - длина пути от корня до любого листового элемента одинакова;
  • ветвистость - в отличие от двоичных деревьев каждый узел может ссылаться на множество потомков;
  • отсортированность - ключи в дереве хранятся в неубывающем порядке;
  • логарифмическое время работы всех стандартных операций (поиск, вставка, удаление).

B-деревья (или их разновидности) используются в индексах большинства реляционных СУБД. Оптимизированы специально для работы с дисковой подсистемой.

При построении дерева применяется параметр t, который называется минимальной степенью. Количество ключей в узле (за исключением корневого) должно быть от t – 1 до 2t – 1.

Пример B-дерева (t=3):

Стоит обратить внимание, что дочерние узлы ссылаются не на сам родитель, а разделитель между ключами этого родителя.

Поиск элемента

Алгоритм поиска элемента схож с алгоритмом двоичного дерева поиска. Обход начинается с корня. Так как все ключи хранятся в неубывающем порядке, то поиск ведем слева на право. Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему потомку. Повторяем пока ключ не найден или не дошли до листа.

Добавление элемента

Добавление элемента уже интереснее. Возможны два случая:

  1. Если узел содержит от t-1 до 2t-2 элемента. Т.е. узел не заполнен. В этом случае просто в узел добавляется новый элемент и все.
  2. Если узел содержит 2t-1 ключей (узел заполнен), то при добавлении в него он разбивается на два по t-1 элемента. При этом средний элемент (медиана) узла идет в родительский узел. Соответственно, если и родительский узел был заполнен, то разбиваем и его разбиваем на два. Если разбивается корневой узел, то увеличивается высота дерева. Добавим в дерево ключ 12:

Добавление элемента в B-дерево

Удаление элемента

Удаление происходит сложнее, потому что при удалении происходит перестроение дерева. Удалять можно как из листового узла, так и из внутреннего.

Рассмотрим удаление из листового узла:

  1. Если в узле больше, чем t-1 ключей, то просто удаляем ключ.
  2. Если в t-1 ключей (минимальное количество) и существует соседний узел(находящийся рядом с ним и имеющий такого же родителя), который содержит больше t-1 ключей. В этом случае ближайший ключ узла-соседа перейдет в родительский узел в качестве разделителя, а ключ узла-родителя перейдет в наш узел, где мы удаляем ключ. Для примера удалим ключ 44.

Удаление в листовом узле B-дерево

  1. Если в узле  t-1 ключ (минимальное количество) и все соседние узлы, содержат t-1 ключ (минимальное количество), то мы объединяем его с каким-либо соседом, удаляем нужный ключ. И тот ключ из узла-родителя, который был разделителем для этих двух «бывших» соседей, переместим в наш новообразовавшийся узел (он будет в нем медианой).

Удаление в листовом узле B-дерево

Специальные предложения

Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Vladimir Litvinenko 24.11.17 20:05 Сейчас в теме
Хм, а что стало с сайтом debug1c.ru? Узнал статью, зашел на сайт, а там большая часть материалов пропала, включая эту публикацию.
Это бедствие стихийное, или запланированное? ))
2. Irwin 354 24.11.17 22:09 Сейчас в теме
(1)Сайт в скором времени прекратит свое существование.
3. kuzyara 1073 01.12.17 04:36 Сейчас в теме
В ms sql насколько я знаю, получить данные индекса нельзя.
В Oracle посмотреть на внутреннюю структуру индекса можно, для этого выгрузить индекс в дамп следующей командой:
alter session set events 'immediate trace name treedump level nnnn; где nnnn это object_id индекса.

Эта команда выгрузит структуру указанного индекса в файл в папку user_dump_dest в $ORACLE_BASE/admin/SID/udump.
Содержимое файла выглядит приблизительно так:
----- begin tree dump
branch: 0x2402004 37756932 (0: nrow: 104, level: 1)
leaf: 0x2402005 37756933 (-1: nrow: 517 rrow: 517)
leaf: 0x2402006 37756934 (0: nrow: 514 rrow: 514)
leaf: 0x2402007 37756935 (1: nrow: 481 rrow: 481)
leaf: 0x2402008 37756936 (2: nrow: 481 rrow: 481)
leaf: 0x2403309 37761801 (3: nrow: 481 rrow: 481)
...
leaf: 0x240336d 37761901 (97: nrow: 481 rrow: 481)
leaf: 0x240336e 37761902 (98: nrow: 482 rrow: 482)
leaf: 0x240336f 37761903 (99: nrow: 481 rrow: 481)
leaf: 0x2403370 37761904 (100: nrow: 481 rrow: 481)
leaf: 0x2403372 37761906 (101: nrow: 481 rrow: 481)
leaf: 0x2403373 37761907 (102: nrow: 377 rrow: 377)
----- end tree dump
По дампу видно, что индекс состоит из одного корневого блока и nrow: 104 листовых блоков (с -1 до 102 включительно).
Строки начинающиеся на branch - это либо корневой блок, либо блоки ветвления.
Листовые блоки начинаются на leaf.

Treedump выводит простой список на каждый блок индекса, в соответствии со структурой.
За ключевым словом вида ветки идут цифры hex (0x2402004) и decimal (3775693) - это Relative Block Address (RBA) - адрес физического расположения блока. Используя этот адрес блока, можно получить id файла и блока функциями пакета dbms_utility и выгрузить содержимое конкретных блоков индекса.

Дальше, nrow - это суммарное количество ключей или строк включая строки, которые отмечены как удаленные, а rrow - количество ключей или строк.

В этом дампе мы увидели общую структуру индекса и сколько ключей хранятся в каждом узле индекса, но в ней нет самих значений ключей.

Все это информация о дереве.

Как хранятся значения самих ключей подробно описано на сайте одного китайца, имя которого прилично выговорить я так и не смог ;)
kirinalex; Aleskey_K; +2 Ответить
4. Irwin 354 01.12.17 17:04 Сейчас в теме
(3) А как же команды DBCC IND и DBCC PAGE в MS SQL? С помощью этих команд можно посмотреть физическую структуру базы данных. А также DVM-функция sys.dm_db_database_page_allocations.
pragmatic; +1 Ответить
5. CheBurator 3430 14.07.20 00:45 Сейчас в теме
ээээ..?
Двоичное дерево поиска - это двоичное дерево, для которого выполняются следующие дополнительные условия:

Оба поддерева — левое и правое — являются двоичными деревьями поиска.

.
Это как так? определение себя через самого себя?
Оставьте свое сообщение

См. также

Автоматические и управляемые блокировки применительно к типовым конфигурациям 1С Промо

Математика и алгоритмы Практика программирования v8 v8::blocking 1cv8.cf Бесплатно (free)

Основные принципы работы с режимами автоматических и управляемых блокировок в 1С Предприятие 8. Теория и применение в типовых конфигурациях: БП, УТ, ЕРП

10.11.2018    35323    ids79    40    

1С: Документооборот, Data Science и Python

Документооборот и делопроизводство Математика и алгоритмы ДО Бесплатно (free)

В статье рассказывается о создании и обучении модели Data Science на языке Python и интеграции с системой 1С: Документооборот

04.08.2020    1695    Vaganov_Alexey    4    

Применение математических достижений в решении сложных задач бизнеса

Математика и алгоритмы Бесплатно (free)

Как правило, самые сложные задачи решаются с точки зрения математики очень легко. Но чтобы найти правильное решение, важно понять бизнес-цель, которую достигает эта задача. О практическом применении математических достижений для эффективного решения сложных задач бизнеса на конференции Infostart Event 2019 Inception рассказал Дмитрий Мишнов.

25.05.2020    3460    Mishnov    17    

Улучшение пооперационного планирования в 1С:ERP 2.4 внешними средствами

Математика и алгоритмы Производительность и оптимизация (HighLoad) Бесплатно (free)

Задача построения оптимального производственного расписания требует сравнения тысяч и десятков тысяч вариантов. Выполнять такие вычисления средствами платформы 1С Предприятие нецелесообразно. Как реализовать пооперационное планирование с использованием генетических алгоритмов и параллельных вычислений в докладе на конференции Infostart Event 2019 Inception рассказал генеральный директор компании «ИНТЕХ» Сергей Сафаров.

02.03.2020    5422    ildarovich    7    

Как работает серверный вызов в 1С Промо

Математика и алгоритмы v8::УФ Бесплатно (free)

Клиент-серверная архитектура заложена в платформе изначально — со времен «1С:Предприятие 8.0». Однако при разработке на 8.0 и 8.1 о разделении кода на клиентскую и серверную часть можно было не заботиться, поскольку на клиенте (на толстом клиенте) был доступен тот же функционал, что и на сервере. Всё изменилось с выходом платформы «1С:Предприятие 8.2», когда появился тонкий клиент. Теперь на клиенте доступен один функционал, на сервере — другой. Клиент и сервер «общаются» между собой с помощью серверного вызова. Конечно, это усложнило процесс разработки, но с другой стороны – можно создавать более оптимальные (быстрые) решения, поскольку все сложные задачи выполняются на сервере.

18.11.2017    56688    pahich    82    

Treemapping — способ визуализации данных древовидной структуры. Карта-схема дерева

Математика и алгоритмы Работа с интерфейсом v8 1cv8.cf Бесплатно (free)

Предлагается ознакомиться с редким способом графического представления иерархических данных. Приводится алгоритм формирования и пример реализации.

18.02.2020    4936    randomus    20    

Регистры бухгалтерии. Общая информация

Практика программирования Математика и алгоритмы v8 v8::БУ БУ Бесплатно (free)

Общая информация о внутреннем устройстве регистров бухгалтерии.

05.09.2019    29388    YPermitin    24    

"Хочу универсально!" [Часть 1]

Математика и алгоритмы Практика программирования Разработка v8 1cv8.cf Бесплатно (free)

Сентябрьская серия статей про то, как начинающий разработчик Вася проходит путь от простой задачки к созданию своего механизма. На этот раз - открытие значения из текущей колонки.

02.09.2019    9900    SeiOkami    35    

Будни автоматизации или "мне нужна программка для 3D упаковки" Промо

Практика программирования Математика и алгоритмы Оптовая торговля Оптовая торговля v8 1cv8.cf УУ Бесплатно (free)

Автоматизация отечественных предприятий, которой приходиться заниматься, это нужная и высокооплачиваемая, но довольно нервная работа. Выручает юмор. Например, при общении с требовательным клиентом можно вспомнить анекдот: "Держась руками за стену, на ногах еле стоит мужик. К нему пристает ребенок: "Ну, папа, пожалуйста, сделай мне кораблик!", папа отвечает: "Ага! - Сейчас все брошу и пойду делать тебе кораблик!". Про один такой сделанный для клиента "кораблик" и хочется рассказать. Надеюсь, совместное погружение в теплое ламповое (то есть клиентоориентированное) программирование доставит Вам положительные эмоции, да и задача попалась интересная. Поплыли?

24.03.2014    45408    ildarovich    116    

Иерархия без "В ИЕРАРХИИ"

Математика и алгоритмы v8 Бесплатно (free)

Говорится о том, как эффективно представлять иерархию в СУБД, как получать и использовать эти представления при решении задач в запросной технике. Уточняются и дополняются запросы из статьи "Уровни, глубина, прародители, циклы и аналоги запросом" [https://infostart.ru/public/160707/].

22.08.2019    12558    ildarovich    19    

EnterpriseData – часть 3. Загрузка данных, идентификация объектов

Практика программирования Математика и алгоритмы Перенос данных из 1C8 в 1C8 Разработка v8 v8::УФ 1cv8.cf Бесплатно (free)

Основные этапы загрузки данных через EnterpriseData. Идентификация объектов загружаемых полностью и по ссылке. Приведены схемы процессов загрузки данных. Описание основных операций и обработчиков. Перечень процедур БСП, используемых при загрузке данных, структура «КомпонентыОбмена».

22.08.2019    15225    ids79    8    

Обработчики событий при записи объектов. Зачем и что за чем?

Математика и алгоритмы v8 Бесплатно (free)

Программисту, имеющему немного опыта на платформе 1С 8.3, бывает сложно разобраться: ПередЗаписью, ПриЗаписи, ПослеЗаписи, на сервере, на клиенте, в модуле формы, в модуле объекта.... Эта шпаргалка была создана в процессе обучения и реального опыта с целью разложить всё по полочкам, чтобы было четкое понимание в каком случае какой обработчик нужно использовать и в какой последовательности они запускаются при записи и проведении документов. Данная статья будет полезна в большей степени начинающим разработчикам. Но и опытным позволит освежить информацию, упорядочить её.

25.07.2019    54336    AlbinaAAA    28    

Метод Кларка-Райта. Оптимальное планирование маршрутов грузоперевозок Промо

Математика и алгоритмы Бесплатно (free)

Одной из наиболее важных задач каждого предприятия, осуществляющего доставку грузов в крупных населенных пунктах, является сокращение издержек. Возможное решение данной проблемы заключается в сокращении пробега автотранспорта и, как следствие, уменьшении расхода ГСМ. Появляются такие вопросы ... - СКОЛЬКО НУЖНО МАШИН ДЛЯ РАЗВОЗКИ КОНКРЕТНОГО ОБЪЕМА ГРУЗА ПО АДРЕСАМ ДОСТАВКИ ? - КАК РАЗБИТЬ ТОЧКИ ДОСТАВКИ НА ОПТИМАЛЬНЫЕ ПО ПРОБЕГУ И ЗАГРУЗКЕ МАШИН МАРШРУТЫ ? ... В этой статье Вы найдете один из многих способов получить ответ на эти вопросы.

10.02.2016    60275    mi1man    20    

Как проводятся документы в типовых конфигурациях от 1С

Математика и алгоритмы Практика программирования Разработка v8::ОУ ERP2 УТ11 Россия УУ Бесплатно (free)

В свое время, когда только начинал шаги в 1С и изучал, как проводятся документы в конфигурациях на платформе 1С по книге "Разработка управляемого интерфейса" (Хрусталева Е.Ю.), и там были представлены примеры совсем далекие от того, как сейчас проводятся документы в современных конфигурациях от 1С.

24.07.2019    27958    skv_79    35    

Управление качеством кода

Математика и алгоритмы Рефакторинг и качество кода v8 Бесплатно (free)

О SonarQube, АПК, EDT. Какие преимущества дает их использование. Для каких команд подходит.

22.07.2019    16679    Stepa86    33    

Что делает "В ИЕРАРХИИ" в запросе?

Математика и алгоритмы v8 Бесплатно (free)

Описание действий платформы 1С при использовании конструкции "В ИЕРАРХИИ" в запросах.

16.07.2019    27689    YPermitin    34    

Приемы обработки больших данных в 1С Промо

Универсальные обработки Математика и алгоритмы Перенос данных из 1C8 в 1C8 v8 1cv8.cf Бесплатно (free)

Рассказ об эффективных приемах организации обработок больших объемов данных на платформе 1С

07.08.2015    67475    tormozit    27    

Создание отчетов с помощью СКД - основные понятия и элементы

Практика программирования Математика и алгоритмы v8 v8::СКД Бесплатно (free)

Основные принципы работы СКД. Понятия схемы компоновки и макета компоновки. Описание основных элементов схемы компоновки: наборы данных, поля, вычисляемые поля, ресурсы, параметры.

25.06.2019    54099    ids79    25    

Реализуем Стек, Очередь и Приоритетную очередь в 1С

Практика программирования Математика и алгоритмы v8 1cv8.cf Россия Бесплатно (free)

В статье рассматриваются способы реализации таких абстрактных структур данных, как стек, очередь и приоритетная очередь, используя готовые типы данных 1С. Выявляются "узкие" места, сложные моменты в реализации и сравнивается скорость работы.

24.06.2019    14293    RonX01    65    

Почему вообще работает мой запрос? или Ещё раз о планах запросов

Математика и алгоритмы Практика программирования Разработка v8::Запросы Бесплатно (free)

Другие статьи на эту тему объясняют, что такое план выполнения запроса, но не рассказывают о том, как его получить. Эта заметка призвана заполнить этот пробел. Её цель - популяризировать общедоступные инструменты получения плана запроса среди разработчиков, которые ещё не начали их использовать.

10.06.2019    9448    DataReducer    12    

XDTO - это просто Промо

Математика и алгоритмы v8 1cv8.cf Бесплатно (free)

С появлением платформы 8.1 фирма “1С” представила механизм, носящий интригующее название XML Data Transfer Objects или, если коротко - XDTO. По традиции, документирование механизма составлял тот, кто хорошо разбирался в вопросе, а стало быть опустил “и так понятные” с его точки зрения моменты. Целью данной статьи (или цикла статей, как получится) стало желание поделиться накопленным опытом. Мне кажется, многие неочевидные вещи в механизме XDTO необходимо осветить получше.

24.12.2012    296783    Evil Beaver    173    

Вычисление 200 тысяч знаков числа pi

Математика и алгоритмы v8 Россия Бесплатно (free)

В статье рассматриваются возможности платформы выполнять сверхточные вычисления без использования сложных алгоритмов и внешних компонент на примере вычисления числа pi.

28.05.2019    8006    Oleg_nsk    96    

Регистры накопления. Виртуальные таблицы. Часть №1: Обороты

Практика программирования Математика и алгоритмы Разработка v8 1cv8.cf Бесплатно (free)

Описание работы платформы 1С:Предприятие 8.2 с виртуальной таблицей "Обороты" регистров накопления.

20.05.2019    28705    YPermitin    7    

Выдержки из книги Чистый код

Математика и алгоритмы Бесплатно (free)

Недавно я прочитал книгу "Чистый код" Роберта Мартина (Robert Cecil Martin). В ней описываются принципы организации и форматирование исходного кода программы так, чтобы в дальнейшем было легко поддерживать такой код. Эта книга является библией для многих программистов, но вот в среде программистов 1С, к сожалению, не очень распространено чтение подобной фундаментальной литературы. Книга более 400 страниц и так много порой лениво читать, да и времени всегда не хватает. По этому я решил выделить в виде цитирования по разделам самые важные моменты. А также снабдил текст своими примерами кода.

16.05.2019    10817    FreeArcher    105    

Самоучитель языка запросов 1С. Промо

Практика программирования Решение задач на 1С:Специалист Математика и алгоритмы v8 v8::Запросы Бесплатно (free)

Сервис для изучения запросов 1С: "Консоль изучения запросов 1С:Предприятие 8". Теперь и с конструктором запросов!

07.05.2013    110432    bpc222    327    

Что такое алгоритм?

Математика и алгоритмы Бесплатно (free)

Как ответить на этот вопрос и не попасть пальцем в небо.

25.02.2019    8924    mkalimulin    274    

Криптовалюты, а также иные взгляды на природу денег в терминах 1С

Математика и алгоритмы Бесплатно (free)

Это отчасти полемическая статья. Я задумал написать ее как ответ на другую хорошую статью о криптовалютах. Хотелось поспорить с некоторыми утверждениями автора, а ещё больше с некоторыми комментариями. А чтобы текст был более понятным для местной аудитории, я решил использовать, где только возможно, терминологию и практику 1С.

28.01.2019    6248    mkalimulin    89    

Как писать код? Технологии древних цивилизаций, или все новое - это хорошо забытое старое

Математика и алгоритмы Бесплатно (free)

Все современные технологии - это развитие и доведение до ума (или маразма) древних идей. За последнее время не придумали ничего нового - все, что мы видим, было придумано тысячи лет назад. Не является исключением и программирование, которое в сути своей является переводом с языка условностей технического задания или заявки пользователя в формализованный и абсолютно точный язык математической логики. А логику придумали (по крайней мере первыми опубликовались в ведущих научных журналах) еще древние греки.

23.01.2019    11701    starik-2005    43    

Предметно-ориентированное проектирование (3D) в 1С. Виртуальная машина. Промо

Математика и алгоритмы Бесплатно (free)

Проектирование программного обеспечения - это постоянная битва за простоту.

03.06.2014    40349    Evgen.Ponomarenko    88    

Роберт Мартин: "Будущее программирования" / Robert Martin: "The Future of Programming"

Математика и алгоритмы Блоги Бесплатно (free)

Перевод-транскрибация выступления.

14.01.2019    15769    Vladimir Litvinenko    38    

Многоязычное программирование: создание систем с использованием нескольких языков

Математика и алгоритмы Россия Бесплатно (free)

В мире существует несколько тысяч языков программирования. Несмотря на то, что многие из них крайне непопулярны, очень специфичны или уже созданы очень давно, они продолжают существовать, а новые языки продолжают появляться. Похоже, нет оснований полагать, что количество языков когда-нибудь начнет уменьшаться и в конечном счете будет создан один универсальный язык программирования. Большое количество языков может пугать своей необъятностью, но новое понимание идеи многоязычных проектов позволяет не только ориентироваться в этом разнообразии, но и видеть очевидную выгоду для всех.

09.01.2019    12294    kalyaka    36    

Решение транспортной задачи запросом Промо

Математика и алгоритмы v8 Бесплатно (free)

Списание по двум последовательностям партий запросом (без программной обработки)

1 стартмани

30.04.2014    35138    bforce    22    

Размышления о хороших практиках, навеянные одной статьей

Математика и алгоритмы Бесплатно (free)

Прочитал статью "Ректальное программирование: основы для практикующих 1С-программистов". Статья очень хорошая и своевременная. Но у меня возникло некоторое сомнение. А достаточно ли автор любит и понимает предмет, о котором пишет? Насколько богат его опыт ректального программирования и занимался ли он им вообще? Как человек обладающий многолетним опытом РП, я решил представить вам необходимые дополнения к статье.

21.12.2018    6831    mkalimulin    61    

Ректальное программирование: основы для практикующих 1С-программистов

Математика и алгоритмы Бесплатно (free)

Одной из самых популярных и зарекомендовавших себя методологий программирования в 1С является так называемое ректальное программирование. Редкий проект внедрения и сопровождения учётных систем на платформе 1С обходится без его использования. Зачастую без знания данной методологии программистам даже бывает сложно найти работу в сфере 1С, потому что работодатели, особенно фирмы-франчайзи, в основном отдают предпочтение классическим, зарекомендовавшим себя методикам, а не новомодным заграничным веяниям.

19.12.2018    43634    for_sale    351    

Многопоточное восстановление последовательностей

Производительность и оптимизация (HighLoad) Практика программирования Математика и алгоритмы Универсальные функции v8 Бесплатно (free)

Универсальный алгоритм многопоточного фонового восстановления любой последовательности.

05.12.2018    13401    _ASZ_    33    

Парсер запросов 1С. Часть 1: Введение, разбор математических выражений Промо

Математика и алгоритмы v8 Бесплатно (free)

Рано или поздно становится скучно решать типичные задачи, для которых придумана 1С. Голова пухнет от бухгалтерских терминов и очередных "хотелок" пользователей. Именно в такие моменты хочется гордо поднять голову, воскликнуть "Но я же программист!" и заняться чем-то интересным. В цикле статей я постараюсь доступно описать, как устроены парсеры в целом и на примере парсера языка запросов 1С. Требования к навыкам читающего: основы языка 1С, основы алгоритмизации.

1 стартмани

04.12.2013    30763    juntatalor    49    

Основные понятия и механизмы оптимизации клиент-серверного взаимодействия в 1C

Математика и алгоритмы Практика программирования v8 Россия Бесплатно (free)

У многих начинающих 1С программистов часто возникают вопросы про клиент-серверное взаимодействие в 1С и чтобы разобраться в непростых механизмах платформы, необходимо понять, что же такое контекст, для чего предназначены директивы компиляции, что представляют собой контекстные/внеконтекстные вызовы и как наиболее оптимально описывать прикладные задачи в модулях управляемых форм.

23.08.2018    39140    Rain88    46    

Учебный курс. Повышение качества разработки. Ошибки программы

Практика программирования Математика и алгоритмы Рефакторинг и качество кода Бесплатно (free)

Учебный курс по теории и практике программирования. Бесплатно. В виде структурированного текста. Лекции № 3,4,5. Эти лекции посвящены ошибкам программ, их классификации и способам исправления

10.07.2018    19735    Артано    92    

Що там у них в Java

Математика и алгоритмы Бесплатно (free)

Развенчание мифа о тяжёлой жизни не 1С программистов на примере создания веб сервиса редактирования таблички с использованием framework spring в Java.

24.05.2018    11254    van_za    62    

Сервис для изучения методов платформы 1С:Предприятие 8. Бесплатно! Промо

Практика программирования Решение задач на 1С:Специалист Математика и алгоритмы v8 Бесплатно (free)

Бесплатный ON-Line сервис изучения методов платформы 1С:Предприятие 8. Подготовка к аттестации 1С:Специалист on-line! Тестовые задания по различным видам учета! Подсказки для оптимального решения!

27.06.2013    50158    bpc222    52    

Учебный курс. Повышение качества разработки. Вводная лекция, часть 2

Практика программирования Математика и алгоритмы Бесплатно (free)

Учебный курс по теории и практике программирования. Бесплатно. В виде структурированного текста. Лекция №2. Эта лекция посвящена абстракциям, их свойствами и практическому применению в рамках классических парадигм программирования.

24.05.2018    13003    Артано    36    

Учебный курс. Повышение качества разработки. Вводная лекция

Математика и алгоритмы Бесплатно (free)

Учебный курс по теории и практике программирования. Бесплатно. В виде структурированного текста.

10.05.2018    17947    Артано    51    

"Взлом" теста "1С:Профессионал" методом машинного обучения

Практика программирования Математика и алгоритмы v8 1cv8.cf Бесплатно (free)

Нейронные сети – не единственная модель, реализующая принципы машинного обучения. Есть еще байесовская модель, которая математически строже и определеннее, поскольку построена на надежном фундаменте теории вероятностей. Применению байесовского вывода к решению интересной теоретической задачи и посвящена данная статья. Слово "взлом" в заголовке использовано для привлечения внимания. Речь идет исключительно о математическом методе, показанном на примере знакомой всем задачи. 

12.03.2018    19301    ildarovich    19    

Внутреннее качество разработки конфигураций 1С Промо

Практика программирования Математика и алгоритмы Бесплатно (free)

Пиши с верой в то, что твой читатель - это маньяк с дробовиком, знающий твой домашний адрес. Размышления на тему внутреннего качества кода при разработке/доработках конфигураций 1С.

21.06.2013    37894    ig1082    50    

Правила программирования и автоматизации

Математика и алгоритмы Бесплатно (free)

Изложил свой опыт программирования, больше десяти лет.

21.02.2018    18481    Dzenn    127    

Творим Историю вместе

Математика и алгоритмы Бесплатно (free)

Расширяем границы, выходим за рамки, ставим новые цели - все, как вы любите.

17.01.2018    17510    1c-intelligence    108    

Использование git при разработке на 1С

Математика и алгоритмы Россия Бесплатно (free)

Продолжение цикла статей по основам CI. Данная статья расскажет о реализации возможности хранения кода продукта в системе управления версиями git и познакомит со специализированным инструментарием, предназначенным для решения этой и других смежных задач.

27.12.2017    32684    real_MaxA    57    

v8: Концепция минимального изменения конфигурации для легкого обновления Промо

Математика и алгоритмы v8 1cv8.cf Бесплатно (free)

"Лучше день потерять потом за пять минут долететь" ((с) "Крылья, ноги и хвосты") или как сделать так чтобы обновление конфигурации проходило с минимальными трудозатратами.

28.01.2013    38168    MarSeN    57    

Об уровне абстракции и сложности системы

Математика и алгоритмы Бесплатно (free)

В среде 1С почти не приходится слышать таких терминов, как уровень абстракции, декомпозиция и управление сложностью. Тем не менее, эти термины следует понимать, а подходы применять на практике, поскольку правильно выбранный уровень абстракции ведет к упрощению и увеличению устойчивости программного кода на порядки.

21.12.2017    12366    m-rv    15    

Введение в CI для 1С

Математика и алгоритмы v8 Россия Бесплатно (free)

Значение роли тестирования при разработке ПО трудно переоценить, его применение позволяет повысить надёжность продукта и улучшить качество кода. Для продуктов для платформы 1С:Предприятие существует ряд инструментов для проведения тестирования, в том числе и от самого вендора. Но, также появились открытые инструменты, реализующие мировые практики проведения тестирования (проверки продукта), поддерживаемые сообществом. В этой статье описаны базовые принципы, которые необходимо понимать перед началом применения этих инструментов.

21.11.2017    23828    real_MaxA    22