<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sun, May 10, 2015 at 2:02 AM, Svante v. Erichsen <span dir="ltr"><<a href="mailto:Svante.v.Erichsen@web.de" target="_blank">Svante.v.Erichsen@web.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
How did you determine the threshold to switch to Fisher-Yates?<br>
<br></blockquote><div><br></div><div>Mostly, I inferred it from my previous experience with similar algorithms... and it is completely wrong!<br><br></div><div>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:<br><br>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.<br><br></div><div>For ECL, the optimal cut-point seems to be around 10000. In any case, it runs much slower than in SBCL or in CCL.<br><br></div><div>For GCL, the optimal cut-point seems to be around 5000 and it is also much slower than SBCL or CCL.<br><br></div><div>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.<br><br></div><div>I would also be interested to see how commercial Lisp implementations behave.<br><br><br></div></div></div></div>