Josephus Flavius Problem in Prolog
Benjamin Johnston
So, I attempted the Josephus Flavius Problem in Prolog (SWI-Prolog).
Prolog is a personal favourite of mine, but I'll readily admit that it
doesn't do very well performance benchmarks:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=ghc&lang2=
swiprolog&box=1
I think my first and naive Prolog attempt is pretty elegant, and seems to
run faster and more efficiently than my recollection of Mark's results.
On len = 1000000 / Nth = 40 it ran in 53 seconds (including all the I/O),
and used less than 100MB RAM. With aggressive garbage collection, it runs
with less than 32MB RAM in 105 seconds.
Prolog source appears below.
How it works:
The key with my Prolog solution is that I convert the input into a
difference list (this seems to be a Prolog equivalent of the goals of
circular programming). A diff list allows "queue" operations to be performed
in O(1) time.
The algorithm works by treating the diff list as a queue, and dequeueing the
head until it is empty:
- if the head should be killed, then put it in the death list.
- if the head should be saved (for now), then put it back at the end of the
queue.
This naive approach means that solve(List, N, .., ..) runs in about
O(length(List) * N) time.
The code may be confusing if you're unfamiliar with the difference list
idiom; but I think it should be straightforward to Prolog programmers who've
had some experience with it.
-Ben
%---------------------
% "Friendly" interface
solve(Input, Nth, DeathList, Survivor) :-
% Convert the input into a difference list (i.e. a Queue)
append(Input, End, InputDiff),
% Then run the solver...
!, take(Nth, Nth, InputDiff-End, DeathList, Survivor).
%---------------------
% Base case: only one left - it's the survivor
take(_, _, [Survivor|Rest]-End, [Survivor], Survivor) :-
Rest == End, !.
% Found the person to kill: add to death list, reset the counter
take(N, 1, [H|Alive]-End, [H|Dead], Survivor) :-
!, take(N, N, Alive-End, Dead, Survivor).
% Not yet at person to kill: add to the end of the queue, decrement counter
take(N, C, [H|Alive]-[H|NewEnd], Dead, Survivor) :-
C2 is C - 1,
!, take(N, C2, Alive-NewEnd, Dead, Survivor).
%---------------------
Erik de Castro Lopo
> So, I attempted the Josephus Flavius Problem in Prolog (SWI-Prolog).
Thanks Ben, thats very cool.
The only problem is I can't figure out how to compile it :-). I've
installed SWI-Prolong version 5.6.59 on an Ubuntu Linux system and
I've read the man page for swipl but I still can't figure it out.
Clues?
Cheers,
Erik
--
----------------------------------------------------------------------
Erik de Castro Lopo
http://www.mega-nerd.com/
Mark Bradley
second execution time, even runghc gives 3 seconds, so there must be
something horribly inefficient happening in ghci.
and when compiled with heap profiling it uses less than 30M with a
nice mountain peak at 0.5 seconds and a slow decline from 25M - 20M
until dropping at the end.
I probably should have done this sort of profiling for the talk but I
ran out of preparation time and didn't think there would be such a
giant difference.
I've also gathered some data when using a 10 million input list of victims.
1 million input list
---------------
Program -> Time -> Memory
ghc -> 3s (5s with profiling) -> max 30M (total 82M)
runghc -> 3s -> can only assume it is similar, my runghc isnt compiled
with profiling
ghci -> 90s -> 3.6G (:set +s)
10 million input list
---------------
Program -> Time -> Memory
ghc -> 30s (150s with profiling) -> max 400M (total 33G - this value
lines up with ghci's memory usage so maybe they are related?)
ghci -> (long coffee break) 1,100s -> 32.8G
there is more things i could test (passing in the length instead of
computing it, only printing the final result etc) but im satisfied
with what i have. Also the 10 milion input list has some obvious
garbage collection pauses
-markb
Benjamin Johnston
The easiest way is as follows.
Create a file: e.g., josephus.pl, with the source (attached).
Launch swipl
Then you can test it as follows:
?- [josephus].
% josephus compiled 0.02 sec, 1,756 bytes
true.
?- solve([1,2,3,4,5], 2, DeathList, Survivor).
DeathList = [2, 4, 1, 5, 3],
Survivor = 3.
?- halt.
PS. The first two arguments must be fully ground and the last two arguments
must be variables (i.e., the mode is: solve(+list,+num,-list,-elem))
-Ben
André Pang
> the performance i gathered was using ghci, compiling gives it a 3
> second execution time, even runghc gives 3 seconds, so there must be
> something horribly inefficient happening in ghci.
Did you compile with -O?
Mark Bradley
i compiled with these commands and got the same result (profiling made
it a little slower)
$ ghc --make josephus.hs
$ ghc josephus.hs
$ ghc -prof josephus.hs
>
>
> >
>
Simon Winwood
Just to represent :)
This is pretty much the same algorithm; we could probably speed
it up by being clever with the stack (we don't really need to reverse
it each time around). I also got rid of the death list mainly because
it takes ages to print out for n = 1000000.
How would I get numbers for this case with your code?
Anyway, the code is below. Unoptimised, it takes about 8.8
seconds (19M max), with -O2 it takes 6.2 (~ 20M). Time was measured
with time, space with heap profiling -- top had a resident size of
57M, but who knows what is in there.
josephus :: Int -> Int -> Int
josephus n m = josephus' (m - 1) (m - 1) ([1..n], [])
josephus' :: Int -> Int -> ([Int], [Int]) -> Int
josephus' m n ([x], []) = x
josephus' m n ([], stack) = josephus' m n (reverse stack, [])
josephus' m 0 (x:xs, stack) = josephus' m m (xs, stack)
josephus' m n (x:xs, stack) = josephus' m (n - 1) (xs, x : stack)
main = do {
; [num, nth] <- getArgs
; putStrLn $ show $ josephus (read num) (read nth)
}
Simon
At Fri, 19 Jun 2009 10:19:02 +1000,
Manuel M T Chakravarty
> the performance i gathered was using ghci, compiling gives it a 3
> second execution time, even runghc gives 3 seconds, so there must be
> something horribly inefficient happening in ghci.
GHCi is an *interpreter* with very little optimisation as it isn't
intended for "production" runs of any code. It also maintains data
structures for source level debugging. There is no point in
benchmarking ghci code.
> and when compiled with heap profiling it uses less than 30M with a
> nice mountain peak at 0.5 seconds and a slow decline from 25M - 20M
> until dropping at the end.
For any meaningful benchmarking, you need to compile with -O or -O2.
> 10 million input list
> ---------------
> Program -> Time -> Memory
> ghc -> 30s (150s with profiling) -> max 400M (total 33G - this value
> lines up with ghci's memory usage so maybe they are related?)
If you compiled without -O, then they are related by both *lacking*
any significant static optimisations. (However, the compiled code is
at least not interpreted.)
Manuel
Leon Smith
the source code somewhere. :-) I'm wondering if it's related to my
own simple solution available here:
http://lambda-the-ultimate.org/node/1872#comment-22984
If you are using GHC 6.10.3, you should be able to speed up my
solution slightly by using "splitAt", however this should be a bit
of a slowdown if you are using GHC 6.8.3. To second Manuel
Chakravarty, you really need to compile with ghc -O or -O2 to make
any kind of meaningful benchmark. -O turns on strictness analysis,
which tends to be a particularly important optimization for most
programs. I normally compile -O2 all the time, if you use recent
versions of GHC and use the native code generator (not via-c) the
compiler is pretty fast on modern machines.
You can still interact with compiled files using GHCi, though be
warned that if you don't export them from the module or compile using
a flag I don't remember, the functions won't be visible in GHCi.
You can export all functions by writing "module ModuleName where" at
the top of your file.
Simon, your solution encodes the traditional two-stack queue, and
it probably would be a good idea to factor out that functionality into
enqueue and dequeue operations.
Best,
Leon