Dan Rosén wrote:
What complexity does these functions have?
I argue that the shuffleArr function should be O(n), since it only contains one loop of n, where each loop does actions that are O(1): generating a random number and swapping two elements in an array.
However, they both have the same runnig time (roughly), and through looking at the plot it _very_ much looks quadratic.
Right. In the case of shuffleArr, it's the garbage collection time that explodes. I think that the reason is that the garbage collector has to scan the whole array (which lives in the old generation) on each garbage collection, while the young generation is kept very small, making GCs very frequent. Indeed the program behaves much better with just one GC generation:
./a.out +RTS -G1 (1000000, 1988698, 1760732, 1.98870,1.76073) (1500000, 2991546, 2683592, 1.99436,1.78906) (2000000, 4018388, 3611451, 2.00919,1.80573)
Output format: (n, time for your original shuffleArray (t1), time for Daniel's stricter version (t2), t1/n, t2/n) While with the default settings, it looks much worse:
./a.out (1000000, 7575850, 7958790, 7.57585, 7.95879) (1500000,17119397,19449044,11.41293,12.96602) (2000000,30687335,35125661,15.34367,17.56283)
You can also increase the initial heap size,
./a.out +RTS -H250M (1000000, 1131828, 901863, 1.13183, 0.90186) (1500000, 1726737, 1427783, 1.15116, 0.95186) (2000000, 2324647, 1935705, 1.16232, 0.96785)
Bertram