X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~yarrgweb/git?p=ypp-sc-tools.db-live.git;a=blobdiff_plain;f=yarrg%2Frsvalue.c;h=c3fac1a01f9260c0812ea58c0f0bffe23f395fe0;hp=b4e23227d2b42ca598612ac21cb8248150cee9a4;hb=2388148ea6c557995767e4391088838946c2f238;hpb=1170fca71dcf10ed2d046fc22f8f1a63ac2ce5cb diff --git a/yarrg/rsvalue.c b/yarrg/rsvalue.c index b4e2322..c3fac1a 100644 --- a/yarrg/rsvalue.c +++ b/yarrg/rsvalue.c @@ -7,10 +7,10 @@ DEBUG_DEFINE_DEBUGF(value); typedef struct { int mass, volu; } CommodInfo; -static int commodstablesz; -static CommodInfo *commodstable; +static int commodstabsz; +static CommodInfo *commodstab; -static sqlite3_stmt *ss_ipair_dist, *ss_ipair_trades; +static sqlite3_stmt *ss_ipair_dist; static sqlite3_stmt *ss_ite_buy, *ss_ite_sell; #define MAX_LEGS (MAX_ROUTELEN-1) @@ -21,22 +21,19 @@ typedef struct { #define TRADES_PER_BLOCK 10 -typedef struct TradesBlock{ +typedef struct TradesBlock { struct TradesBlock *next; + int ntrades; Trade t[TRADES_PER_BLOCK]; } TradesBlock; -typedef struct { - double distance_loss_factor; - int ntrades; - TradesBlock *trades; -} IslandPair; - -IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */ +static IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */ typedef struct IslandTradeEnd { struct IslandTradeEnd *next; + /* key: */ int commodid, price; + /* values: */ int qty; unsigned long generation; int rownum; @@ -72,22 +69,7 @@ static void avail_c(const Trade *t, IslandTradeEnd **trades, for (search= *trades; search; search=search->next) if (search->commodid==t->commodid && search->price==price) goto found; - /* not found, add new row */ - - search= mmalloc(sizeof(*search)); - search->commodid= t->commodid; - search->price= price; - search->next= *trades; - search->generation= 0; - - SQL_BIND(ss_ite, 1, islandid); - SQL_BIND(ss_ite, 2, t->commodid); - SQL_BIND(ss_ite, 3, price); - assert(SQL_STEP(ss_ite)); - search->qty= sqlite3_column_int(ss_ite, 0); - SQL_MUST( sqlite3_reset(ss_ite) ); - - *trades= search; + abort(); found:; if (search->generation != generation) { @@ -136,7 +118,7 @@ static void add_leg_c(int startrow, int leg, double value) { add_constraint(startrow+leg, value); } -static IslandPair *ipair_get(int si, int di) { +IslandPair *ipair_get(int si, int di) { IslandPair *ip, **ipa; assert(si < islandtablesz); @@ -149,45 +131,21 @@ static IslandPair *ipair_get(int si, int di) { return ip; ipa[di]= ip= mmalloc(sizeof(*ip)); - ip->ntrades= 0; ip->trades= 0; - int inblock= TRADES_PER_BLOCK; - TradesBlock *block=0, **tail=&ip->trades; + ip->route_tail_value= -1; - debugf("VALUE ipair_get(%d,%d) running...\n", si,di); + 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) ); assert(SQL_STEP(ss_ipair_dist)); int dist= sqlite3_column_int(ss_ipair_dist, 0); ip->distance_loss_factor= pow(distance_loss_factor_per_league, dist); sqlite3_reset(ss_ipair_dist); - - SQL_MUST( sqlite3_bind_int(ss_ipair_trades, 1, si) ); - SQL_MUST( sqlite3_bind_int(ss_ipair_trades, 2, di) ); - - while (SQL_STEP(ss_ipair_trades)) { - if (inblock == TRADES_PER_BLOCK) { - block= mmalloc(sizeof(*block)); - block->next= 0; - *tail= block; - tail= &block->next; - inblock= 0; - } - int *irp, i; - for (i=0, irp=&block->t[inblock].commodid; i<3; i++, irp++) - *irp= sqlite3_column_int(ss_ipair_trades, i); - ip->ntrades++; - inblock++; - } - if (inblock < TRADES_PER_BLOCK) - block->t[inblock].commodid= -1; - - sqlite3_reset(ss_ipair_trades); return ip; } -double value_route(int nislands, const int *islands) { +double value_route(int nislands, const int *islands, int exclude_arbitrage) { int s,d; /* We need to construct the LP problem. GLPK talks @@ -244,7 +202,9 @@ double value_route(int nislands, const int *islands) { s++, delay_slot_loss_factor *= LOSS_FACTOR_PER_DELAY_SLOT) { int si= islands[s]; - for (d=s; dtrades; - int tradestodo= ip->ntrades; - if (!tradestodo) - goto next_d; - int inblock= 0; - int col= lpx_add_cols(lp,ip->ntrades); + if (!ip->trades) + goto next_d; double loss_factor= delay_slot_loss_factor * ip->distance_loss_factor; debugf(" SOME i%d#%d..i%d#%d dslf=%g dlf=%g lf=%g\n", si,s, di,d, delay_slot_loss_factor, ip->distance_loss_factor, loss_factor); - while (tradestodo-- >0) { - if (inblock >= TRADES_PER_BLOCK) { - block= block->next; - inblock= 0; - } - Trade *t= &block->t[inblock++]; - - debugf(" TRADE i%d#%d..i%d#%d c%d %d-%d ", - si,s, di,d, t->commodid, t->src_price, t->dst_price); - - nconstraint_rows=0; - - avail_c(t, &itradeends[si].src, t->src_price, "src", si, ss_ite_sell); - avail_c(t, &itradeends[di].dst, t->dst_price, "dst", di, ss_ite_buy); - - int leg; - for (leg=s; legcommodid].mass*1e-3); - add_leg_c(volu_constraints,leg, commodstable[t->commodid].volu*1e-3); - add_leg_c(capi_constraints,leg, t->src_price); - } - - double unit_profit= t->dst_price * loss_factor - t->src_price; - debugf(" unit profit %f\n", unit_profit); - - lpx_set_col_bnds(lp, col, LPX_LO, 0, 0); - lpx_set_obj_coef(lp, col, unit_profit); - lpx_set_mat_col(lp, col, nconstraint_rows, - constraint_rows, constraint_coeffs); - - if (DEBUGP(value)) { - char *name= masprintf("c%d_p%d_%d_p%d_%d", - t->commodid, s, t->src_price, d, t->dst_price); - lpx_set_col_name(lp, col, name); - free(name); - } - - col++; - } /* while (tradestodo-- >0) */ + TradesBlock *block; + for (block=ip->trades; block; block=block->next) { + int inblock; + for (inblock=0; inblockntrades; inblock++) { + Trade *t= &block->t[inblock]; + + debugf(" TRADE i%d#%d..i%d#%d c%d %d-%d ", + si,s, di,d, t->commodid, t->src_price, t->dst_price); + + nconstraint_rows=0; + + avail_c(t, &itradeends[si].src, t->src_price, "src", si,ss_ite_sell); + avail_c(t, &itradeends[di].dst, t->dst_price, "dst", di,ss_ite_buy); + + int leg; + for (leg=s; legcommodid].mass*1e-3); + add_leg_c(volu_constraints,leg, commodstab[t->commodid].volu*1e-3); + add_leg_c(capi_constraints,leg, t->src_price); + } + + double unit_profit= t->dst_price * loss_factor - t->src_price; + debugf(" unit profit %f\n", unit_profit); + if (unit_profit <= 0) continue; + + int col= lpx_add_cols(lp,1); + lpx_set_col_bnds(lp, col, LPX_LO, 0, 0); + lpx_set_obj_coef(lp, col, unit_profit); + lpx_set_mat_col(lp, col, nconstraint_rows, + constraint_rows, constraint_coeffs); + + if (DEBUGP(value)) { + char *name= masprintf("c%d_p%d_%d_p%d_%d", t->commodid, + s, t->src_price, d, t->dst_price); + lpx_set_col_name(lp, col, name); + free(name); + } + } /* inblock */ + } /* block */ /*----- that's done adding these trades to the LP problem -----*/ @@ -342,53 +298,110 @@ double value_route(int nislands, const int *islands) { return profit; } +#define TRADE_FROM \ + " FROM sell, buy\n" \ + " WHERE sell.commodid=buy.commodid AND sell.price < buy.price\n" + +static void read_trades(void) { + /* We would like to use DISTINCT but sqlite3 is too stupid + * to notice that it could use the index to do the DISTINCT + * which makes it rather slow. */ + sqlite3_stmt *ss_trades; + +#define TRADE_COLS \ + "sell.commodid, sell.islandid, sell.price, buy.islandid, buy.price" + SQL_PREPARE(ss_trades, + " SELECT " TRADE_COLS "\n" + TRADE_FROM + " ORDER BY " TRADE_COLS); + + SQL_DISTINCT_DECL(cols,5); + while (SQL_DISTINCT_STEP(ss_trades,cols,5)) { + IslandPair *ip= ipair_get(cols[1], cols[3]); + TradesBlock *block= ip->trades; + if (!block || ip->trades->ntrades >= TRADES_PER_BLOCK) { + block= mmalloc(sizeof(*block)); + block->next= ip->trades; + ip->trades= block; + block->ntrades= 0; + } + Trade *trade= &block->t[block->ntrades]; + trade->commodid= cols[0]; + trade->src_price= cols[2]; + trade->dst_price= cols[4]; + block->ntrades++; + } + sqlite3_finalize(ss_trades); +} + +static void read_islandtradeends(const char *bs, int srcdstoff) { + +#define TRADEEND_KEYCOLS "%s.commodid, %s.islandid, %s.stallid" + char *stmt= masprintf(" SELECT " TRADEEND_KEYCOLS ", %s.price, %s.qty\n" + TRADE_FROM + " ORDER BY " TRADEEND_KEYCOLS, + bs,bs,bs,bs,bs, bs,bs,bs); + char *stmt_id= masprintf("qtys (%s)",bs); + sqlite3_stmt *ss= sql_prepare(stmt, stmt_id); + free(stmt); free(stmt_id); + + SQL_DISTINCT_DECL(cols,5); + while (SQL_DISTINCT_STEP(ss,cols,3)) { + IslandTradeEnd *search; + + int commodid= cols[0]; + int islandid= cols[1]; + int price= cols[3]; + int qty= cols[4]; + + IslandTradeEnd **trades= (void*)((char*)&itradeends[islandid] + srcdstoff); + + for (search= *trades; search; search=search->next) + if (search->commodid==commodid && search->price==price) + goto found; + /* not found, add new end */ + + search= mmalloc(sizeof(*search)); + search->commodid= commodid; + search->price= price; + search->next= *trades; + search->generation= 0; + search->qty= 0; + *trades= search; + + found: + search->qty += qty; + } + sqlite3_finalize(ss); +} + void setup_value(void) { sqlite3_stmt *sst; int i; - commodstablesz= sql_single_int("SELECT max(commodid) FROM commods") + 1; - commodstable= mmalloc(sizeof(*commodstable)*commodstablesz); - for (i=0; i=0 && id=0 && id sell.price\n" - " WHERE sell.islandid=?\n" - " AND buy.islandid=?"); - -#define BS(bs) \ - SQL_PREPARE(ss_ite_##bs, \ - "SELECT\n" \ - " sum(qty)\n" \ - " FROM " #bs "\n" \ - " WHERE islandid=?\n" \ - " AND commodid=?\n" \ - " AND price=?"); - BS(buy) - BS(sell) -#undef BS - - ipairs= mcalloc(sizeof(*ipairs) * islandtablesz); + read_trades(); + read_islandtradeends("sell", offsetof(IslandTradeEndHeads, src)); + read_islandtradeends("buy", offsetof(IslandTradeEndHeads, dst)); }