UNITY (programmeringsspråk)

UNITY är ett programmeringsspråk som konstruerats av K. Mani Chandy och Jayadev Misra för deras bok Parallel Program Design: A Foundation . Det är ett teoretiskt språk som fokuserar på vad , istället för var , när eller hur . Språket innehåller ingen metod för flödeskontroll , och programsatser körs på ett icke-deterministiskt sätt tills satser upphör att orsaka ändringar under körning. Detta gör att program kan köras på obestämd tid, såsom autopilot- eller kraftverkssäkerhetssystem, såväl som program som normalt skulle avslutas (som här konvergerar till en fast punkt ).

Beskrivning

Alla påståenden är tilldelningar och separeras med # . Ett påstående kan bestå av flera tilldelningar, av formen a,b,c := x,y,z eller a := x || b := y || c := z . Du kan också ha en kvantifierad satslista , <# x,y : expression :: sats > , där x och y väljs slumpmässigt bland de värden som uppfyller expression . Ett kvantifierat uppdrag är liknande. I <|| x,y : expression :: sats > , sats exekveras samtidigt för alla par av x och y som uppfyller expression .

Exempel

Bubblesort

Bubblesortera arrayen genom att jämföra intilliggande nummer och byta dem om de är i fel ordning. Använder $\Theta (n)$ förväntad tid, $\Theta (n)$ processorer och $\Theta (n^{2})$ förväntat arbete. Anledningen till att du bara har $\{0,1\}$ $\displaystyle \Theta (n)}$ förväntad tid, är att k alltid väljs slumpmässigt från . Detta kan åtgärdas genom att vända k manuellt.

Program bubblesort deklarera n: heltal, A: matris [0..n-1] av heltal initialt n = 20 # <|| i : 0 <= i och i < n :: A[i] = rand() % 100 > tilldela <# k : 0 <= k < 2 :: <|| i : i % 2 = k och 0 <= i < n - 1 :: A[i], A[i+1] := A[i+1], A[i] om A[i] > A[ i+1] > > slut

Rang-sortera

Du kan sortera i $\Theta (\log n)$ tid med rank-sort. Du behöver ${\displaystyle \Theta (n^{2})}-$ processorer och gör $\Theta (n^{2})$ arbete.

Program ranksort deklarera n: heltal, A,R: array [0..n-1] av heltal initialt n = 15 # <|| i : 0 <= i < n :: A[i], R[i] = rand() % 100, i > tilldela <|| i : 0 <= i < n :: R[i] := <+ j : 0 <= j < n och (A[j] < A[i] eller (A[j] = A[i] och j < i)) :: 1 > > # <|| i : 0 <= i < n :: A[R[i]] := A[i] > slut

Floyd-Warshall-algoritm

Genom att använda Floyd–Warshall-algoritmen alla pars kortaste väg- algoritm, inkluderar vi intermediära noder iterativt och får $\Theta (n)$ tid, med $\Theta (n^{ 2})$ processorer och $\Theta (n^{3})$ fungerar.

Programmets kortaste väg deklarerar n,k: heltal, D: array [0..n-1, 0..n-1] av heltal initialt n = 10 # k = 0 # <|| i,j : 0 <= i < n och 0 <= j < n :: D[i,j] = rand() % 100 > tilldela <|| i,j : 0 <= i < n och 0 <= j < n :: D[i,j] := min(D[i,j], D[i,k] + D[k,j]) > || k := k + 1 om k < n - 1 ände

Vi kan göra detta ännu snabbare. Följande program beräknar alla pars kortaste väg i $) {\displaystyle \Theta (n^{3} )}$ $\displaystyle \Theta (\log ^{2}n)}$ tid, med hjälp av processorer och $\Theta (n^{3}\log n)$ fungerar.

Program shortestpath2 deklarera n: heltal, D: matris [0..n-1, 0..n-1] av heltal initialt n = 10 # <|| i,j : 0 <= i < n och 0 <= j < n :: D[i,j] = rand() % 10 > tilldela <|| i,j : 0 <= i < n och 0 <= j < n :: D[i,j] := min(D[i,j], ) > slut

Efter omgången ${\displaystyle r} innehåller$ D[i,j] längden på den kortaste vägen från $i$ till $j$ av längden $0\dots r$ . I nästa omgång, av längden $0\dots 2r$ , och så vidare.

K. Mani Chandy och Jayadev Misra (1988) Parallell Program Design: A Foundation .