UNITY (язык программирования)

UNITY — это язык программирования, созданный К. Мани Чанди и Джаядевом Мисрой для их книги «Проектирование параллельных программ: основа» . Это теоретический язык, который фокусируется на том, что , а не где , когда и как . Язык не содержит методов управления потоком данных , и операторы программы выполняются недетерминированным образом до тех пор, пока операторы не перестанут вызывать изменения во время выполнения. Это позволяет программам работать бесконечно, например, автопилоту или системам безопасности электростанции, а также программам, которые обычно завершаются (которые здесь сходятся к фиксированной точке ).

Описание

Все операторы являются присваиваниями и разделены #. Оператор может состоять из нескольких присваиваний вида a,b,c := x,y,z, или a := x || b := y || c := z. Вы также можете иметь количественный список утверждений , <# x,y : expression :: statement>, где x и y выбираются случайным образом среди значений, удовлетворяющих выражению . аналогично Количественное задание . В <|| x,y : expression :: statement >, оператор выполняется одновременно для всех пар x и y которые удовлетворяют выражению .

Примеры

Пузырьковая сортировка

Пузырьковая сортировка массива путем сравнения соседних чисел и замены их местами, если они расположены в неправильном порядке. С использованием $\Theta (n)$ ожидаемое время, $\Theta (n)$ процессоры и $\Theta (n^{2})$ ожидаемая работа. Причина, по которой у тебя есть только $\Theta (n)$ ожидаемое время, это k всегда выбирается случайным образом из $\{0,1\}$ . Это можно исправить, перевернув k вручную.

Program bubblesort
declare
    n: integer,
    A: array [0..n-1] of integer
initially
    n = 20 #
    <|| i : 0 <= i and i < n :: A[i] = rand() % 100 >
assign
    <# k : 0 <= k < 2 ::
        <|| i : i % 2 = k and 0 <= i < n - 1 ::
            A[i], A[i+1] := A[i+1], A[i] 
                if A[i] > A[i+1] > >
end

Ранговая сортировка

Вы можете отсортировать $\Theta (\log n)$ время с ранговой сортировкой. Вам нужно $\Theta (n^{2})$ процессоры и делают $\Theta (n^{2})$ работа.

Program ranksort
declare
    n: integer,
    A,R: array [0..n-1] of integer
initially
    n = 15 #
    <|| i : 0 <= i < n :: 
        A[i], R[i] = rand() % 100, i >
assign
    <|| i : 0 <= i < n ::
        R[i] := <+ j : 0 <= j < n and (A[j] < A[i] or (A[j] = A[i] and j < i)) :: 1 > >
    #
    <|| i : 0 <= i < n ::
        A[R[i]] := A[i] >
end

Алгоритм Флойда – Уоршалла

Используя алгоритм Флойда – Уоршалла для всех пар алгоритма кратчайшего пути , мы итеративно включаем промежуточные узлы и получаем $\Theta (n)$ время, используя $\Theta (n^{2})$ процессоры и $\Theta (n^{3})$ работа.

Program shortestpath
declare
    n,k: integer,
    D: array [0..n-1, 0..n-1] of integer
initially
    n = 10 #
    k = 0 #
    <|| i,j : 0 <= i < n and 0 <= j < n :: 
        D[i,j] = rand() % 100 >
assign
    <|| i,j : 0 <= i < n and 0 <= j < n ::
        D[i,j] := min(D[i,j], D[i,k] + D[k,j]) > ||
    k := k + 1 if k < n - 1
end

Мы можем сделать это еще быстрее. Следующие программы вычислят кратчайший путь для всех пар в $\Theta (\log ^{2}n)$ время, используя $\Theta (n^{3})$ процессоры и $\Theta (n^{3}\log n)$ работа.

Program shortestpath2
declare
    n: integer,
    D: array [0..n-1, 0..n-1] of integer
initially
    n = 10 #
    <|| i,j : 0 <= i < n and 0 <= j < n ::
        D[i,j] = rand() % 10 >
assign
    <|| i,j : 0 <= i < n and 0 <= j < n ::
        D[i,j] := min(D[i,j], <min k : 0 <= k < n :: D[i,k] + D[k,j] >) >
end

После раунда $r$ , D[i,j] содержит длину кратчайшего пути из $i$ к $j$ длины $0\dots r$ . В следующем раунде длиной $0\dots 2r$ , и так далее.