From: Ian Jackson Date: Fri, 9 Oct 2009 21:04:23 +0000 (+0100) Subject: WIP routesearch; route high table X-Git-Tag: 5.0^2~61 X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~yarrgweb/git?p=ypp-sc-tools.db-test.git;a=commitdiff_plain;h=4ed298fb2ac975783ad1a350659f5ae22825e24e WIP routesearch; route high table --- diff --git a/yarrg/rscommon.h b/yarrg/rscommon.h index 5cbf5b7..bdcc157 100644 --- a/yarrg/rscommon.h +++ b/yarrg/rscommon.h @@ -21,10 +21,15 @@ #define COUNTER_LIST \ CTR(commodities_loaded) \ CTR(trades_loaded) \ + CTR(islands_arbitrage) \ + CTR(ipairs_relevant) \ CTR(quantities_loaded) \ CTR(routes_considered) \ - CTR(routes_eliminated) \ + CTR(routes_quickelim) \ + CTR(routes_stratelim) \ CTR(routes_valued) \ + CTR(newbests_strat_absolute) \ + CTR(newbests_strat_perleague) \ CTR(subroute_tails_valued) \ CTR(subroutes_valued) \ CTR(subroutes_nonempty) @@ -137,9 +142,26 @@ extern int *islandid2arch; }) +typedef struct { + double value; + PotentialResult *pr; +} HighScoreEntry; + +extern int nhighscores_absolute, nhighscores_perleague; +extern HighScoreEntry *highscores_absolute; +extern HighScoreEntry *highscores_perleague; + + #define ONDEMAND(pointer_lvalue, calloc_size_count) \ ((pointer_lvalue) ? : \ ((pointer_lvalue) = mcalloc(sizeof(*(pointer_lvalue)) * calloc_size_count))) +static inline int isle2arch(int isle) { + int arch= islandid2arch[isle]; + assert(arch>=0); + return arch; +} + + #endif /*RSCOMMON_H*/ diff --git a/yarrg/rsmain.c b/yarrg/rsmain.c index bde48a1..b3a6d73 100644 --- a/yarrg/rsmain.c +++ b/yarrg/rsmain.c @@ -59,16 +59,24 @@ int main(int argc, const char **argv) { printf("route value is %g\n", val); } else if (!strcmp(arg,"search")) { MCALLOC(results, argc); + max_dist= atoi(*argv++); + nhighscores_absolute= atoi(*argv++); + nhighscores_perleague= atoi(*argv++); + + MCALLOC(highscores_absolute, nhighscores_absolute); + MCALLOC(highscores_perleague, nhighscores_perleague); + int resultsix= 0; - while ((arg= *argv++)) { + while ((arg= argv[resultsix])) { search(atoi(arg), &results[resultsix]); resultsix++; } int i, midarch, finarch; for (i=0; ipr; \ + if (!pr) continue; \ + const int *const ports= pr->absperl##_ports; \ + int nports; \ + for (nports=0; nports=0; nports++); \ + int finisle= ports[nports-1]; int finarch= isle2arch(finisle); \ + int midisle= ports[nports/2]; int midarch= isle2arch(midisle); \ + fprintf(stderr, \ + " @%2d #%2d | start%3d mid %d:%3d f%d:%3d | %5d %5d %4d |", \ + pos, nhighscores_##absperl - 1 - pos, \ + ports[0], midarch,midisle, finarch,finisle, \ + (int)hs->value, (int)pr->absolute, (int)pr->perleague); \ + for (i=0; i=0); - return arch; -} - static double process_route(int nports, int totaldist, double overestimate_excepting_tail) { int i; @@ -58,16 +52,11 @@ static double process_route(int nports, int totaldist, debugf(" %d",ports[i]); debugf("\n"); - int finisle= ports[nports-1]; int finarch= isle2arch(finisle); - int midisle= ports[nports/2]; int midarch= isle2arch(midisle); - - PotentialResult **strat_fin= ONDEMAND(strat_base[finarch], narches); - PotentialResult *strat= ONDEMAND(strat_fin[midarch], 1); - + double guess_absolute=0, guess_perleague=0; if (nports>=2) { int pair[2], i; pair[1]= ports[nports-1]; - double guess_absolute= overestimate_excepting_tail; + guess_absolute= overestimate_excepting_tail; for (i=0; iroute_tail_value; } - double guess_perleague= guess_absolute / leagues_divisor; + guess_perleague= guess_absolute / leagues_divisor; + if (guess_absolute <= highscores_absolute[0].value && + guess_perleague <= highscores_perleague[0].value) { + ctr_routes_quickelim++; + debugf(" QELIM %f %f\n", guess_absolute, guess_perleague); + return guess_absolute; + } + } + + int finisle= ports[nports-1]; int finarch= isle2arch(finisle); + int midisle= ports[nports/2]; int midarch= isle2arch(midisle); + + PotentialResult **strat_fin= ONDEMAND(strat_base[finarch], narches); + PotentialResult *strat= ONDEMAND(strat_fin[midarch], 1); + + if (nports>=2) { if (guess_absolute <= strat->absolute && guess_perleague <= strat->perleague) { - ctr_routes_eliminated++; + ctr_routes_stratelim++; debugf(" ELIM %f %f\n", guess_absolute, guess_perleague); return guess_absolute; } @@ -103,14 +107,35 @@ static double process_route(int nports, int totaldist, fildebugf("final %d:%3d mid %d:%3d ",finarch,finisle,midarch,midisle); -#define CHK(absperl) \ - fildebugf(#absperl " %15f", absperl); \ - if (absperl < strat->absperl) { \ - debugf(" "); \ - } else { \ - strat->absperl= absperl; \ - memcpy(strat->absperl##_ports, ports, sizeof(*ports) * nports); \ - fildebugf("** "); \ +#define CHK(absperl) \ + fildebugf(#absperl " %15f", absperl); \ + if (absperl < strat->absperl) { \ + debugf(" "); \ + } else { \ + int pos; \ + ctr_newbests_strat_##absperl++; \ + strat->absperl= absperl; \ + memcpy(strat->absperl##_ports, ports, sizeof(*ports) * nports); \ + if (nports < MAX_ROUTELEN-1) strat->absperl##_ports[nports]= -1; \ + fildebugf("** "); \ + for (pos=0; pos < nhighscores_##absperl; pos++) \ + if (highscores_##absperl[pos].pr == strat) goto found_##absperl; \ + /* not found */ \ + pos= -1; \ + found_##absperl: \ + for (;;) { \ + pos++; \ + if (pos >= nhighscores_##absperl-1) break; /* new top */ \ + if (highscores_##absperl[pos].value >= absperl) break; /* found spot */ \ + if (pos>0) \ + highscores_##absperl[pos-1]= highscores_##absperl[pos]; \ + } \ + pos--; \ + if (pos>0) { \ + highscores_##absperl[pos].value= absperl; \ + highscores_##absperl[pos].pr= strat; \ + } \ + fildebugf("@%2d", pos); \ } CHK(absolute) @@ -147,6 +172,9 @@ void search(int start_isle, PotentialResult ****strat_base_io) { recurse(start_isle,0,0,1e6); } +int nhighscores_absolute, nhighscores_perleague; +HighScoreEntry *highscores_absolute; +HighScoreEntry *highscores_perleague; int narches; char **archnames; diff --git a/yarrg/rsvalue.c b/yarrg/rsvalue.c index 4914ce7..8fe5f22 100644 --- a/yarrg/rsvalue.c +++ b/yarrg/rsvalue.c @@ -145,6 +145,9 @@ static IslandPair *ipair_get_create(int si, int di) { ip->trades= 0; ip->route_tail_value= -1; + if (si==di) ctr_islands_arbitrage++; + else ctr_ipairs_relevant++; + debugf("VALUE ipair_get(i%d,i%d) running...\n", si,di); SQL_MUST( sqlite3_bind_int(ss_ipair_dist, 1, si) ); SQL_MUST( sqlite3_bind_int(ss_ipair_dist, 2, di) ); diff --git a/yarrg/x.gdb b/yarrg/x.gdb index 42aaddc..e83ccaf 100644 --- a/yarrg/x.gdb +++ b/yarrg/x.gdb @@ -1,5 +1,5 @@ file ./routesearch -set args -DN 13460 20210 -1 0.0005 search 10 4 19 134 32 13 24 36 +set args -DN 13460 20210 -1 0.0005 search 30 20 20 4 19 134 32 13 24 36 break setup_search run finish