russell@unturf.com
b71284e245
scribus-0004: scribus{150,170,171}format_save.cpp writes styles via
names.contains() on QList<QString> (from QMap::keys()) inside O(S) loop
— O(S²) per save. Fix: use lists.charStyles().contains() (QMap, O(log N))
directly. 6 defect sites across 3 format variants. 375x at N=1000.
darktable: 5-MOAD scan complete (darktable-0001..0005 + MOAD-0002/0003/0005
CLEAN already committed). No new defects found beyond prior scan.
SCAN-TODO: mark both targets as scanned with summary.
131 lines
4.7 KiB
Python
131 lines
4.7 KiB
Python
"""
|
|
scribus-0004: file saver names.contains O(N²) style filter on save
|
|
|
|
Simulates the defect in scribus{150,170,171}format_save.cpp where
|
|
QList<QString> names = lists.charStyleNames();
|
|
for style in styleList:
|
|
if names.contains(style.name()): // O(N) per iteration → O(N²) total
|
|
is replaced by:
|
|
for style in styleList:
|
|
if lists.charStyles().contains(style.name()): // O(log N) via QMap
|
|
"""
|
|
import time
|
|
import random
|
|
|
|
PYTHONUNBUFFERED = 1 # noqa: ensure unbuffered output reminder
|
|
|
|
# ---------------------------------------------------------------------------
|
|
# Defective: QList<QString>::contains inside for-loop → O(N²)
|
|
# Simulates: charStyleNames() returns QList (from QMap::keys()), then
|
|
# we call list.contains() for each style in styleList.
|
|
# ---------------------------------------------------------------------------
|
|
|
|
def write_styles_defective(style_names_list, used_names_set):
|
|
"""
|
|
style_names_list: all style names in sorted order (simulates styleList)
|
|
used_names_set: names that are 'used' (simulates ResourceCollection)
|
|
|
|
Defective: convert to list then do O(N) contains per iteration.
|
|
"""
|
|
ops = 0
|
|
# Simulate QList<QString> names = lists.charStyleNames()
|
|
# (QMap::keys() returns QList — O(K) copy)
|
|
names_as_list = list(used_names_set) # simulates QList<QString>
|
|
|
|
result = []
|
|
for style_name in style_names_list:
|
|
# QList::contains() — O(K) linear scan
|
|
for n in names_as_list:
|
|
ops += 1
|
|
if n == style_name:
|
|
result.append(style_name)
|
|
break
|
|
return ops, result
|
|
|
|
|
|
# ---------------------------------------------------------------------------
|
|
# Fixed: QMap<QString,QString>::contains → O(log N)
|
|
# Simulates: lists.charStyles().contains(charStyle.name())
|
|
# ---------------------------------------------------------------------------
|
|
|
|
def write_styles_fixed(style_names_list, used_names_set):
|
|
"""
|
|
Fixed: use the map directly for O(log N) lookup per style.
|
|
In Python we model QMap::contains as set membership (O(1)), which
|
|
matches the O(log N) QMap::contains behavior asymptotically vs O(N).
|
|
"""
|
|
ops = 0
|
|
result = []
|
|
for style_name in style_names_list:
|
|
# QMap::contains — O(log N) (simulated as O(1) hash set)
|
|
ops += 1
|
|
if style_name in used_names_set:
|
|
result.append(style_name)
|
|
return ops, result
|
|
|
|
|
|
# ---------------------------------------------------------------------------
|
|
# Benchmark
|
|
# ---------------------------------------------------------------------------
|
|
|
|
def benchmark(N, label):
|
|
"""
|
|
N: number of styles in the document
|
|
Half of all styles are 'used' (worst-case: used_names is also size N/2).
|
|
"""
|
|
all_styles = [f"style_{i}" for i in range(N)]
|
|
used_names = set(all_styles[:N // 2]) # first half are used
|
|
|
|
# Defective: O(N²) — list.contains inside loop
|
|
t0 = time.perf_counter()
|
|
defect_ops, defect_result = write_styles_defective(all_styles, used_names)
|
|
t1 = time.perf_counter()
|
|
defect_time = t1 - t0
|
|
|
|
# Fixed: O(N log N) → O(N) — map/set contains per style
|
|
t2 = time.perf_counter()
|
|
fixed_ops, fixed_result = write_styles_fixed(all_styles, used_names)
|
|
t3 = time.perf_counter()
|
|
fixed_time = t3 - t2
|
|
|
|
op_ratio = defect_ops / max(fixed_ops, 1)
|
|
time_ratio = defect_time / max(fixed_time, 1e-9)
|
|
|
|
# Verify correctness — both should produce same output
|
|
assert sorted(defect_result) == sorted(fixed_result), (
|
|
f"Result mismatch at N={N}: defect={len(defect_result)} fixed={len(fixed_result)}"
|
|
)
|
|
|
|
print(
|
|
f" N={N:5d}: defect_ops={defect_ops:8d} fixed_ops={fixed_ops:6d} "
|
|
f"op_ratio={op_ratio:7.1f}x "
|
|
f"defect_t={defect_time*1000:.1f}ms fixed_t={fixed_time*1000:.1f}ms "
|
|
f"time_ratio={time_ratio:.1f}x [{label}]"
|
|
)
|
|
return op_ratio
|
|
|
|
|
|
def main():
|
|
print("scribus-0004: file saver names.contains O(N²) — benchmark")
|
|
print("=" * 75)
|
|
|
|
ratio_100 = benchmark(100, "N=100")
|
|
ratio_500 = benchmark(500, "N=500")
|
|
ratio_1000 = benchmark(1000, "N=1000 (professional template)")
|
|
|
|
print()
|
|
print(f" op_ratio at N=100: {ratio_100:.1f}x")
|
|
print(f" op_ratio at N=500: {ratio_500:.1f}x")
|
|
print(f" op_ratio at N=1000: {ratio_1000:.1f}x")
|
|
|
|
# Assert meaningful speedup — O(N²) vs O(N) should show >10x at N=500
|
|
assert ratio_100 > 3, f"Expected >3x at N=100, got {ratio_100:.1f}x"
|
|
assert ratio_500 > 10, f"Expected >10x at N=500, got {ratio_500:.1f}x"
|
|
assert ratio_1000 > 20, f"Expected >20x at N=1000, got {ratio_1000:.1f}x"
|
|
|
|
print()
|
|
print("PASS — scribus-0004 confirmed: O(N²) file-save style filter speedup ✓")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|