Josephus — More Optimized

(1--n) conses up a list of integers from 1 to n; this costs me Ο(n) in the time it takes to construct the list, and then another Ο(n) for the Dllist.of_list function to walk over it and construct a doubly-linked circular version; then of course the GC tosses away the original (1--n) list.

My new version constructs the circular list directly via an initialization function:

(* return number of survivor, size-tracking optimization, more efficient initialization *)
let josephus n m =
  let init n =
    let rec init' circle =
      let i = Dllist.get circle in
	if i = 1
	then circle
	else init' (Dllist.prepend circle (i-1))
    in
      init' (Dllist.create n)
  in
  let rec j size circle =
    if size = 1
    then Dllist.get circle
    else j (size-1) (Dllist.drop (Dllist.skip circle (m-1)))
  in
    j n (init n)

This yields another factor of 2 speedup.