#! /usr/bin/python3 # Last edited on 2024-09-20 16:49:36 by stolfi import sys from math import floor, sqrt, inf, nan # A /run/ is a combination of parameters {Ns,Nr,Nb,k} and the corresponding mesh and time data. # A run is represented by a python {dict} with the following keys: run_fields = ( ('i', "{:>6s}", "{:6d}", False, ), # Index of run. ('Ns', "{:>6s}", "{:6d}", False, ), # Number of meridian slices in keg. ('Nr', "{:>6s}", "{:6d}", False, ), # Number of wall face rings in keg. ('Nb', "{:>6s}", "{:6d}", False, ), # Number of inserted vertices per meridian edge in keg. ('k', "{:>6s}", "{:6d}", True, ), # Number of slicing planes to use. ('Ne', "{:>12s}", "{:12d}", True, ), # Number of edges. ('Nf', "{:>12s}", "{:12d}", False, ), # Number of faces. ('m', "{:>12s}", "{:12d}", True, ), # Number of plane-edge intersections. ('deg', "{:>6s}", "{:6.1f}", True, ), # Average face degree. ('md', "{:>14s}", "{:14d}", False, ), # Intersections {m} times avg degree {deg}. ('Tr', "{:>8s}", "{:8.3f}", False, ), # Estimated running time (seconds). ) # Elements [1] and [2] in each quadruple are the formats for printing the key in a header # and a value in a data line, respectively. Element [3] is {True} iff the field is . # relevant for {distance}. def main(): # Chooses combinations of the keg parameters {Ns,Nr,Nb} # so as to give a nice spread of the running time # regression variables {nE}, {k}, {m}, {md = m*deg} m_min_M = 0.2; m_min = m_min_M * 1000000 m_max_M = 128.0; m_max = m_max_M * 1000000 Ne_min_K = 10; Ne_min = Ne_min_K * 1000 Ne_max_K = 4000; Ne_max = Ne_max_K * 1000 Tr_min = 0.30 Tr_max = 8.00 # Generate potentially interesting combinations: runs = [] set_raw = set() # Set of indices into {runs} wrt_raw = open("out/choose_runs_raw.txt", "w") print_header(wrt_raw) k_exp_K = 1 while k_exp_K < 64: k = int(k_exp_K * 1000) m_exp_M = romu(m_min_M, 0.125) while m_exp_M <= 1.5*m_max_M: m_exp = m_exp_M * 1000000 for deg_exp in 5, 10, 20, 40, 80, 160, 320, 640, 1280: md_exp = m_exp*deg_exp Ns = romu(m_exp/k, 5) Nb = romu(deg_exp/2, 5) for Ne_exp_K in 5, 10, 20, 40, 80, 160, 320, 640, 1280, 2560: Ne_exp = Ne_exp_K * 1000 Nr = romu(Ne_exp/(Ns*Nb), 5) save_raw(Ns,Nr,Nb,k, wrt_raw, runs, Ne_min, Ne_max, m_min, m_max, Tr_min, Tr_max) m_exp_M *= 1.5 k_exp_K *= 1.5 wrt_raw.close() # Select combinations that are most varied: nraw = len(runs); set_raw = set(range(nraw)) set_kuk = set() wrt_kuk = open("out/choose_runs_kuk.txt", "w") dif_tol = 0.250 # Accept only runs that differ at least this much from other runs in some signif field. tim_tol = 0.150 # Exclude runs that differ by less than this much in {Tr}. sys.stderr.write(" dif_tol = {0:6.3f} tim_tol = {1:6.3f}\n".format(dif_tol, tim_tol)) sys.stderr.write(" {0:>3s} {1:>6s} ".format('key', 'dif')) print_header(wrt_kuk) print_header(sys.stderr) nkuk = 0 while len(set_raw) > 0: # Pop the run in {set_raw} that is most distinct from all in {set_kuk}: if len(set_kuk) == 0: irun_raw_best = set_raw.pop() irun_kuk_best = None dif_best = +inf key_best = '--' else: irun_raw_best, irun_kuk_best, dif_best, key_best = find_farthest(runs, set_raw, set_kuk) set_raw.remove(irun_raw_best) run_raw_best = runs[irun_raw_best] sys.stderr.write(" {0:>3s} {1:6.3f} ".format(key_best, dif_best)) print_dic(sys.stderr, run_raw_best) if dif_best <= dif_tol: break # Add the run to {set_kuk}: set_kuk.add(irun_raw_best) print_dic(wrt_kuk, run_raw_best) nkuk += 1 # Exclude runs with {Tr} too close to this one: exclude_close_times(runs, set_raw, run_raw_best['Tr'], tim_tol) wrt_kuk.close() # Find distinct objects: set_obj = set() sys.stderr.write(" {:>6s} {:>6s} {:>6s}\n".format('Ns','Nr','Nb')) for irun in set_kuk: run = runs[irun] obj = ( run['Ns'], run['Nr'], run['Nb'] ) if not obj in set_obj: set_obj.add(obj) sys.stderr.write(" {:6d} {:6d} {:6d}\n".format(obj[0],obj[1],obj[2])) sys.stderr.write("generated %6d raw runs\n" % nraw) sys.stderr.write("selected %6d distinct runs of %d distinct objects\n" % (nkuk, len(set_obj))) return 0 def save_raw(Ns,Nr,Nb,k, wrt_raw, runs, Ne_min, Ne_max, m_min, m_max, Tr_min, Tr_max): # Appends the run {Ns,Nr,Nb,k} to the list {runs} (and writes to {wrt_raw}) if its independent and # dependent parameters are in the stated range. debug = False Ne = Ns*(Nr*(Nb + 2) + 3) Nf = Ns*(Nr+2) deg = 2*Nb + 4 # Degree of the faces that are crossed by slicing planes. m = k*Ns md = int(m*(Nb+2)) # Estimated avg number of {.lnext} steps if there were no {.skip} links. # Estimated running time: A = 0.162e-6 B = 0.123e-6 Tr = A*Ne + B*m if debug: sys.stderr.write("trying Ns = %s Nr = %d Nb = %d k = %d\n" % (Ns,Nr,Nb,k)) if \ (Ne >= Ne_min and Ne <= Ne_max) and \ (m >= m_min and m <= m_max) and \ (Tr >= Tr_min and Tr <= Tr_max): irun = len(runs) run = { 'i': irun, 'Ns': Ns, 'Nr': Nr, 'Nb': Nb, 'k': k, 'Ne': Ne, 'Nf': Nf, 'm': m, 'deg': deg, 'md': md, 'Tr': Tr, } runs.append(run) print_dic(wrt_raw, run) print_dic(sys.stderr, run) return None def find_farthest(runs, set_raw, set_kuk): # Given two non-empty sets of indices of runs, finds the run in # {set_raw} that is furthest from the closest run in {set_kuk}. # Returns the indices of the two closest runs {run_raw} and {run_kuk} # in the two sets, as well as their distance and the key that realizes # that distance. global run_fields assert len(set_raw) > 0 assert len(set_kuk) > 0 dif_best = -inf irun_raw_best = None irun_kuk_best = None key_best = None for irun_raw in set_raw: run_raw = runs[irun_raw] dif_min, key_min, irun_kuk_min = distance_from_set(runs, run_raw, set_kuk) if dif_min > dif_best: dif_best = dif_min irun_raw_best = irun_raw irun_kuk_best = irun_kuk_min key_best = key_min return irun_raw_best, irun_kuk_best, dif_best, key_best def distance_from_set(runs, run_raw, set_kuk): # Finds the min distance from {run_raw} to the runs whose indices are in {set_kuk}, # which must be non-empty. Returns that distance, and the index of the run in # {set_kuk} that realizes it, and the key that realizes that distance. global run_fields assert len(set_kuk) > 0 dif_min = +inf key_min = None irun_kuk_min = None for irun_kuk in set_kuk: run_kuk = runs[irun_kuk] dst, key = distance(run_raw, run_kuk) if dst < dif_min: dif_min = dst key_min = key irun_kuk_min = irun_kuk return dif_min, key_min, irun_kuk_min def exclude_close_times(runs, set_raw, Tr, tim_tol): # Excludes from the set {set_raw} any runs that have 'Tr' too close to {Tr} global run_fields n0 = len(set_raw) for irun_raw in list(set_raw): run_raw = runs[irun_raw] tmid = (abs(run_raw['Tr']) + abs(Tr))/2 tdif = abs(run_raw['Tr'] - Tr)/tmid if tdif < tim_tol: set_raw.remove(irun_raw) n1 = len(set_raw) sys.stderr.write(" -- eliminated %d raw runs, %d left\n" % (n0-n1, n1)) def distance(run0, run1): # Tells how distinct {run0} and {run1} are. Specifically, it is the # max of the abs difference between corresponding relevant fields, divided by # the sum of the fields. # Returns that max dif and its key. global run_fields dif_max = -inf key_max = None for key, sfmt, vfmt, signif in run_fields: if signif: sk = (abs(run0[key]) + abs(run1[key]))/2 dk = abs((run0[key] - run1[key])/sk) if dk > dif_max: dif_max = dk key_max = key return dif_max, key_max def print_header(wrt): global run_fields wrt.write("#") for key, sfmt, vfmt, signif in run_fields: wrt.write(" ") wrt.write(sfmt.format(key)) wrt.write("\n") return None def print_dic(wrt, run): global run_fields wrt.write(" ") for key, sfmt, vfmt, signif in run_fields: wrt.write(" ") if run == None: wrt.write(sfmt.format('--')) else: wrt.write(vfmt.format(run[key])) wrt.write("\n") return None def romu(x, m): # Rounds {x} to a power of 2 times {m}. r = x/m n = 1 while n*sqrt(2) < r: n = n*2 return n*m main()