2003-02-16 16:44:26 UTC
При работе с деревьями (с древовидной структурой сайта) у меня встал вопрос о том, как управлять положением узлов дерева относительно других узлов. Т.е. как по желанию произвольно менять его, не применяя при этом специальных мер по записи элементов исходной таблицы (из которой формируется дерево) в требуемом порядке – если эта таблица формируется человеком вручную, или соглашений по значениям некоторых полей (ключей), с помощью которых можно сделать требуемую сортировку.
Примером такого соглашения может являться, например то, что одноуровневые элементы дерева (братья) должны выводиться в порядке возрастания/убывания их числовых идентификаторов. Например, в примере формирования списка всех URI сайта, если принять за правило выводить одноуровневые элементы в порядке возрастания их числовых идентификаторов, — раздел hardware будет идти перед разделом software, или компьютеры будут идти перед принтерами. В этом случае, если необходимо изменить порядок следования, необходимо изменить числовые идентификаторы соответствующих разделов.
При большом количестве элементов это может оказаться неудобным, да и при маленьком количестве не очень хочется утруждать себя «правильной» схемой нумерации. Одним из способов решения этой проблемы, может являться сохранение дополнительной информации об элементе, предшествующем данному, или следующим за ним.
Приведенный здесь пример кода, является весьма упрощенным примером топологической сортировки, работающем для узкого класса задач. «Топологическая сортировка – это установление частичного порядка среди объектов, упорядоченных в линейном порядке, т.е. в таком расположении объектов линейной последовательности а1 а2 … аn, чтобы для любых aj предшествующих ak выполнялось условие j < k.» Д. Кнут
Хотя проблема возникла при выводе древовидной структуры, а такая сортировка как показано выше осуществляется для линейной последовательности, однако если дерево формируется из таблицы, то данный алгоритм, можно применить и к этой задаче. Подробнее о формировании древовидных структур из линейных, смотрите пример про формирование деревьев средствами парсера из соответствующего раздела.
Теперь об упрощениях и соглашениях принятых при решении задачи:
В качестве примера таблицы подвергаемой сортировке, рассмотрим исходную таблицу, применяемую для формирования URI сайта, из примера про построение списка всех URI сайта:
id | parent_id | dir | title |
---|---|---|---|
1 | 0 | hardware | Железо |
11 | 1 | computers | Компьютеры |
12 | 1 | printers | Принтеры |
121 | 12 | laser | Лазерные |
122 | 12 | ink | Струйные |
2 | 0 | software | Программное обеспечение |
21 | 2 | os | Операционные системы |
22 | 2 | editors | Текстовые редакторы |
3 | 0 | news | Новости |
Дополним её столбцом prev_id
содержащем id
строки, предшествующей данной (если ничего не предшествует, то это значение равно нулю) и перемешаем строки, показывая что нам не важен порядок следования строк в исходной таблице. Таблица примет такой вид:
id | parent_id | prev_id | dir | title |
---|---|---|---|---|
1 | 0 | 0 | hardware | Железо |
2 | 0 | 122 | software | Программное обеспечение |
3 | 0 | 22 | news | Новости |
11 | 1 | 1 | computers | Компьютеры |
12 | 1 | 11 | printers | Принтеры |
21 | 2 | 2 | os | Операционные системы |
22 | 2 | 21 | editors | Текстовые редакторы |
121 | 12 | 12 | laser | Лазерные |
122 | 12 | 121 | ink | Струйные |
Сам код метода сортировки имеет вид:
####### # Топологическая сортировка таблицы # методу передается исходная таблица - table, имя ключевого столбца - key # и имя столбца с ключами предшествующих элементов - prev_key @sort_table[table;key;prev_key][table_hash;table_columns] # создание хэша из таблицы для ускорения поиска $table_hash[^table.hash[$prev_key]] # таблица названий столбцов $table_columns[^table.columns[]] # названия столбцов результирующей таблицы $result[^table::create{^table_columns.menu{$table_columns.column}[ ]}] # добавление первого элемента ^result.append{^table_columns.menu{$table_hash.0.[$table_columns.column]}[ ]} $prev_key($table_hash.0.[$key]) ^while($prev_key && $table_hash.[$prev_key].[$key]){ ^result.append{^table_columns.menu{$table_hash.[$prev_key].[$table_columns.column]}[ ]} $prev_key($table_hash.[$prev_key].[$key]) }
Ещё немного комментариев, к тем, что уже есть в коде.
prev_id
должны быть уникальны, и хотя бы одно из них должно быть равно нулю (первый элемент). Если это не так, метод работать не будет.$items
, — вызов этого метода, возвращающий ту же самую таблицу, отсортированную по информации из поля prev_id
, будет выглядеть так:
$items[^sort_table[$items;id;prev_id]]
Отсортированная таблица будет выглядеть следующим образом:
id | parent_id | prev_id | dir | title |
---|---|---|---|---|
1 | 0 | 0 | hardware | Железо |
11 | 1 | 1 | computers | Компьютеры |
12 | 1 | 11 | printers | Принтеры |
121 | 12 | 12 | laser | Лазерные |
122 | 12 | 121 | ink | Струйные |
2 | 0 | 122 | software | Программное обеспечение |
21 | 2 | 2 | os | Операционные системы |
22 | 2 | 21 | editors | Текстовые редакторы |
3 | 0 | 22 | news | Новости |
Как выяснилось позднее, — в коде есть ошибка, которая проявляется в том, что если в исходной таблице есть NULL(пустые) значения, сортированная таблица получается не совсем такой как хотелось бы. Короче говоря в строке где есть NULL значения столбцов меньше чем в той, в которой их нет. В связи с этим родился ещё один вариант решения задачи:
####### # Топологическая сортировка таблицы # методу передается исходная таблица - table, имя ключевого столбца - key # и имя столбца с ключами предшествующих элементов - prev @sort_table[table;key;prev][table_columns;insert_current_row] # таблица названий столбцов $table_columns[^table.columns[]] # названия столбцов результирующей таблицы $result[^table::create{^table_columns.menu{$table_columns.column}[ ]}] # код вставки текущей строки $insert_current_row{ ^result.join[$table][$.limit(1) $.offset[cur]] } # добавление первого элемента # т.е. у которого prev = 0 ^table.locate[$prev;0] $insert_current_row $prev_key($table.$key) ^while($prev_key && ^table.locate[$prev;$prev_key]){ $insert_current_row $prev_key($table.$key) }
Однако этот способ далеко не оптимален, потому что метод locate
работает с помощью последовательного перебора, и при больших таблицах это будет сильно торомозить, однако, поскольку производится копирование строк, а не значений, NULL значения допускаются.
И наконец, последний вариант кода — без поиска последовательным перебором (locate
), а с двоичным поиском нужной строки таблицы:
####### # Топологическая сортировка таблицы # методу передается исходная таблица - table, имя ключевого столбца - key # и имя столбца с ключами предшествующих элементов - prev @sort_table[table;key;prev][table_columns;insert_current_row;i;l;u;break;binary_search;prev_key] # таблица названий столбцов $table_columns[^table.columns[]] # названия столбцов результирующей таблицы $result[^table::create{^table_columns.menu{$table_columns.column}[ ]}] # код вставки текущей строки $insert_current_row{ ^result.join[$table][$.limit(1) $.offset[cur]] } # добавление первого элемента # т.е. у которого prev = 0 # или иными словами - задание начальных значений ^table.sort($table.$prev) $insert_current_row $prev_key($table.$key) # Бинарный поиск $binary_search{ # начальные условия $l(1) $u(^table.count[]) $break(1) ^while($u >= $l && $break){ $i(^math:floor(($l + $u)/2)) ^table.offset[set]($i) ^if($prev_key < $table.$prev){ $u($i - 1) }{ ^if($prev_key == $table.$prev){ $break(0) }{ $l($i + 1) } } } } ^for[k](1;^table.count[] - 1){ $binary_search $insert_current_row $prev_key($table.$key) }
Немного комментариев:
sort
), ускорение работы будет значительное, ибо сортировка производится только один раз, в отличие от locate
в предыдущем варианте кода, который выполнялся для каждой строки таблицы.В принципе всё. Если я найду более оптимальный вариант кода для данной задачи, я в очередной раз изменю эту статью.