The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Josephus Flavius Problem in Prolog
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 9 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Jun 18 2009, 8:19 pm
From: "Benjamin Johnston" <johns...@it.uts.edu.au>
Date: Fri, 19 Jun 2009 10:19:02 +1000
Local: Thurs, Jun 18 2009 8:19 pm
Subject: Josephus Flavius Problem in Prolog

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...
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
- 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

-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).

%---------------------

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 21 2009, 2:58 am
From: Erik de Castro Lopo <mle...@mega-nerd.com>
Date: Sun, 21 Jun 2009 16:58:47 +1000
Local: Sun, Jun 21 2009 2:58 am
Subject: Re: [fp-syd] Josephus Flavius Problem in Prolog

Benjamin Johnston wrote:
> 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/

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 21 2009, 4:59 am
Date: Sun, 21 Jun 2009 18:59:47 +1000
Local: Sun, Jun 21 2009 4:59 am
Subject: Re: [fp-syd] Josephus Flavius Problem in Prolog
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.

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

On Fri, Jun 19, 2009 at 10:19 AM, Benjamin

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 21 2009, 6:32 am
From: "Benjamin Johnston" <johns...@it.uts.edu.au>
Date: Sun, 21 Jun 2009 20:32:09 +1000
Local: Sun, Jun 21 2009 6:32 am
Subject: RE: [fp-syd] Re: Josephus Flavius Problem in Prolog

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 21 2009, 2:07 pm
From: André Pang <oz...@algorithm.com.au>
Date: Sun, 21 Jun 2009 11:07:29 -0700
Local: Sun, Jun 21 2009 2:07 pm
Subject: Re: [fp-syd] Re: Josephus Flavius Problem in Prolog
On Jun 21, 2009, at 1:59 AM, Mark Bradley wrote:

> 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?

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 21 2009, 9:09 pm
Date: Mon, 22 Jun 2009 11:09:04 +1000
Local: Sun, Jun 21 2009 9:09 pm
Subject: Re: [fp-syd] Re: Josephus Flavius Problem in Prolog
2009/6/22 André Pang <oz...@algorithm.com.au>:

> On Jun 21, 2009, at 1:59 AM, Mark Bradley wrote:

>> 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?

nope

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 24 2009, 12:51 pm
From: Simon Winwood <s...@cse.unsw.edu.au>
Date: Thu, 25 Jun 2009 02:51:32 +1000
Local: Wed, Jun 24 2009 12:51 pm
Subject: Re: [fp-syd] Josephus Flavius Problem in Prolog

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
}

Simon

At Fri, 19 Jun 2009 10:19:02 +1000,

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 25 2009, 4:33 am
From: Manuel M T Chakravarty <c...@cse.unsw.edu.au>
Date: Thu, 25 Jun 2009 18:33:16 +1000
Local: Thurs, Jun 25 2009 4:33 am
Subject: Re: [fp-syd] Re: Josephus Flavius Problem in Prolog

> 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

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 28 2009, 12:24 am
From: Leon Smith <leon.p.sm...@gmail.com>
Date: Sat, 27 Jun 2009 21:24:39 -0700 (PDT)
Local: Sun, Jun 28 2009 12:24 am
Subject: Re: Josephus Flavius Problem in Prolog
Mark,  I'm curious what you mean by cycling,  and if you could post
the source code somewhere.  :-)  I'm wondering if it's related to my
own simple solution available here:

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

it probably would be a good idea to factor out that functionality into
enqueue and dequeue operations.

Best,
Leon