Оптимальное упорядочение деревьев: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Оптимальное упорядочение деревьев''' (''Optimal ordering for trees'') - Существует прост...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Оптимальное упорядочение деревьев''' (''Optimal ordering for trees'') - | '''Оптимальное упорядочение деревьев''' (''[[Optimal ordering for trees]]'') - | ||
Существует простой алгоритм определения оптимального порядка, в котором | Существует простой [[алгоритм]] определения оптимального порядка, в котором | ||
следует осуществлять вычисления, образующие линейный участок | следует осуществлять вычисления, образующие линейный участок | ||
программы для случая, когда они представлены в виде дерева. Оптимальность здесь | программы для случая, когда они представлены в виде [[дерево|дерева]]. Оптимальность здесь | ||
понимается в том смысле, что порядок задает самую короткую последовательность | понимается в том смысле, что порядок задает самую короткую последовательность | ||
команд машины из всех возможных для данного дерева. | команд машины из всех возможных для данного дерева. | ||
Алгоритм состоит из двух частей. Первая помечает каждую вершину дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для | Алгоритм состоит из двух частей. Первая помечает каждую [[вершина|вершину]] дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для | ||
вычисления поддерева с данным корнем при условии, что не делается запоминаний промежуточных результатов. Вторая часть --- это обход дерева, порядок которого управляется вычисленными метками вершин. Выходной код генерируется во время указанного обхода дерева. Содержательно алгоритм, обрабатывая два операнда бинарной операции, сначала работает над вычислением того из них, который | вычисления [[поддерево|поддерева]] с данным [[корень|корнем]] при условии, что не делается запоминаний промежуточных результатов. Вторая часть --- это [[обход графа|обход дерева]], порядок которого управляется вычисленными [[метка|метками]] вершин. Выходной код генерируется во время указанного обхода дерева. Содержательно алгоритм, обрабатывая два операнда бинарной операции, сначала работает над вычислением того из них, который | ||
требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым. | требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым. | ||
В общем случае, когда луч может содержать общие подвыражения и представляется дэгом, | В общем случае, когда [[луч]] может содержать общие подвыражения и представляется [[дэг|дэгом]], | ||
задача генерации кода существенно усложняется: задачи оптимальной генерации кода по | задача генерации кода существенно усложняется: задачи оптимальной генерации кода по | ||
дэгу для одноадресной машины, а также для машины с неограниченным числом | дэгу для одноадресной машины, а также для машины с неограниченным числом | ||
регистров являются ''<math>\ | регистров являются ''[[NP-Полная задача|<math>\mathcal NP</math>-Полными]]''. | ||
==Литература== | ==Литература== | ||
[Евстигнеев-Касьянов/98] | [Евстигнеев-Касьянов/98] | ||
Версия от 18:53, 9 декабря 2009
Оптимальное упорядочение деревьев (Optimal ordering for trees) - Существует простой алгоритм определения оптимального порядка, в котором следует осуществлять вычисления, образующие линейный участок программы для случая, когда они представлены в виде дерева. Оптимальность здесь понимается в том смысле, что порядок задает самую короткую последовательность команд машины из всех возможных для данного дерева.
Алгоритм состоит из двух частей. Первая помечает каждую вершину дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для вычисления поддерева с данным корнем при условии, что не делается запоминаний промежуточных результатов. Вторая часть --- это обход дерева, порядок которого управляется вычисленными метками вершин. Выходной код генерируется во время указанного обхода дерева. Содержательно алгоритм, обрабатывая два операнда бинарной операции, сначала работает над вычислением того из них, который требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым.
В общем случае, когда луч может содержать общие подвыражения и представляется дэгом, задача генерации кода существенно усложняется: задачи оптимальной генерации кода по дэгу для одноадресной машины, а также для машины с неограниченным числом регистров являются [math]\displaystyle{ \mathcal NP }[/math]-Полными.
Литература
[Евстигнеев-Касьянов/98]