Я посещаю класс алгоритмов, и кажется, что алгоритмы «разделяй и властвуй» могут быть реализованы с использованием параллельной обработки. Всегда ли это так?
Все ли алгоритмы «разделяй и властвуй» используют параллелизм?
08.11.2013
- Любой алгоритм может быть реализован с использованием параллельной обработки. Вопрос, который вы действительно хотите задать, заключается в том, должны ли они быть такими. IE: Есть ли в этом какая-то польза. 08.11.2013
Ответы:
1
Да, но не обязательно эффективно.
Алгоритмы «разделяй и властвуй» лучше всего подходят (легче для понимания) для параллелизма на уровне задач. Эти задачи являются рекурсивными, а рекурсивные задачи можно объяснить как иерархию дерева задач. Иерархии дерева задач можно рассматривать как несколько вызовов функции с разными параметрами. Некоторые вызовы функций будут ожидать выполнения других (т. е. своих дочерних элементов), что доступно на параллельном жаргоне как *wait*o или join, если они выполняются асинхронно или доступны непосредственно в синхронных исполнениях (блокировка вызовов будет ожидать результатов автоматически). Все эти операции доступны практически в каждом параллельном фреймворке.
Но связь между параллельными задачами может быть дорогостоящей в зависимости от размера данных параметров. Если разделение и распределение вашей задачи на более мелкие части (по сети для выполнения на нескольких компьютерах или между процессами для многоядерных вычислений) занимает больше времени, чем выполнение частей, вы не получите прироста производительности. Фактически вы потеряете производительность.
Преобразование последовательного алгоритма «разделяй и властвуй» в его параллельный аналог проще при использовании фреймворка, допускающего иерархию задач, такую как задачи OpenMP в C/C++ или SCOOP в Python (доступны многие другие).
08.11.2013
Новые материалы
Создание кнопочного меню с использованием HTML, CSS и JavaScript
Вы будете создавать кнопочное меню, которое имеет состояние наведения, а также позволяет вам выбирать кнопку при нажатии на нее. Финальный проект можно увидеть в этом Codepen .
Шаг 1..
Внедрите OAuth в свои веб-приложения для повышения безопасности
OAuth — это широко распространенный стандарт авторизации, который позволяет приложениям получать доступ к ресурсам от имени пользователя, не раскрывая его пароль. Это позволяет пользователям..
Классы в JavaScript
class является образцом java Script Object. Конструкция «class» позволяет определять классы на основе прототипов с чистым, красивым синтаксисом. // define class Human
class Human {..
Как свинг-трейдеры могут использовать ИИ для больших выигрышей
По мере того как все больше и больше профессиональных трейдеров и активных розничных трейдеров узнают о возможностях, которые предоставляет искусственный интеллект и машинное обучение для улучшения..
Как построить любой стол
Я разработчик программного обеспечения. Я люблю делать вещи и всегда любил. Для меня программирование всегда было способом создавать вещи, используя только компьютер и мое воображение...
Обзор: Машинное обучение: классификация
Только что закончил третий курс курса 4 часть специализации по машинному обучению . Как и второй курс, он был посвящен низкоуровневой работе алгоритмов машинного обучения. Что касается..
Разработка расширений Qlik Sense с qExt
Использование современных инструментов веб-разработки для разработки крутых расширений
Вы когда-нибудь хотели кнопку для установки переменной в приложении Qlik Sense? Когда-нибудь просили..