stupid benchmark

josephus.clj

;; (set! *warn-on-reflection* true)
(set! *unchecked-math* true)

(import 'java.util.ArrayList)

(defn shout [^long counter ^long nth [^long cnt ^ArrayList coll]]
  (loop [counter counter
         [count soldiers] [cnt coll]]
    (if (= 1 count)
      (.get ^ArrayList soldiers 0)
      (recur (long (rem (+ counter count) nth))
             (loop [index 0
                    [new-counter left-over] [0 (ArrayList.)]]
               (if (= index count)
                 [new-counter left-over]
                 (recur (inc index)
                        (if-not (zero? (rem (+ counter index) nth))
                          [(inc new-counter) (doto ^ArrayList left-over
                                                   (.add ^ArrayList (.get ^ArrayList soldiers index)))]
                          [new-counter left-over]))))))))

(defn josephus [^long people ^long nth]
  (shout 0 nth [people (let [soldiers (ArrayList.)]
                         (doseq [x (range 1 (inc people))]
                           (.add ^ArrayList soldiers x))
                         soldiers)]))

(defn run-iterations [iterations times]
  (dotimes [_ times]
    (let [start (System/nanoTime)]
        (dotimes[_ iterations] 
            (josephus 40 3))
        (let [end (System/nanoTime)]
            (println (float (/ (- end start) (* 1000 iterations))))))))

(println (josephus 40 3))
(run-iterations 1000000 10)

josephus.java

import java.util.ArrayList;
import java.util.List;


public class Chain {
    private List < Integer > persons;
    private int index, size;

    public Chain(int size) {
        this.size = size;
        persons = new ArrayList < Integer > (size);
        for (int i = 0 ; i < size ; i++) {
            persons.add(i+1);
        }
    }

    public void kill(int nth)
    {
        index = 0;
        while (size > 1)
            {
                shout(nth);
            }
    }

    public Integer getFirst()
    {
        return persons.get(0);
    }

    public void shout(int nth)
    {
        while (index < size)
            {
                persons.remove(index);
                index += nth - 1;
                size--;
            }
        index -= size;
    }

    public static void run() {
        Chain chain = new Chain(40);
        chain.kill(3);
    }
        
    public static void main(String[] args) {
        int iterations = 1000000;
        int times = 10;
        for(int t = 0 ; t < times; t++) {
            System.gc();
            long start = System.nanoTime();
            for(int i = 0; i < iterations ; i++) {
                run();
            }
            long end = System.nanoTime();
            System.out.println(((end - start) * 1.0)/ (iterations * 1000 ));
        }
        
    }
}

timings.txt

> java -cp ~/code/playground-master/lib/clojure-1.3.0-beta1.jar clojure.main ~/tmp/josephus/list-reduction/josephus.clj
26
8.054568
7.6519504
7.663035

> java Chain                                                          ~  
0.927971938
0.852831584
0.85291521
0.853978969