сортировать

Чтобы узнать о местонахождении Плоского мира, см. Плоский мир (мир) § Tsort .

сортировать

Первоначальный выпуск	1979 год ( 1979 )
Операционная система	Unix , Unix-подобные , V , Inferno
Платформа	Кросс-платформенный
Тип	Команда

Программа tsort — это утилита командной строки на Unix и Unix-подобных платформах, которая выполняет топологическую сортировку входных данных. По состоянию на 2017 год , это часть стандарта POSIX .1.

История

По его информации Эта команда изначально была написана для обеспечения упорядочивания объектных файлов, что позволяло компоновщику обрабатывать их последовательно (каждый ровно один раз и по порядку). Страница руководства FreeBSD датируется своим появлением в версии 7 Unix .

Обратите внимание, что следующее описание описывает поведение реализации tsort во FreeBSD и упоминает функции GNU, где они могут существовать. Другие реализации или версии могут отличаться.

Синтаксис

tsort [-dlq] [FILE]

Опции FreeBSD могут быть:

-d         turn on debugging
-l         search for and display the longest cycle.
-q         Do not display informational messages about cycles.

GNU предоставляет только следующие опции:

--help     display help message and exit
--version  display version information and exit

POSIX не предписывает никаких опций.

Поведение

tsort считывает свои входные данные (из заданного ФАЙЛА или стандартного ввода , если входной файл не указан или для ФАЙЛА со значением «-») как пары строк, разделенных пробелами, что указывает на частичный порядок. Результатом является общий порядок, соответствующий заданному частичному порядку.

Другими словами: для ориентированного ациклического графа (используемого в качестве графа зависимостей ) tsort выдает список вершин так, чтобы для всех ребер «a->b» «a» стояло в листинге перед «b».

Примеры

tsort перечисляет вершины ориентированного ациклического графа в таком порядке, что соблюдаются все отношения порядка/направления:

$ tsort <<EOF > 3 8 > 3 10 > 5 11 > 7 8 > 7 11 > 8 9 > 11 2 > 11 9 > 11 10 > EOF 3 5 7 11 8 10 2 9

образец ДЕНЬ

График звонков

tsort может помочь переупорядочить функции в исходном файле, чтобы как можно больше их было определено до их использования (интерпретируйте следующее как: main() звонки parse_options(), tail_file() и tail_forever(); tail_file() звонки pretty_name(), и так далее. В результате dump_remainder() должны быть определены в первую очередь, start_lines() второй и т. д.):

$ cat call-graph main parse_options main tail_file main tail_forever tail_file pretty_name tail_file write_header tail_file tail tail_forever recheck tail_forever pretty_name tail_forever write_header tail_forever dump_remainder tail tail_lines tail tail_bytes tail_lines start_lines tail_lines dump_remainder tail_lines file_lines tail_lines pipe_lines tail_bytes xlseek tail_bytes start_bytes tail_bytes dump_remainder tail_bytes pipe_bytes file_lines dump_remainder recheck pretty_name

$ # note: 'tac' reverses the order $ tsort call-graph | tac dump_remainder start_lines file_lines pipe_lines xlseek start_bytes pipe_bytes tail_lines tail_bytes pretty_name write_header tail recheck parse_options tail_file tail_forever main

Библиотека

Традиционный ld (компоновщик Unix) требует, чтобы входные данные библиотеки были отсортированы в топологическом порядке, поскольку он обрабатывает файлы за один проход. Это относится как к статическим библиотекам ( *.a) и динамические библиотеки ( *.so), а в случае статических библиотек — предпочтительно для отдельных объектных файлов, содержащихся в них.

BSD UNIX использует tsort как обычную часть типичных вызовов команд ar и ranlib (из /usr/share/mk/bsd.lib.mk):

lib${LIB}.a: ${OBJS} ${STATICOBJS}
    @${ECHO} building static ${LIB} library
    @${AR} cq ${.TARGET} `lorder ${OBJS} ${STATICOBJS} | tsort -q` ${ARADD}
    ${RANLIB} ${.TARGET}

Здесь lorder («библиотечный порядок») используется для создания списка межфайловых зависимостей путем проверки таблицы символов.

Примечания по использованию

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

a b b c

a b b c

a b b c

a b b c

a b b c

Пары одинаковых элементов указывают на наличие вершины, но не на порядок (поэтому следующее представляет собой одну вершину без ребер):

a a

Строго говоря, не существует топологического упорядочения графа, содержащего один или несколько циклов . Однако tsort выводит предупреждение, а GNU tsort выводит обнаруженные циклы в стандартную ошибку (строки, начинающиеся с 'tsort:'):

$ tsort <<EOF
> a b
> b c
> c a
> EOF
UX: tsort: INFORM: cycle in data
tsort: a
tsort: b
tsort: c
a
b
c

См. также

• Сортировка (Unix)
• Сделать (программное обеспечение)
• Топологическая сортировка
• Список команд Unix
• График звонков

Ссылки

Дальнейшее чтение

• Кнут, Дональд Э. (1997). Искусство компьютерного программирования . Том. 1 (3-е изд.). стр. 261–268. ISBN  0-201-89683-4 .
• Кан, AB (1962). «Топологическая сортировка больших сетей» . Коммуникации АКМ . 5 (11): 558–562. дои : 10.1145/368996.369025 . S2CID   16728233 .

Внешние ссылки

Страница руководства по tsort на

• FreeBSD ,
• OpenBSD ,
• НетБСД ,
• ЭКС ,
• Солярис ,
• HP-UX
• dep-trace Упорядочивает основные зависимости и разворачивает вложенные. (базовый: без презумпции 2D-графики)