chiark
/
gitweb
/
~ianmdlvl
/
matchsticks-search.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
introduce m_over_best and use it instead of computing maxminsize
[matchsticks-search.git]
/
main.c
diff --git
a/main.c
b/main.c
index d2900152f1336eaace2a8b656024f9f48dde100e..69f56d1a30e8bba421e9e7a7231019a45f08b09d 100644
(file)
--- a/
main.c
+++ b/
main.c
@@
-91,6
+91,8
@@
typedef uint32_t AdjWord;
#define PRADJ "08"PRIx32
typedef uint32_t AdjWord;
#define PRADJ "08"PRIx32
+#define FOR_BITS(j,m) for (j=0, j##bit=1; j < (m); j++, j##bit<<=1)
+
static int n, m, maxhamweight;
static AdjWord *adjmatrix;
static AdjWord adjall;
static int n, m, maxhamweight;
static AdjWord *adjmatrix;
static AdjWord adjall;
@@
-99,7
+101,7
@@
static double best;
static glp_prob *best_prob;
static AdjWord *best_adjmatrix;
static glp_prob *best_prob;
static AdjWord *best_adjmatrix;
-static int n_over_best;
+static int n_over_best
, m_over_best
;
static int *weight;
static unsigned printcounter;
static int *weight;
static unsigned printcounter;
@@
-118,6
+120,7
@@
static void progress_eol(void) {
static void set_best(double new_best) {
best = new_best;
n_over_best = floor(n / best);
static void set_best(double new_best) {
best = new_best;
n_over_best = floor(n / best);
+ m_over_best = floor(m / best);
}
/*----- multicore support -----*/
}
/*----- multicore support -----*/
@@
-308,10
+311,10
@@
static void multicore(void) {
for (w=0; w<ncpus; w++) {
mc_rwvsetup_full();
for (w=0; w<ncpus; w++) {
mc_rwvsetup_full();
- LPRINTF("reading report from %2d
\n
",w);
+ LPRINTF("reading report from %2d",w);
ssize_t sr = preadv(fileno(mc_workers[w].results), mc_iov, mc_niovs, 0);
if (!sr) continue;
ssize_t sr = preadv(fileno(mc_workers[w].results), mc_iov, mc_niovs, 0);
if (!sr) continue;
- LPRINTF("got report from %2d
\n
",w);
+ LPRINTF("got report from %2d",w);
maxhamweight = 0;
optimise(1);
}
maxhamweight = 0;
optimise(1);
}
@@
-354,16
+357,20
@@
static void prep(void) {
setlinebuf(stderr);
weight = calloc(sizeof(*weight), m); assert(weight);
n_over_best = INT_MAX;
setlinebuf(stderr);
weight = calloc(sizeof(*weight), m); assert(weight);
n_over_best = INT_MAX;
+ m_over_best = INT_MAX;
}
}
+#if 0
static AdjWord one_adj_bit(int bitnum) {
return (AdjWord)1 << bitnum;
}
static AdjWord one_adj_bit(int bitnum) {
return (AdjWord)1 << bitnum;
}
+#endif
static int count_set_adj_bits(AdjWord w) {
static int count_set_adj_bits(AdjWord w) {
- int j, total;
- for (j=0, total=0; j<m; j++)
- total += !!(w & one_adj_bit(j));
+ int j, total = 0;
+ AdjWord jbit;
+ FOR_BITS(j,m)
+ total += !!(w & jbit);
return total;
}
return total;
}
@@
-372,8
+379,7
@@
static int count_set_adj_bits(AdjWord w) {
static int totalfrags;
static bool maxhamweight_ok(void) {
static int totalfrags;
static bool maxhamweight_ok(void) {
- double maxminsize = (double)m / maxhamweight;
- return maxminsize > best;
+ return maxhamweight <= m_over_best;
}
static bool preconsider_ok(int nwords, bool doprint) {
}
static bool preconsider_ok(int nwords, bool doprint) {
@@
-384,14
+390,13
@@
static bool preconsider_ok(int nwords, bool doprint) {
bool had_max = 0;
for (i=0, totalfrags=0; i<nwords; i++) {
int frags = count_set_adj_bits(adjmatrix[i]);
bool had_max = 0;
for (i=0, totalfrags=0; i<nwords; i++) {
int frags = count_set_adj_bits(adjmatrix[i]);
- had_max += (frags >= maxhamweight);
- totalfrags += frags;
PRINTF("%"PRADJ" ", adjmatrix[i]);
PRINTF("%"PRADJ" ", adjmatrix[i]);
- double maxminsize = (double)m / frags;
- if (maxminsize <= best) {
+ if (frags > m_over_best) {
PRINTF(" too fine");
goto out;
}
PRINTF(" too fine");
goto out;
}
+ had_max += (frags >= maxhamweight);
+ totalfrags += frags;
}
if (!had_max) {
/* Skip this candidate as its max hamming weight is lower than
}
if (!had_max) {
/* Skip this candidate as its max hamming weight is lower than
@@
-411,6
+416,7
@@
static void optimise(bool doprint) {
/* Consider the best answer (if any) for a given adjacency matrix */
glp_prob *prob = 0;
int i, j;
/* Consider the best answer (if any) for a given adjacency matrix */
glp_prob *prob = 0;
int i, j;
+ AdjWord jbit;
/*
* Up to a certain point, optimise() can be restarted. We use this
/*
* Up to a certain point, optimise() can be restarted. We use this
@@
-496,8
+502,8
@@
static void optimise(bool doprint) {
glp_set_obj_coef(prob, X_minimum, 1);
for (i=0; i<n; i++) {
glp_set_obj_coef(prob, X_minimum, 1);
for (i=0; i<n; i++) {
- for (j=0
; j<m; j++
) {
- if (!(adjmatrix[i] &
one_adj_bit(j)
))
+ for (j=0
, jbit=1; j<m; j++, jbit<<=1
) {
+ if (!(adjmatrix[i] &
jbit
))
continue;
/* x_total_i += x_minimum */
/* x_total_j += x_minimum */
continue;
/* x_total_i += x_minimum */
/* x_total_j += x_minimum */
@@
-598,6
+604,9
@@
static void optimise(bool doprint) {
}
static void iterate_recurse(int i, AdjWord min) {
}
static void iterate_recurse(int i, AdjWord min) {
+ int j;
+ AdjWord jbit;
+
if (i >= n) {
printcounter++;
optimise(!(printcounter & 0xfff));
if (i >= n) {
printcounter++;
optimise(!(printcounter & 0xfff));
@@
-615,8
+624,8
@@
static void iterate_recurse(int i, AdjWord min) {
if (i == 0 && (adjmatrix[i] & (1+adjmatrix[i])))
goto again;
if (i == 0 && (adjmatrix[i] & (1+adjmatrix[i])))
goto again;
-
for (int j = 0; j < m; j++
)
- if (adjmatrix[i] &
one_adj_bit(j)
)
+
FOR_BITS(j,m
)
+ if (adjmatrix[i] &
jbit
)
weight[j]++;
for (int j = 0; j < m; j++)
if (weight[j] >= n_over_best)
weight[j]++;
for (int j = 0; j < m; j++)
if (weight[j] >= n_over_best)
@@
-625,8
+634,8
@@
static void iterate_recurse(int i, AdjWord min) {
iterate_recurse(i+1, adjmatrix[i]);
takeout:
iterate_recurse(i+1, adjmatrix[i]);
takeout:
-
for (int j = 0; j < m; j++
)
- if (adjmatrix[i] &
one_adj_bit(j)
)
+
FOR_BITS(j,m
)
+ if (adjmatrix[i] &
jbit
)
weight[j]--;
again:
weight[j]--;
again: