Достоверные отношения частоты выполнения: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Достоверные отношения частоты выполнения''' (''Reliable relations of execution frequency'') - П...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Достоверные отношения частоты выполнения''' (''Reliable relations of execution frequency'') | '''Достоверные отношения частоты выполнения''' (''[[Reliable relations of execution frequency]]'') — Пусть <math>G</math> — некоторый ''[[уграф]]'' с начальной [[вершина|вершиной]] <math>p_0</math> и конечной <math>q_0</math>, <math>M</math> — множество элементов (вершин и [[дуга|дуг]]) уграфа <math>G</math>, <math>M_1,M_2\subseteq M</math>, <math>{\mathcal N}</math> — | ||
Пусть <math>G</math> | множество [[путь|путей]] по <math>G</math> от <math>p_0</math> до <math>q_0</math>, а <math>\mid P \cap M_1 \mid</math> — количество вхождений элементов из <math>M_1 \subseteq M</math> в некоторый путь <math>P</math> по <math>G</math>. | ||
<math>p_0</math> и конечной <math>q_0</math>, <math>M</math> | |||
и дуг) уграфа <math>G</math>, <math>M_1,M_2\subseteq M</math>, <math>{\ | |||
множество путей по <math>G</math> от <math>p_0</math> до <math>q_0</math>, а <math>\mid P \cap M_1 | |||
\mid</math> | |||
M</math> в некоторый путь <math>P</math> по <math>G</math>. | |||
Говорят, что <math>M_1</math> и <math>M_2</math> ''достоверно выполняются | Говорят, что <math>M_1</math> и <math>M_2</math> ''достоверно выполняются одинаково часто'' в <math>G</math> (обозначается <math>M_1 \doteq M_2</math>), если для любого пути <math>P</math> из <math>{\mathcal N}</math> выполняется <math>\mid M_1 \cap P \mid = \mid M_2 \cap P \mid</math>. <math>M_1</math> ''достоверно выполняется "чаще"'', чем <math>M_2</math> (обозначается <math>M_1 <\!\! \cdot\ M_2</math>), если <math>\mid M_1 \cap P \mid \leq \mid M_2 \cap P \mid</math> для любого пути <math>P \in {\mathcal N}</math> и существует такой путь <math>P \in {\mathcal N}</math>, что <math>\mid M_1 \cap P \mid < \mid M_2 \cap P \mid</math>. | ||
одинаково часто'' в <math>G</math> (обозначается <math>M_1 \doteq M_2</math>), если | |||
для любого пути <math>P</math> из <math>{\ | |||
P \mid = \mid M_2 \cap P \mid</math>. <math>M_1</math> ''достоверно выполняется "чаще"'', чем | |||
<math>M_2</math> (обозначается <math>M_1 <\!\! \cdot\ M_2</math>), если <math>\mid M_1 \cap P | |||
\mid \leq \mid M_2 \cap P \mid</math> для любого пути <math>P \in {\ | |||
N}</math> и существует такой путь <math>P \in {\ | |||
\cap P \mid < \mid M_2 \cap P \mid</math>. | |||
''' | '''Достоверные отношения частоты выполнения''' играют весьма важную роль при решении задачи ''[[оптимизация программ|оптимизации программы]]''. Целесообразность (оптимизационный эффект) ни одного из оптимизирующих преобразований нельзя гарантировать, если не обеспечены определенные '''достоверные отношения частоты выполнения''' между элементами преобразуемого | ||
''оптимизации программы''. Целесообразность | им ''[[фрагмент|фрагмента]]''. | ||
(оптимизационный эффект) ни одного из оптимизирующих | |||
преобразований нельзя гарантировать, если не обеспечены | |||
определенные ''' | |||
им ''фрагмента''. | |||
==Литература== | ==Литература== | ||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
Текущая версия от 16:31, 7 февраля 2011
Достоверные отношения частоты выполнения (Reliable relations of execution frequency) — Пусть [math]\displaystyle{ G }[/math] — некоторый уграф с начальной вершиной [math]\displaystyle{ p_0 }[/math] и конечной [math]\displaystyle{ q_0 }[/math], [math]\displaystyle{ M }[/math] — множество элементов (вершин и дуг) уграфа [math]\displaystyle{ G }[/math], [math]\displaystyle{ M_1,M_2\subseteq M }[/math], [math]\displaystyle{ {\mathcal N} }[/math] — множество путей по [math]\displaystyle{ G }[/math] от [math]\displaystyle{ p_0 }[/math] до [math]\displaystyle{ q_0 }[/math], а [math]\displaystyle{ \mid P \cap M_1 \mid }[/math] — количество вхождений элементов из [math]\displaystyle{ M_1 \subseteq M }[/math] в некоторый путь [math]\displaystyle{ P }[/math] по [math]\displaystyle{ G }[/math].
Говорят, что [math]\displaystyle{ M_1 }[/math] и [math]\displaystyle{ M_2 }[/math] достоверно выполняются одинаково часто в [math]\displaystyle{ G }[/math] (обозначается [math]\displaystyle{ M_1 \doteq M_2 }[/math]), если для любого пути [math]\displaystyle{ P }[/math] из [math]\displaystyle{ {\mathcal N} }[/math] выполняется [math]\displaystyle{ \mid M_1 \cap P \mid = \mid M_2 \cap P \mid }[/math]. [math]\displaystyle{ M_1 }[/math] достоверно выполняется "чаще", чем [math]\displaystyle{ M_2 }[/math] (обозначается [math]\displaystyle{ M_1 \lt \!\! \cdot\ M_2 }[/math]), если [math]\displaystyle{ \mid M_1 \cap P \mid \leq \mid M_2 \cap P \mid }[/math] для любого пути [math]\displaystyle{ P \in {\mathcal N} }[/math] и существует такой путь [math]\displaystyle{ P \in {\mathcal N} }[/math], что [math]\displaystyle{ \mid M_1 \cap P \mid \lt \mid M_2 \cap P \mid }[/math].
Достоверные отношения частоты выполнения играют весьма важную роль при решении задачи оптимизации программы. Целесообразность (оптимизационный эффект) ни одного из оптимизирующих преобразований нельзя гарантировать, если не обеспечены определенные достоверные отношения частоты выполнения между элементами преобразуемого им фрагмента.
Литература
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.