![]() Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сравнение реализаций
Постановка задачи Была поставлена задача реализовать алгоритм поиска в ширину и сравнить свою реализацию с реализацией этого алгоритма в библиотеке Boost Graph Library. Boost Graph Library (BGL) предоставляет гибкую и эффективную реализацию концепции графов. В данной библиотеке можно выбрать представление графа (например, список смежности или матрица смежности), тип и алгоритм из большого набора алгоритмов, среди которых имеется алгоритм поиска в ширину. Описание алгоритма Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа Этот алгоритм делает следующее: 1. Добавляет начальную вершину в очередь и помечает её как использованную. 2. Извлекает следующую вершину из очереди и добавляет в очередь смежные ей неиспользованные вершины, помечая их как использованные. 3. Если очередь непуста, переходит к пункту 2. Алгоритм называется поиском в ширину, так как поиск идет вширь: сначала выбираются все соседние для заданной вершины s, затем соседи соседей и так далее.
Реализация алгоритма Реализация алгоритма поиска в ширину с использованием очереди на языке программирования C++ приведена ниже. Данный алгоритм реализован в библиотеке Boost Graph Library. Для его использования необходимо выполнить следующий код:
Сравнение реализаций Для сравнения собственной реализации алгоритма и реализации в библиотеке Boost Graph Library использоваласть функция clock_gettime, которая позволяет получить текущее время. Сравнение времени выполнения этих реализаций представлено на Рис. 1. По этому графику видно, что время выполнения реализации через BGL намного больше, чем время выполнения реализации, представленной на Рис. 1 (примерно в 20 раз). Рис. 2 Сравнение времени выполнения алгоритма Обе реализации алгоритма выполнялись на одном и том же графе и выводили те же данные. Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM.
SeoHammer делает продвижение сайта прозрачным и простым занятием.
Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
Что умеет делать SeoHammer
— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок. — Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта. — Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы). — SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание. SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение Вывод Осмелюсь предположить, что низкая скорость выполнения реализации библиотеки BGL связана с её универсальностью. Из этого исследования можно заключить, что при необходимости использования небольшого числа алгоритмов целесообразнее использовать собственную, пусть и не универсальную, реализацию.
|