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.
git-svn-id: svn://svn.tartarus.org/sgt/puzzles@6125
cda61777-01e9-0310-a592-
d414129be87e
if (n == 0)
break; /* we're done */
- /*
- * Shuffle the list.
- */
- shuffle(list, n, sizeof(*list), rs);
-
#ifdef GENERATION_DIAGNOSTICS
printf("initial grid:\n");
{
#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;