Performance comparison of Functional C++ 11, Java 8, JavaScript and Wolfram

I summarize the author's algorithm as follows: take an array of R^3 vectors, and for each element in the vector, perform the [+,-,-], [-,+,-], and [-,-,+] transform. So N numbers become 3N numbers, which is followed by a duplicate removal process faciliated by the sorting.

The improvement is that the duplicate removal can be accomplished without sorting.

Let's say you have an array of R^3 already sorted. Then say you create 3 arrays each of which is created by "shifting" the array in each of the 3 directions. Call the original A, and the derived B0, B1, B2. Note that B0, B1, and B2 are each sorted since element within each array is adjusted in the same direction. Then all you need to do is to do a 3-way merge, which takes linear time.

I bet by doing this, the runtime could be significantly reduced. My guess is that it runs in the range of 10-30 seconds (instead of 335 seconds).

A minor nit to pick: the 1,448,575,636 number is not the number of buyouts. (It looks like the number of nodes in the evaluation graph.)

Spoiler: the answer is 111110110111_2. (edit: had the wrong answer)

1) In any of the transformations [(-,-,+),(-,+,-),(+,-,-)], the delta b/w numbers (s-b, s-z, b-z) changes by 0 or 2. What this tells us is that if the delta is odd to start, it will always be odd, if even always even.

2) Since the final state will involve only one type left standing (or else the stronger could eat the weaker), we know that the final counts will be two at 0, one at something >0. Since our losers end with an even delta (0), they must always have had an even delta. In the scenario you proposed, that's s and z (2055 - 2017 = 38). So b, bigcorps, is going to be our winner.

3) Now that we know who will win, we need to find the maximum possible number of bs remaining. Since each move reduces the total population by one, the maximum bs will be produced by the shortest sequence of moves that gets rid of all zs and ss.

4) As long as z>0 and s>0, our best move is to have z eat s, as it drops the population of z and s by 2. So our first sequence is to have all zs eat ss, leaving us with s = 38, b = 4023, z = 0.

5) When z = 0, our only possible move is b eats s, creating a z, which can then be eaten by an s to produce a b, thereby restoring b to its original count and lowering s by 2. After repeating this sequence 19 times to get rid of the 38 ss, we'll have s = 0, b = 4023, z = 0.

Ergo, maximal final state is 4023 bigcorps.

I made some modifications (diverging further from the "functional" nature, if you could call it that) and as you can see it is much faster[0].

Output:

  $ node new-magicForest.js 2017 2055 2006
  total forests: 6128
  { goats: 0, wolves: 0, lions: 4023 }
  total time: 20ms

1. CPUs have gotten very good at doing runtime optimization kinds of things on their own, like predicting branches and reducing the cost of virtual function calls. 2. Java only does optimizations that can be done quickly, since the optimizer has to compete with the executing program itself. 3. The claim was overblown to begin with, and Java is trying to do too many other things, like be secure, that interfere with performance.

I'm instead shocked that the C++ version beat Fortran.

  next_forests.reserve(forests.size() * possible_meals.size());

Is this really true? A sort plus a linear scan has very low constant time factors, good cache locality (depending on the sorting algorithm used), and no need to allocate if you're sorting in place. I've seen good results using sort to filter duplicates in my own performance-sensitive code. Are you saying this technique is "horribly worse" based on your experience or intuition?

  Goats Wolves Lions    C++11  Nimrod
     17     55     6     0.00    0.03
    117    155   106     0.17    0.13
    217    255   206     0.75    0.62
    317    355   306     2.16    1.89
    417    455   406     5.28    4.34
    517    555   506    10.75    8.42
    617    655   606    19.15   14.45
    717    755   706    31.58   23.04
    817    855   806    46.52   33.69
    917    955   906    67.94   48.57
   1017   1055  1006    93.75   65.25
   2017   2055  2006   731.42  500.95

  import qualified Data.Set as S                                                                                                                                                
  
  data Forest = F Int Int Int
    deriving (Eq, Ord, Show)
  
  meal forests = (S.toList . S.fromList)
    [nextForest |
     forest <- forests,
     meal <- possibleMeals,
     let nextForest = forest <+> meal,
     valid nextForest]
   where
    possibleMeals = [
      F (-1) (-1)   1,
      F (-1)   1  (-1),
      F   1  (-1) (-1)]
    F x y z <+> F x' y' z' = F (x+x') (y+y') (z+z')
    valid (F x y z) = x >= 0 && y >= 0 && z >= 0
  
  findStable forest = iter [forest]
   where
    iter forests | not (done forests) = iter (meal forests)
                 | otherwise          = filter stable forests
    done forests = null forests || any stable forests
    stable (F _ 0 0) = True
    stable (F 0 _ 0) = True
    stable (F 0 0 _) = True
    stable _         = False
  
  main = print $ findStable (F 117 155 106)

I may even take a stab at rewriting it myself if I get some time.

Also performance of fortran code is quite dependent on the compiler and compiler options. Somethng that was not well described.