Достоверные отношения частоты выполнения: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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>p_0</math> до <math>q_0</math>, а <math>\mid P \cap M_1 \mid</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>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>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>. | ||
''' | '''Достоверные отношения частоты выполнения''' играют весьма важную роль при решении задачи ''[[оптимизация программ|оптимизации программы]]''. Целесообразность (оптимизационный эффект) ни одного из оптимизирующих преобразований нельзя гарантировать, если не обеспечены определенные '''достоверные отношения частоты выполнения''' между элементами преобразуемого | ||
им ''[[фрагмент|фрагмента]]''. | им ''[[фрагмент|фрагмента]]''. | ||
==Литература== | ==Литература== | ||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 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.