Имплементация иерархии справочника в pandas с высокой скоростью обхода и доступа

Git (proof-of-concept):https://github.com/elegantwist/hierarchy_pandas

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

Существует два подхода для реализации работы с иерархией в таблицах: 1. Построение n-уровневых индексов средствами самого pandas (в свежих версиях) и 2. Построение текстовой строки, где единой строкой, составленной из указателей на группы, разделенными спецсимволом, указывается полный путь до элемента. Ниже описывается третий подход, который берет немного от первого и второго, и имеет свои как слабые, так и сильные стороны, и в определенных случаях может быть безальтернативным вариантом к применению:

1. Каждому элементу справочника присваивается собственный ID-код, сформированный по заранее согласованному формату. Этот ID представляет собой координаты нахождения элемента в иерархии

2. Формат ID выглядит как целое число вида XXXYYYZZZ. При этом для записей нижнего уровня (элементы) отведены младшие 3 класса — ZZZ (000–999), подгруппы — средние 3 класса — YYY (000000–999000), группы верхнего уровня — старшие 3 класса XXX (000000000–999000000)

Примеры интерпретации:

элемент с ID 10013098 имеет координаты: id элемента 098, id подгруппы — 013, id — 010

элемент с ID 100 имеет координаты: id элемента 100, id подгруппы — 000, id — 000

элемент с ID 9900000 имеет координаты: id элемента 000, id подгруппы — 900, id — 009

3. При этом, такой подход означает, что необходимо заранее знать максимальную глубину дерева и зафиксировать максимальное количество элементов в дереве. Соответственно, максимальная глубина — количество классов, а максимальное количество элементов — количество разрядов группы.

Таким образом, состав и соотношение размеров кодов может варьироваться (можно как XYZ, XXYYZZ, XXXXYYYYZZZZ, … и т.д.), но формат быть един и выбран один раз, при разметки дерева

Таким образом, данный подход применим только в том случае, когда иерархия не перестраивается динамически в режиме online, но есть какое-то время для ее переразметки.

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

Примеры реализации:

1. Чтобы выбрать все элементы группы, по входящему ID группы достаточно выбрать все элементы, с ID от XXXYYY000 по XXXYYY999

Пример (для формата XXYYZZ):

Для группы 20500, ID всех подчиненных элементов будет лежать в диапазоне от 20500–20599

Для группы 130000, ID всех подчиненных элементов будет лежать в диапазоне от 130000–130099

С использованием pandas это выглядит достаточно просто:

all_items = df[df.eval("(index >= 20500) & (index <= 20599)")]

2. Чтобы выбрать все подгруппы нижнего уровня, по ID группы верхнего уровня, достаточно выбрать все элементы, с ID от XXX000000 по XXX9999999, с дополнительным условием, что ID делится без остатка на размер группы т.е. на 1000 (это — однозначный признак группы)

Примеры (для формата XXYYZZ):

Для группы 20000, ID всех подчиненных подгрупп будет лежать в диапазоне от 20000–29900 (размер группы = 100)

Код:

all_subgroups = df[df.eval("(index >= 20000") & (index <= 29900) & ((index % 100) == 0)")]

А если необходимо выбрать все группы верхнего уровня, то это будет диапазон от 000000–990000, при размере группы = 10000:

all_top_groups = df[df.eval("(index >= 0") & (index <= 990000) & ((index % 10000) == 0)")]

3. Выбрать все элементы в иерархии верхнего уровня, для всех подчиненных подгрупп, но без учета самих подгрупп: XXX000000 — XXX999999, вычитая ID которые нацело делятся на размер группы (1000)

Пример (для формата XXYYZZ):

Для группы 20000, ID всех подчиненных элементов всех подгрупп, без самих подгрупп будет лежать в диапазоне от 29999–29999 (размер группы = 100), за вычетом элементов с ID 20000, 20100, 20200, … , 29900

Код:

all_subgroups = df[df.eval("(index >= 20000") & (index <= 29999) & ((index % 100) != 0)")]

Примеры показывают, что достоинства метода в том, что все указанные выборки по иерархии:

– легко реализовать и внедрить

– понятны пользователю

– работают быстро как на уровне SQL, так и на уровне Pandas

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