shithub: puzzles

Info  •  Files  •  Log  •  Branches

James H profiled the new Same Game grid generator and discovered it
was spending 60% of its time in shuffle(). The purpose of the
shuffle() call was to go through a largish array in random order
until we found an element that worked, so there's no actual need to
shuffle the whole array every time and I only did it out of
laziness. So I now pick a random element each time I go round the
loop, meaning I save a lot of shuffling effort whenever the loop
terminates early (which is often). I get about a factor of two speed
improvement from this small change.

[originally from svn r6125]

--- a/samegame.c

+++ b/samegame.c

@@ -398,11 +398,6 @@

             if (n == 0)

                 break;		       /* we're done */

-            /*

-             * Shuffle the list.

-             */

-            shuffle(list, n, sizeof(*list), rs);

-

 #ifdef GENERATION_DIAGNOSTICS

             printf("initial grid:\n");

             {

@@ -420,13 +415,17 @@

 #endif

             /*

-             * Now go through the list one element at a time and

-             * actually attempt to insert something there.

+             * Now go through the list one element at a time in

+             * random order, and actually attempt to insert

+             * something there.

              */

             while (n-- > 0) {

                 int dirs[4], ndirs, dir;

-                pos = list[n];

+                i = random_upto(rs, n+1);

+                pos = list[i];

+                list[i] = list[n];

+

                 x = pos % w;

                 y = pos / w;