On Sun, May 10, 2015 at 2:02 AM, Svante v. Erichsen < Svante.v.Erichsen@web.de> wrote:
How did you determine the threshold to switch to Fisher-Yates?
Mostly, I inferred it from my previous experience with similar algorithms... and it is completely wrong!
I have been benchmarking an instrumentalized version of the shuffle-sublist function (code attached) with several FLOSS common-lisp implementations and found the following results:
For SBCL and Clozure CL, the optimal cut-point is around 200 and 150 respectively. I have run it with different list sizes and in a couple of machines, and the results seem consistent.
For ECL, the optimal cut-point seems to be around 10000. In any case, it runs much slower than in SBCL or in CCL.
For GCL, the optimal cut-point seems to be around 5000 and it is also much slower than SBCL or CCL.
Considering those results I would choose 200 as the best cut point because it is where SBCL and CCL perform best without incurring in a great penalty for ECL and GCL (~40%). Note also that performance degrades quite fast for SBCL and CCL once the optimal cut point is surpassed.
I would also be interested to see how commercial Lisp implementations behave.