Sequential stateful without short circuiting:An array N elements is created, all initialized to true. We start iterating over the array from index one, keep on setting values to false whenever (Count mod K) is 0. We keep track of number of survivors also and as soon as it reaches 1, we return the closest array index which is still true( or alive). As we never remove elements from array (no short circuiting).
declare
fun {Josephus N K}
A = {NewArray 1 N true}
fun {NextI I} (I mod N)+1 end
fun {Iter N C I}
if N==1 andthen {Array.get A I}==true then I
elseif N==1 then {Iter N C {NextI I}}
elseif {Array.get A I}==true andthen (C mod K)==0 then
{Array.put A I false}
{Iter N-1 C+1 {NextI I}}
elseif {Array.get A I}==true then
{Iter N C+1 {NextI I}}
else {Iter N C {NextI I}}
end
end
in
{Iter N 1 1}
end
Sequential stateful with short circuiting:The only difference here is that, we use a dictionary instead of array and remove(rather than setting value to false) whenever (Count mod K) is 0. Structurally both these programs are the same.
declare
fun {Josephus N K}
D = {NewDictionary}
for I in 1..N do D.I:=t end
fun {NextI I} (I mod N)+1 end
fun {Iter N C I}
if N==1 andthen {Dictionary.condGet D I f}==t then I
elseif N==1 then {Iter N C {NextI I}}
elseif {Dictionary.condGet D I f}==t
andthen (C mod K)==0 then
{Dictionary.remove D I}
{Iter N-1 C+1 {NextI I}}
elseif {Dictionary.condGet D I f}==t then
{Iter N C+1 {NextI I}}
else {Iter N C {NextI I}}
end
end
in
{Iter N 1 1}
end
Structure of Active object based version from the book:Here we basically create a doubly linked list of Victim active objects and pass the kill(I) token. Every Vicim on the list passes the token to next object in the list(and also is removed if I mod K is 0). This way the token keeps on circulating untill there is just one item(survivor) remaining in the list.
Apart from the models used, The main differences between the above versions and those there in the book, are in the code size and the iteration. In above versions iterations is done explicitly while in the versions from the book iteration is implicit due to the message passing technique.
b) I'm passing the analysis of finding the (n,k) region for which short circuiting is helpful because It's easy to understand by logic only. Larger the N and smaller the K(but greater than 1 or else there won't be second iteration and hence no use of shortcircuiting), more is the advantage of short circuiting as less number of items are to be traversed in subsequenct iterations one after another. If short circuiting was not there then we have to traverse all N items in all the iterations no matter how many of them are alive.
However, in above two versions the version with short circuiting is actually slower but that is because Dictionary operations are much more expensive than Array operations and that shadows the advantage bought by short circuiting.
I used following code to find about the timings of the three versions.
for N in 1000..1050 do
for K in 100..110 do T1 T2 R in
T1 = {Property.get 'time.total'}
R = {Josephus N K}
{Wait R}
T2 = {Property.get 'time.total'}
{Show josephus(n:N k:K result:R timeTaken:(T2-T1))}
end
end
The version that uses OO model was hovering around 130ms, declarative concurrent version(fastest) was hovering aroung 70ms and declarative sequential model(slowest) was taking around 210ms. Declarative sequential model is slow because of the Dictionary operations as they're expensive.
Asymptotically all three versions have the same time complexity as they're effectively doing the same thing which is to keep on following the list(killing the unfortunates on the way and removing them from the list) circularly unless there is only one survivor left. Note: The word list is used in a very loose sense, its not the list type of oz.
=========================================================================
A declarative sequential solution to josephus problem...While reading the book I wrote this one(nothing fancy).We start with a list [1..N], keep on iterating over it in circular fashion and keep on removing every Kth item untill there is just one element left and that last element is the survivor.
declare Josephus
local
%Generates list [1 2 3..N]
%Usage: {GenerateList N nil}
fun {GenerateList N A}
if N>0 then {GenerateList N-1 N|A}
else A end
end
in
fun {Josephus N K}
% N: number of survivors
% C: count
% Xs: Active list of survivors
% Ys: ongoing list of survivors from Xs
fun {Iter N C Xs Ys}
if N==1 then Xs.1
else
case Xs of X|nil andthen (C mod K)==0 then
{Iter N-1 C+1 {Reverse Ys} nil}
[] X|nil then
{Iter N C+1 {Reverse X|Ys} nil}
[] X|Xr andthen (C mod K)==0 then
{Iter N-1 C+1 Xr Ys}
[] X|Xr then
{Iter N C+1 Xr X|Ys}
end
end
end
in
{Iter N 1 {GenerateList N nil} nil}
end
end
