From 43093e371fc9661baaf5a6d51cb1a8810ecffc19 Mon Sep 17 00:00:00 2001 From: simon Date: Fri, 22 Jul 2005 11:06:57 +0000 Subject: [PATCH] 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. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@6125 cda61777-01e9-0310-a592-d414129be87e --- samegame.c | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-) diff --git a/samegame.c b/samegame.c index 60e0272..b9078eb 100644 --- a/samegame.c +++ b/samegame.c @@ -398,11 +398,6 @@ static void gen_grid(int w, int h, int nc, int *grid, random_state *rs) 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 @@ static void gen_grid(int w, int h, int nc, int *grid, random_state *rs) #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; -- 2.11.0