Открытая коллекция знаний

OpenU.Ru

Справочник UML. Объектно-ориентированное проектирование.

navigation efficiency (эффективность навигации)

Указывает, можно ли эффективно проследить бинарную ассоциацию от одного объекта таким образом, чтобы получить ассоциированный с ним другой объект или множество объектов. Это понятие не применяется к n-арным ассоциациям. Эффективность навигации связана с понятием навигации, однако.tie является его определяющим свойством.
См. navigability.

Семантика

Эффективность навигации можно определить с общей точки зрения, применимо к абстрактному проектированию, а также к различным языкам программирования. Бинарная ассоциация допускает эффективную навигацию в том случае, если средние затраты на получение множества ассоциированных объектов пропорциональны действительному числу объектов в этом множестве (но не верхней границе множественности, которая может быть и неограниченной), плюс фиксированная константа. В терминах, определяющих сложность вычислений, затраты должны составлять 0(п).
Если множественность равна единице или "нуль - единица", то затраты на доступ должны быть постоянными, что исключает поиск в списке переменной длины. При немного более свободном определении эффективности навигации допустимые затраты могут составлять log(n).
Обычно допускающая навигацию ассоциация с множественностью, равной единице, реализуется с помощью указателя, добавляемого в блок, где содержатся атрибуты объекта. Однако возможен и другой внешний вариант реализации с использованием кэш-таблиц, обеспечивающий постоянную среднюю стоимость доступа. То есть ассоциацию можно реализовать в виде объекта-справочной таблицы, которая, хоть и находится вне участвующих в ассоциации классов, обеспечивает возможность навигации между объектами этих классов. (В некоторых ситуациях, при выполнении в реальном времени, нужно ограничивать скорее не средние затраты, а максимально допустимые. Для этого в базовое определение не требуется вносить других изменений, кроме как замену среднего времени на максимально допустимое. Однако вероятностные алгоритмы, такие как хэш-таблицы, придется исключить.)
Если ассоциация не допускает навигацию в нужном направлении, это не означает, что ее вообще нельзя проследить - просто затраты на это могут оказаться слишком значительны (например, в случае поиска в очень большом списке). Если доступ в этом направлении осуществляется редко, то поиск будет вполне приемлемым решением. Эффективность навигации представляет собой концепцию проектирования, которая дает разработчику возможность задавать пути доступа к объектам, принимая во внимание затраты на вычисления. Как правило, говоря о возможности навигации, подразумевают се эффективность.
Ассоциация, которая не допускает эффективной навигации ни в одном из направлений, также возможна (хотя встречается она нечасто). Такую ассоциацию можно реализовать в виде списка связей, в котором осуществляется поиск нужной связи для прослеживания навигации в нужном направлении. Такое прослеживание возможно, однако не эффективно. При моделировании такая ассоциация едва ли может оказаться полезной.

Обсуждение

Эффективность навигации указывает на эффективность, с которой определенный объект может получить доступ к множеству связанных с ним других объектов. Когда множественность представляет
собой 0..1 или 1, то реализацией будет указатель в исходном объекте. При множественности "много" реализацией станет класс-контейнер, в котором содержится множество указателей. Сам класс-контейнер может постоянно присутствовать в виде записи данных объекта этого класса. В любом случае доступ к нему должен осуществляться с постоянными затратами (что является обычной ситуацией при использовании для доступа указателя). Сам класс-контейнер должен обладать эффективной навигацией. Например, простой список всех связей ассоциации не будет эффективным, так как связи для отдельного объекта будут перемешаны с другими, не относящимися к делу связями, и придется делать поиск. А вот список связей объекта, хранящийся с самим объектом, будет эффективным, так как дополнительный поиск в этом случае не нужен.
Если навигация в квалифицированной ассоциации установлена в направлении от кодификатора, это означает, что она эффективна для получения объекта или множества объектов на основе исходного объекта и значения квалификатора. Это соответствует реализации и виде хэш-таблицы или поиска по бинарному дереву, индексированному значением квалификатора (поэтому квалификаторы используются в качестве обычной концепции моделирования).

Алфавитный указатель