structure.py

1import json2import os3from collections import defaultdict4from fractions import Fraction5from .catalog import load_catalog, _data_dir67MEASURE_KEYS = [8    "sensitivity",9    "block_sensitivity",10    "certificate",11    "certificate_0",12    "certificate_1",13    "decision_tree_depth",14    "real_degree",15    "dnf_size",16    "cnf_size",17]1819def _fp_tuple(row):20    return tuple(row["fill_fingerprint"])2122def invariant_keys(row):23    genus = row["genus"]24    gf2 = row["gf2_degree"]25    pop = row["popcount"]26    fp = _fp_tuple(row)27    return {28        "genus": (genus,),29        "gf2_degree": (gf2,),30        "popcount": (pop,),31        "genus+gf2": (genus, gf2),32        "genus+pop": (genus, pop),33        "gf2+pop": (gf2, pop),34        "genus+gf2+pop": (genus, gf2, pop),35        "fingerprint": fp,36        "genus+fingerprint": (genus,) + fp,37    }3839KEY_ORDER = [40    "genus", "gf2_degree", "popcount",41    "genus+gf2", "genus+pop", "gf2+pop", "genus+gf2+pop",42    "fingerprint", "genus+fingerprint",43]4445def determines(rows, key_name, measure):46    groups = defaultdict(set)47    for row in rows:48        k = invariant_keys(row)[key_name]49        groups[k].add(row[measure])50    bad = {k: sorted(v) for k, v in groups.items() if len(v) > 1}51    return (len(bad) == 0), bad5253def coarsest_determiner(rows, measure):54    for key_name in KEY_ORDER:55        ok, _ = determines(rows, key_name, measure)56        if ok:57            return key_name58    return None5960def determination_report(rows):61    report = {}62    for measure in MEASURE_KEYS:63        det = coarsest_determiner(rows, measure)64        report[measure] = det65    return report6667def collisions(rows, key_name, measure):68    _, bad = determines(rows, key_name, measure)69    out = []70    members = defaultdict(list)71    for row in rows:72        k = invariant_keys(row)[key_name]73        members[k].append(row["name"])74    for k, vals in bad.items():75        out.append((k, vals, members[k]))76    return out7778def measure_gap(rows, big, small):79    out = []80    for row in rows:81        a = row[big]82        b = row[small]83        out.append((row["name"], a, b, a - b))84    return out8586def extremal_on(rows, measure_a, measure_b, ratio=False):87    best = None88    holders = []89    for row in rows:90        a = max(row[measure_a], 0)91        b = max(row[measure_b], 0)92        if ratio:93            if b == 0:94                continue95            val = Fraction(a, b)96        else:97            val = a - b98        if best is None or val > best:99            best = val100            holders = [row["name"]]101        elif val == best:102            holders.append(row["name"])103    return best, holders104105if __name__ == "__main__":106    here = _data_dir()107    for D in (3, 4):108        rows = load_catalog(D, here)109        print(f"=== D={D} ({len(rows)} designs) ===")110        rep = determination_report(rows)111        for measure, det in rep.items():112            print(f"  {measure:22s} determined by: {det}")113        print()