Анализ с параллельными алгоритмами

Question

Всем известно, что bubblesort - O(n^2), но это зависит от количества сравнений, необходимых для сортировки. У меня есть вопрос, в котором, если бы меня не интересовало количество сравнений, но время вывода, то как вы это анализируете? Есть ли способ сделать анализ по времени вывода вместо сравнения?

Например, если у вас есть сортировка пузырьков и параллельные сравнения для всех пар (даже тогда нечетные сравнения), то время прохождения будет примерно как 2n-1. Количество сравнений было бы высоким, но мне все равно, поскольку конечное время пропускной способности будет быстрым.

В целом, существует ли общий анализ для общего времени параллельной работы? Если да, просто дайте мне несколько ключевых терминов, и я узнаю все остальное от google.

Answer 1

Анализ алгоритмов не предназначен для реального времени выполнения. Вот для чего нужны ориентиры. Анализ показывает, насколько относительная сложность в программе, но фактическое время выполнения этой программы зависит от многих других факторов, которые строгий анализ не может гарантировать реальное время. Например, что произойдет, если ваша ОС решит приостановить установку вашей программы? Ваше время запуска будет снято. Даже запуск одной и той же программы снова и снова дает разные результаты из-за сложности компьютерных систем (сбоев страниц памяти, сбора мусора виртуальных машин, прерываний ввода-вывода и т. Д.). Анализ не может учитывать их.

Именно поэтому параллельная обработка обычно не рассматривается во время анализа. Механизм «параллелизации» компонентов программы обычно является внешним по отношению к вашему коду и обычно основан на вероятностном алгоритме планирования. Я не знаю, как сделать статический анализ. Еще раз, вы можете запустить набор тестов, и это даст вам среднее время выполнения.

Answer 2

Эффективность времени, которую мы получаем параллельными шагами, может быть измерена round complexity. Там, где каждый раунд состоит из параллельных шагов, происходящих одновременно. Поступая таким образом, мы можем видеть, насколько эффективным является время прохождения, в аналогичном анализе, к которому мы привыкли.

Answer 3

Параллельное программирование - это немного красная селедка. Выполнение предположений о времени выполнения только на большой нотации O может ввести в заблуждение. Чтобы сравнить время выполнения алгоритмов, вам нужно полное уравнение не только большой записи O.

Проблема в том, что большая нотация O указывает на доминирующий термин, поскольку n переходит в бесконечность. Но время работы находится на конечных диапазонах n. Это легко понять из непрерывной математики (мой фон).

Рассмотрите y=Ax и y=Bx^2 Значок Big O сообщит вам, что y=Bx^2 работает медленнее. Однако между (0, A/B) оно меньше y=Ax. В этом случае было бы быстрее использовать алгоритм O (x^2), чем алгоритм O (x) для x<A/B.

Фактически я слышал о алгоритмах сортировки, которые начинаются с алгоритма O (nlogn), а затем переключаются на логарифм O (n^2), когда n достаточно мало.

Лучший пример - умножение матрицы. Наивный алгоритм O (n^3), но есть алгоритмы, которые доходят до O (n^2,3727). Однако каждый алгоритм, который я видел, имеет такую ​​большую константу, что наивный O (n^3) по-прежнему является самым быстрым алгоритмом для всех значений частиц n, и это вряд ли изменится в ближайшее время.

Так что действительно вам нужно полное уравнение для сравнения. Что-то вроде An^3 (давайте проигнорировать условия более низкого порядка) и Bn^2.3727. В этом случае B настолько невероятно велика, что метод O (n^3) всегда выигрывает.

Параллельное программирование обычно просто снижает константу. Например, когда я делаю умножение матрицы с использованием четырех ядер, мое время идет от An^3 до A/4 n^3. То же самое произойдет с вашей параллельной сортировкой пузырьков. Вы уменьшите константу. Поэтому вполне возможно, что для некоторого диапазона значений n ваш параллельный тип пузырьков будет бить непараллельный (или, возможно, даже параллельный) тип слияния. Хотя, в отличие от матричного умножения, я думаю, что диапазон будет довольно небольшим.