From fe6da52b26f14e539183d5eb71e2132a8bf9fa8f Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Fri, 12 Apr 2013 16:28:52 +0000 Subject: [PATCH] Apply some optimisation to Undead's get_unique() function, which was not only enumerating all possible arrangements of monsters along a sight-line in O(3^n) time, but also allocated memory for them all and then does a quadratic-time loop over that list to find arrangements with a unique visibility count from both ends. Spotted by the new 'make test', which observed that 7x7dn#517035041807425 took 45 seconds to generate. This revised version still does the initial O(3^n) enumeration, which can probably be got rid of as well with a bit more thought, but it now doesn't allocate nearly so much memory and it spots uniques efficiently. The above random seed now generates the same game ID in less than a second, which drops this puzzle off the 'make test' hit list of things most obviously needing speedup. [originally from svn r9826] --- undead.c | 67 +++++++++++++++++++++++++++++++------------------------- 1 file changed, 37 insertions(+), 30 deletions(-) diff --git a/undead.c b/undead.c index 4cc4a12..e38c968 100644 --- a/undead.c +++ b/undead.c @@ -576,8 +576,9 @@ int next_list(struct guess *g, int pos) { void get_unique(game_state *state, int counter, random_state *rs) { - int p,i,c,count_uniques; + int p,i,c,pathlimit,count_uniques; struct guess path_guess; + int *view_count; struct entry { struct entry *link; @@ -589,10 +590,10 @@ void get_unique(game_state *state, int counter, random_state *rs) { struct { struct entry *head; struct entry *node; - } views, single_views, loop_views, test_views; + } views, single_views, test_views; struct entry test_entry; - + path_guess.length = state->common->paths[counter].num_monsters; path_guess.guess = snewn(path_guess.length,int); path_guess.possible = snewn(path_guess.length,int); @@ -615,20 +616,17 @@ void get_unique(game_state *state, int counter, random_state *rs) { views.head = NULL; views.node = NULL; + + pathlimit = state->common->paths[counter].length + 1; + view_count = snewn(pathlimit*pathlimit, int); + for (i = 0; i < pathlimit*pathlimit; i++) + view_count[i] = 0; do { - int mirror; + int mirror, start_view, end_view; - views.node = snewn(1,struct entry); - views.node->link = views.head; - views.node->guess = snewn(path_guess.length,int); - views.head = views.node; - views.node->start_view = 0; - views.node->end_view = 0; - memcpy(views.node->guess, path_guess.guess, - path_guess.length*sizeof(int)); - mirror = FALSE; + start_view = 0; for (p=0;pcommon->paths[counter].length;p++) { if (state->common->paths[counter].p[p] == -1) mirror = TRUE; else { @@ -636,17 +634,18 @@ void get_unique(game_state *state, int counter, random_state *rs) { if (state->common->paths[counter].p[p] == state->common->paths[counter].mapping[i]) { if (path_guess.guess[i] == 1 && mirror == TRUE) - views.node->start_view++; + start_view++; if (path_guess.guess[i] == 2 && mirror == FALSE) - views.node->start_view++; + start_view++; if (path_guess.guess[i] == 4) - views.node->start_view++; + start_view++; break; } } } } mirror = FALSE; + end_view = 0; for (p=state->common->paths[counter].length-1;p>=0;p--) { if (state->common->paths[counter].p[p] == -1) mirror = TRUE; else { @@ -654,16 +653,31 @@ void get_unique(game_state *state, int counter, random_state *rs) { if (state->common->paths[counter].p[p] == state->common->paths[counter].mapping[i]) { if (path_guess.guess[i] == 1 && mirror == TRUE) - views.node->end_view++; + end_view++; if (path_guess.guess[i] == 2 && mirror == FALSE) - views.node->end_view++; + end_view++; if (path_guess.guess[i] == 4) - views.node->end_view++; + end_view++; break; } } } } + + assert(start_view >= 0 && start_view < pathlimit); + assert(end_view >= 0 && end_view < pathlimit); + i = start_view * pathlimit + end_view; + view_count[i]++; + if (view_count[i] == 1) { + views.node = snewn(1,struct entry); + views.node->link = views.head; + views.node->guess = snewn(path_guess.length,int); + views.head = views.node; + views.node->start_view = start_view; + views.node->end_view = end_view; + memcpy(views.node->guess, path_guess.guess, + path_guess.length*sizeof(int)); + } } while (next_list(&path_guess, path_guess.length-1)); /* extract single entries from view list */ @@ -680,17 +694,8 @@ void get_unique(game_state *state, int counter, random_state *rs) { while (test_views.head != NULL) { test_views.node = test_views.head; test_views.head = test_views.head->link; - c = 0; - loop_views.head = views.head; - loop_views.node = views.node; - while (loop_views.head != NULL) { - loop_views.node = loop_views.head; - loop_views.head = loop_views.head->link; - if (test_views.node->start_view == loop_views.node->start_view && - test_views.node->end_view == loop_views.node->end_view) - c++; - } - if (c == 1) { + i = test_views.node->start_view * pathlimit + test_views.node->end_view; + if (view_count[i] == 1) { single_views.node = snewn(1,struct entry); single_views.node->link = single_views.head; single_views.node->guess = snewn(path_guess.length,int); @@ -703,6 +708,8 @@ void get_unique(game_state *state, int counter, random_state *rs) { } } + sfree(view_count); + if (count_uniques > 0) { test_entry.start_view = 0; test_entry.end_view = 0; -- 2.30.2