From 3d51f9529742dae7288aaeaa8d836770cc4eed0a Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Sat, 19 Mar 2022 23:42:57 +0000 Subject: [PATCH] clusters: A really bad 1D clustering program. The idea is to help with guessing expected track lengths. --- clusters | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) create mode 100755 clusters diff --git a/clusters b/clusters new file mode 100755 index 0000000..f3b20aa --- /dev/null +++ b/clusters @@ -0,0 +1,59 @@ +#! /usr/bin/python3 + +import math as M +import sys as SYS + +data = [] +for line in SYS.stdin: data.append(float(line)) +data.sort() +data = [data] + +def cover(lo, hi): + mid = (lo + hi)/2 + return mid, 1.0 - lo/mid + +def metric(vv): + print(";; measuring...") + tot = 0 + for v in vv: + spread = M.pow(v[-1] - v[0], 0.5) + print(";;\t%g .. %g -> %g" % (v[0], v[-1], spread)) + tot += spread + return tot + +def largest_gap(vv): + #print(";; finding gap...") + best, bestwd = None, None + for i, v in enumerate(vv): + lo = v[0] + for j in range(1, len(v)): + hi = v[j] + _, spread = cover(lo, hi) + #print(";;\t%d/%d: %g .. %g -> %g" % (i, j, lo, hi, spread)) + if bestwd is None or spread > bestwd: + best, bestwd = (i, j), spread + lo = hi + #if best is None: print(";; already atomized") + #else: print(";; best gap %d/%d; %g" % (best[0], best[1], bestwd)) + return best + +lastmetric = metric(data) +while True: + best = largest_gap(data) + if best is None: break + i, j = best + newdata = data[:i] + [data[i][:j], data[i][j:]] + data[i + 1:] + newmetric = metric(newdata) + if newmetric > lastmetric: break + lastmetric, data = newmetric, newdata + +def format_duration(t): + f, t = M.modf(t) + frac = ("%g" % f)[1:] + if t >= 3600: return "%d:%02d:%02d%s" % (t//3600, (t//60)%60, t%60, frac) + elif t >= 60: return "%d:%02d%s" % (t//60, t%60, frac) + else: return "%d%s s" % (t, frac) + +for v in data: + mid, spread = cover(v[0], v[-1]) + print("%s ± %g%%" % (format_duration(mid), 100.0*spread)) -- 2.11.0