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

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

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

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

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

Сами по себе деревья бесполезны, если мы не можем выполнять с ними определенные операции. К таким операциям обычно относят: поиск элемента, поиск минимального (максимального) элемента, вставка, удаление. В разрезе этих операций мы и рассмотрим каждое из 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-дерево

34

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

Комментарии
Избранное Подписка Сортировка: Древо
1. Vladimir Litvinenko 24.11.17 20:05 Сейчас в теме
Хм, а что стало с сайтом debug1c.ru? Узнал статью, зашел на сайт, а там большая часть материалов пропала, включая эту публикацию.
Это бедствие стихийное, или запланированное? ))
2. Irwin 326 24.11.17 22:09 Сейчас в теме
(1)Сайт в скором времени прекратит свое существование.
3. kuzyara 796 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 - количество ключей или строк.

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

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

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

См. также

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

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

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

02.09.2019    3896    SeiOkami    35       

Кодогенерация и метагенерация в 1С 24

Статья Программист Нет файла Бесплатно (free) Практика программирования Математика и алгоритмы Разработка

В своем докладе на конференции INFOSTART EVENT 2018 EDUCATION Дмитрий Белозеров рассказал о разработке инструмента, позволяющего программно работать с метаданными 1С и писать скрипты для выполнения тех же действий, которые выполняет разработчик в конфигураторе –  с какими сложностями и нюансами пришлось столкнуться, и что получилось в итоге.

26.08.2019    3951    kirovsbis    28       

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

Статья Программист Нет файла v8 Бесплатно (free) Математика и алгоритмы

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

22.08.2019    4275    ildarovich    16       

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

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

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

22.08.2019    3299    ids79    7       

Запрос SQL для нахождения самого большого простого числа меньше заданного 6

Статья Программист Нет файла Windows Бесплатно (free) Математика и алгоритмы

Данный запрос MS SQL демонстрирует некоторые возможности MS SQL Server, о которых часто неизвестно большинству программистов 1С. В тексте постараюсь объяснить интерес данного запроса (или скрипта).

16.08.2019    1194    alex_bitti    18       

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

Статья Программист Нет файла v8 Бесплатно (free) Математика и алгоритмы

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

25.07.2019    10250    4    AlbinaAAA    22       

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

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

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

24.07.2019    14826    skv_79    32       

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

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

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

22.07.2019    6881    Stepa86    23       

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

Статья Программист Нет файла v8 Бесплатно (free) Математика и алгоритмы

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

16.07.2019    6582    YPermitin    29       

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

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

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

25.06.2019    17214    ids79    16       

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

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

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

24.06.2019    7103    RonX01    63       

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

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

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

10.06.2019    5497    DataReducer    12       

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

Статья Программист Нет файла v8 Россия Бесплатно (free) Математика и алгоритмы

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

28.05.2019    3591    Oleg_nsk    93       

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

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

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

20.05.2019    9766    YPermitin    4       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

16.05.2019    5555    FreeArcher    82       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

25.02.2019    2885    mkalimulin    272       

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

Статья no Нет файла Бесплатно (free) Математика и алгоритмы

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

28.01.2019    3572    mkalimulin    89       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

23.01.2019    8576    starik-2005    43       

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

Статья Программист Нет файла Россия Бесплатно (free) Математика и алгоритмы

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

09.01.2019    5562    kalyaka    33       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

21.12.2018    4400    mkalimulin    61       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

19.12.2018    30504    for_sale    340       

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

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

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

10.11.2018    20717    ids79    40       

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

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

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

23.08.2018    21104    Rain88    42       

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

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

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

10.07.2018    15738    Артано    92       

Що там у них в Java 19

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

24.05.2018    9159    van_za    62       

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

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

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

24.05.2018    10651    Артано    36       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

10.05.2018    15529    Артано    51       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

21.02.2018    16209    Dzenn    127       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

17.01.2018    14847    1c-intelligence    108       

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

Статья Программист Нет файла Россия Бесплатно (free) Математика и алгоритмы

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

27.12.2017    25854    real_MaxA    57       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

21.12.2017    9641    m-rv    15       

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

Статья Программист Нет файла v8 Россия Бесплатно (free) Математика и алгоритмы

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

21.11.2017    18791    real_MaxA    22       

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

Статья Программист Нет файла v8::УФ Бесплатно (free) Математика и алгоритмы

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

18.11.2017    42792    pahich    75       

#Область ВНЕШНИЕ_ВЫЗОВЫ или MVC в 1С, библиотечность и упрощение интеграции кода 43

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

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

12.10.2017    14432    for_sale    58       

Некоторые особенности разработки ММО-игр на платформе 1С:Предприятие 25

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Добрый день, уважаемые коллеги! На первый взгляд может показаться, что статья посвящена довольно необычным вещам, но поверьте мне, эти вещи всем нам вполне привычны, просто мы их обычно видим под другим углом зрения. Поговорим о том, что такое MMO. Многие из вас уже знают, что это такое, потому что существует такая игра, как World of Tanks, а те, кто в нее напрямую не играл, безусловно, о ней слышали. Игра World of Tanks является классическим MMO. MMO расшифровывается как Массивная Многопользовательская Online-игра. С технологической точки зрения это – нагрузки, нагрузки и еще раз нагрузки.

08.09.2017    9368    Inkasor    21       

Групповая разработка конфигураций в крупном холдинге 68

Статья Программист Нет файла v8 Бесплатно (free) Математика и алгоритмы

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

15.08.2017    17024    stas_ganiev    15       

Применение нейронных сетей и генетических алгоритмов в прикладных решениях на платформе 1С 170

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

03.07.2017    31834    comol    63       

Автоматизация процесса 1С-разработки 91

Статья Программист Нет файла v8 Бесплатно (free) Математика и алгоритмы

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

07.06.2017    22523    ekaruk    9       

Пишем игру Минер. Обработка событий ActiveX в 1С 29

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

Пример демонстрирует обработку событий генерируемых компонентой ActiveX в 1С.

29.05.2017    12389    user621724_Dimav1979    11       

Как я доступ на kb.1c.ru получал 90

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

kb.1c - база знаний по технологическим вопросам крупных внедрений и не только. В этой базе знаний собираются методики и решения технологических проблем эксплуатации 1с, check-list'ы и инструкции по настройке ПО на серверах. Какие-то из размещенных статей дублируются на ИТС. Когда я искал пути получения доступа к нему я столкнулся с проблемой: мало кто доподлинно знает как получить доступ к нему, не работая у франчайзи 1с. Я опишу путь, который прошёл я, как физическое лицо.

01.05.2017    22039    ikekoval    33       

Маленькая хитрость СКД - выводим строки X раз 26

Статья Программист Нет файла v8::СКД 1cv8.cf Россия Бесплатно (free) Практика программирования Математика и алгоритмы

Здесь я расскажу, как вывести в отчет СКД произвольное количество одинаковых строк.

17.12.2016    15360    alexandersh    16       

"Распределение в запросе" или "избавляемся от перебора" 182

Статья Программист Нет файла v8 1cv8.cf Россия Бесплатно (free) Математика и алгоритмы Универсальные функции

Хороший перебор - это отсутствие перебора. Рассмотрим пример замены полного перебора запросом.

16.12.2016    27763    alexandersh    45       

Некоторые принципы оптимизации запросов 1С (+SQL) 115

Статья Программист Нет файла v8 Бесплатно (free) Математика и алгоритмы

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

17.11.2016    8601    ture    40       

Использование git для доработки типовых конфигураций 1С 229

Статья Программист Нет файла v8 Беларусь Украина Россия Бесплатно (free) Математика и алгоритмы

Рассмотрены способы доработок типовой конфигурации 1C для различных изменений, и на картинках продемонстрирован подход к разработке с использованием git и частично с тестами.

11.10.2016    185945    pumbaE    31       

Оптимизация запросов 1С:Предприятие – от теории к практике 114

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования Математика и алгоритмы

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

07.10.2016    31048    bpc222    20       

1Script – язык для автоматизации рутины в жизни специалиста по 1С 302

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Мы все здесь – автоматизаторы бизнеса. Мы занимаемся этим каждый день и делаем это хорошо. Но практика показывает, что специалисты по 1С очень редко, очень мало автоматизируют сами себя. Есть много мелких задач, которые мы, 1С-ники, привыкли делать руками, хотя большой класс из этих задач можно было бы переложить на работу машины. Именно об этом и хотелось бы сегодня поговорить.

14.09.2016    44021    Evil Beaver    76