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

Примером такого соглашения может являться, например то, что одноуровневые элементы дерева (братья) должны выводиться в порядке возрастания/убывания их числовых идентификаторов. Например, в , если принять за правило выводить одноуровневые элементы в порядке возрастания их числовых идентификаторов, — раздел hardware будет идти перед разделом software, или компьютеры будут идти перед принтерами. В этом случае, если необходимо изменить порядок следования, необходимо изменить числовые идентификаторы соответствующих разделов.

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

Приведенный здесь пример кода, является весьма упрощенным примером топологической сортировки, работающем для узкого класса задач. «Топологическая сортировка – это установление частичного порядка среди объектов, упорядоченных в линейном порядке, т.е. в таком расположении объектов линейной последовательности а1 а2 … аn, чтобы для любых aj предшествующих ak выполнялось условие j < k.» Д. Кнут

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

Теперь об упрощениях и соглашениях принятых при решении задачи:

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

В качестве примера таблицы подвергаемой сортировке, рассмотрим исходную таблицу, применяемую для формирования 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])
}

Ещё немного комментариев, к тем, что уже есть в коде.

  1. Значения столбца prev_id должны быть уникальны, и хотя бы одно из них должно быть равно нулю (первый элемент). Если это не так, метод работать не будет.
  2. Если назвать вышеприведенную исходную таблицу $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 Новости
  3. Код сортировки достаточно прост и тривиален, а вот код для изменения порядка следования элементов, удаления или вставки нового элемента, будет посложнее, однако проще чем это может показаться с первого взгляда, но это уже совсем другая история.
  4. Для больших структур (сотни элементов) возможно, могут появиться проблемы с производительностью, и придется искать другие способы упорядочивания таких структур.
  5. При частых, одновременных изменениях в структуре дерева (если это используется при построении деревьев), т.е. когда элементы дерева могут добавляться, перемещаться или удаляться одновременно несколькими пользователями в одно и то же время, — будут проблемы, потому что каждое такое изменение может требовать до 6-ти запросов, которые должны производиться при установленной блокировке на таблицу.

Как выяснилось позднее, — в коде есть ошибка, которая проявляется в том, что если в исходной таблице есть 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)
}

Немного комментариев:

  1. Перед двоичным поиском исходная таблица должна быть отсортирована по значениям столбца с ключами предшествующих элементов и здесь, даже в случае самого неэффективного алгоритма реализации сортировки таблицы в парсере (sort), ускорение работы будет значительное, ибо сортировка производится только один раз, в отличие от locate в предыдущем варианте кода, который выполнялся для каждой строки таблицы.
  2. Значения столбца с ключами предшествующих элементов обязательно должны быть числами.

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

2003-02-16 16:44:26 UTC parser snippet web