Топологическая сортировка | Блог

2003-02-16 16:44:26 UTC

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

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

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

Приведенный здесь пример кода, является весьма упрощенным примером топологической сортировки, работающем для узкого класса задач. «Топологическая сортировка – это установление частичного порядка среди объектов, упорядоченных в линейном порядке, т.е. в таком расположении объектов линейной последовательности а₁ а₂ … а_n, чтобы для любых a_j предшествующих a_k выполнялось условие 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	Новости

Код сортировки достаточно прост и тривиален, а вот код для изменения порядка следования элементов, удаления или вставки нового элемента, будет посложнее, однако проще чем это может показаться с первого взгляда, но это уже совсем другая история.
Для больших структур (сотни элементов) возможно, могут появиться проблемы с производительностью, и придется искать другие способы упорядочивания таких структур.
При частых, одновременных изменениях в структуре дерева (если это используется при построении деревьев), т.е. когда элементы дерева могут добавляться, перемещаться или удаляться одновременно несколькими пользователями в одно и то же время, — будут проблемы, потому что каждое такое изменение может требовать до 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)
}

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

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

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

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