73 lines
2.2 KiB
Python
73 lines
2.2 KiB
Python
"""
|
|
rawtherapee-0002: IPTC panel delKeyWord/delSuppCategory O(K*S) linear selection scan.
|
|
|
|
Simulates the defect (std::find over vector per item) vs fix (unordered_set lookup)
|
|
and asserts speedup > 3x at K=1000, S=500.
|
|
"""
|
|
import time
|
|
import sys
|
|
|
|
def del_keyword_defective(all_items, selection):
|
|
"""O(K*S): std::find(selection.begin(), selection.end(), i) per item."""
|
|
selection_list = list(selection)
|
|
keep = []
|
|
for i in range(len(all_items)):
|
|
if i not in selection_list: # Python 'in' on list = O(S)
|
|
keep.append(all_items[i])
|
|
return keep
|
|
|
|
|
|
def del_keyword_fixed(all_items, selection):
|
|
"""O(K): unordered_set lookup per item."""
|
|
selection_set = set(selection)
|
|
keep = []
|
|
for i in range(len(all_items)):
|
|
if i not in selection_set: # Python 'in' on set = O(1)
|
|
keep.append(all_items[i])
|
|
return keep
|
|
|
|
|
|
def benchmark(label, fn, all_items, selection, reps=5):
|
|
best = float('inf')
|
|
for _ in range(reps):
|
|
t0 = time.perf_counter()
|
|
result = fn(all_items, selection)
|
|
t1 = time.perf_counter()
|
|
best = min(best, t1 - t0)
|
|
return best, result
|
|
|
|
|
|
def run(K, S):
|
|
all_items = [f"keyword_{i}" for i in range(K)]
|
|
selection = list(range(0, S)) # first S indices selected
|
|
|
|
t_defect, r1 = benchmark("defective", del_keyword_defective, all_items, selection)
|
|
t_fixed, r2 = benchmark("fixed", del_keyword_fixed, all_items, selection)
|
|
|
|
assert r1 == r2, "Results differ!"
|
|
ratio = t_defect / t_fixed if t_fixed > 0 else float('inf')
|
|
return t_defect, t_fixed, ratio
|
|
|
|
|
|
def main():
|
|
print("rawtherapee-0002: IPTC panel delKeyWord/delSuppCategory selection scan")
|
|
print(f"{'K':>6} {'S':>6} {'defect(ms)':>12} {'fixed(ms)':>10} {'ratio':>8} result")
|
|
|
|
PASS = True
|
|
for K, S in [(100, 50), (1000, 500)]:
|
|
t_d, t_f, ratio = run(K, S)
|
|
status = "PASS" if ratio >= 3.0 else "FAIL"
|
|
if status == "FAIL":
|
|
PASS = False
|
|
print(f"{K:>6} {S:>6} {t_d*1000:>12.3f} {t_f*1000:>10.3f} {ratio:>8.1f}x {status}")
|
|
|
|
if PASS:
|
|
print("\nPASS")
|
|
sys.exit(0)
|
|
else:
|
|
print("\nFAIL")
|
|
sys.exit(1)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|