4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 40: | Строка 40: | ||
Эксперименты проводились на дорожных сетях Западной Европы и США с использованием целевой функции, учитывающей только ожидаемое время в пути. Результаты отражают различные компромиссы между средним временем выполнения запроса (от 5 до 63 микросекунд для США), продолжительностью предварительной обработки (от 59 до 1200 минут) и затратами на хранение (от 21 до 244 байт на узел). Для варианта, использующего три уровня и настроенного для минимального времени выполнения запроса, в таблицах 1 и 2 показана статистика для продолжительности предварительной обработки и эффективности запросов, соответственно. Среднее время выполнения запроса, около 5 микросекунд, на шесть порядков величины меньше, чем у алгоритма Дейкстры. На рис. 2 для каждого ранга r на оси x приведено распределение для 1000 запросов со случайной исходной точкой s и целевым узлом t, для нахождения ответа на которые алгоритму Дейкстры требуется r итераций. Можно различить три уровня маршрутизации при помощи транзитных узлов с небольшими транзитными зонами между ними: для больших рангов достаточно обращения только к первичному уровню, что дает время выполнения запроса около 5 микросекунд, для меньших рангов требуются дополнительные уровни и медианное время выполнения запроса возрастает до 20 микросекунд. | Эксперименты проводились на дорожных сетях Западной Европы и США с использованием целевой функции, учитывающей только ожидаемое время в пути. Результаты отражают различные компромиссы между средним временем выполнения запроса (от 5 до 63 микросекунд для США), продолжительностью предварительной обработки (от 59 до 1200 минут) и затратами на хранение (от 21 до 244 байт на узел). Для варианта, использующего три уровня и настроенного для минимального времени выполнения запроса, в таблицах 1 и 2 показана статистика для продолжительности предварительной обработки и эффективности запросов, соответственно. Среднее время выполнения запроса, около 5 микросекунд, на шесть порядков величины меньше, чем у алгоритма Дейкстры. На рис. 2 для каждого ранга r на оси x приведено распределение для 1000 запросов со случайной исходной точкой s и целевым узлом t, для нахождения ответа на которые алгоритму Дейкстры требуется r итераций. Можно различить три уровня маршрутизации при помощи транзитных узлов с небольшими транзитными зонами между ними: для больших рангов достаточно обращения только к первичному уровню, что дает время выполнения запроса около 5 микросекунд, для меньших рангов требуются дополнительные уровни и медианное время выполнения запроса возрастает до 20 микросекунд. | ||
{| class="wikitable" | |||
|- | |||
! | |||
! colspan="2" | Слой 1 | |||
! colspan="3" | Слой 2 | |||
! colspan="2" | Слой 3 | |||
! | |||
! | |||
|- | |||
! | |||
! <math>| \mathcal{T} |</math> | |||
! <math>|A|</math> ср. | |||
! <math>| \mathcal{T}_2 |</math> | |||
! <math>| table_2 | [ \times 10^6 ]</math> | |||
! <math>|A_2|</math> ср. | |||
! <math>| \mathcal{T}_3 |</math> | |||
! <math>| table_3 | [ \times 10^6 ]</math> | |||
! память [байт/узел] | |||
! время [ч] | |||
|- | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
|- | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
| | |||
|} | |||
Таблица 1. Статистика по предварительной обработке. Представлены размер множеств транзитных узлов, число записей в таблицах расстояний и среднее число узлов доступа на соответствующем уровне, а также расход памяти и время предварительной обработки | Таблица 1. Статистика по предварительной обработке. Представлены размер множеств транзитных узлов, число записей в таблицах расстояний и среднее число узлов доступа на соответствующем уровне, а также расход памяти и время предварительной обработки | ||
{| class="wikitable" | |||
|- | |||
! Header 1 | |||
! Header 2 | |||
! Header 3 | |||
|- | |||
| row 1 cell 1 | |||
| row 1 cell 2 | |||
| row 1 cell 3 | |||
|- | |||
| row 2 cell 1 | |||
| row 2 cell 2 | |||
| row 2 cell 3 | |||
|} | |||
Таблица 2. Эффективность алгоритма маршрутизации при помощи транзитных узлов на 10 000 000 случайных запросов. Столбец для уровня i показывает, на какую часть запросов был дан точный ответ с использованием только информации, доступной на уровнях < i. Каждый «ящик» простирается от нижнего до верхнего квартиля и содержит медианное значение, «усы» простираются до минимального и максимального значений, исключая выбросы, изображенные отдельно | Таблица 2. Эффективность алгоритма маршрутизации при помощи транзитных узлов на 10 000 000 случайных запросов. Столбец для уровня i показывает, на какую часть запросов был дан точный ответ с использованием только информации, доступной на уровнях < i. Каждый «ящик» простирается от нижнего до верхнего квартиля и содержит медианное значение, «усы» простираются до минимального и максимального значений, исключая выбросы, изображенные отдельно |
правка