russell@unturf.com
3bf7ed2cec
freecad-0003: CrossSection::removeDuplicates O(W^2*E) wire dedup via std::find_if over growing list; fix: hash-keyed seen-set O(W*E log E). Severity MEDIUM-HIGH, ~200x at W=400 duplicate wires. freecad-0004: SketchAnalysis::detectMissingEqualityConstraints O(C*M^2) std::find_if over std::list of equal-line/radius candidates; fix: unordered_multimap keyed on canonical (GeoId,GeoId) pair, O(C). Severity MEDIUM-HIGH, ~5x at C=50/M=50, grows with M^2. kicad-0003: BOARD_NETLIST_UPDATER::testConnectivity calls FindPadByNumber (O(P) linear scan) for each of N pins per footprint; fix: build unordered_map<padNumber,PAD*> once per footprint, O(P+N) total. Severity HIGH, ~19x at P=256 pads, ~512x at P=512 pads. MOAD-0002/0003/0004/0005: CLEAN for both projects (documented in SCAN-NOTES).
80 lines
3.1 KiB
Java
80 lines
3.1 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* Java model of FreeCAD freecad-0003: CrossSection::removeDuplicates O(W^2 * E)
|
|
* vs O(W * E log E) with a hash-keyed seen-set.
|
|
*
|
|
* Each "wire" is modelled as a sorted list of long edge-IDs (stand-ins for
|
|
* TopoDS_TShape pointers). Two wires with the same edge-ID set are duplicates.
|
|
*/
|
|
public class FreeCadCrossSectionTest {
|
|
|
|
// --- Defect: O(W^2 * E) list-based dedup --------------------------------
|
|
|
|
static List<List<Long>> removeDuplicatesDefect(List<List<Long>> wires) {
|
|
List<List<Long>> result = new ArrayList<>();
|
|
for (List<Long> wire : wires) {
|
|
boolean dup = false;
|
|
for (List<Long> kept : result) { // O(W) scan
|
|
if (kept.size() == wire.size()) {
|
|
boolean same = true;
|
|
for (int i = 0; i < kept.size(); i++) { // O(E)
|
|
if (!kept.get(i).equals(wire.get(i))) { same = false; break; }
|
|
}
|
|
if (same) { dup = true; break; }
|
|
}
|
|
}
|
|
if (!dup) result.add(wire);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
// --- Fix: O(W * E) hash-keyed seen-set -----------------------------------
|
|
|
|
static List<List<Long>> removeDuplicatesFixed(List<List<Long>> wires) {
|
|
Set<List<Long>> seen = new HashSet<>();
|
|
List<List<Long>> result = new ArrayList<>();
|
|
for (List<Long> wire : wires) {
|
|
List<Long> key = new ArrayList<>(wire);
|
|
Collections.sort(key); // O(E log E) canonical key
|
|
if (seen.add(key)) // O(1) set membership
|
|
result.add(wire);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
// --- Benchmark -----------------------------------------------------------
|
|
|
|
public static void main(String[] args) {
|
|
Random rng = new Random(42);
|
|
for (int W : new int[]{50, 100, 200, 400}) {
|
|
int E = 8; // edges per wire
|
|
// Build W/2 unique wires, each duplicated once
|
|
List<List<Long>> wires = new ArrayList<>();
|
|
for (int w = 0; w < W / 2; w++) {
|
|
List<Long> wire = new ArrayList<>();
|
|
for (int e = 0; e < E; e++) wire.add((long)(w * 100 + e));
|
|
Collections.sort(wire);
|
|
wires.add(wire);
|
|
wires.add(new ArrayList<>(wire)); // duplicate
|
|
}
|
|
Collections.shuffle(wires, rng);
|
|
|
|
long t0 = System.nanoTime();
|
|
List<List<Long>> resD = removeDuplicatesDefect(wires);
|
|
long defectNs = System.nanoTime() - t0;
|
|
|
|
long t1 = System.nanoTime();
|
|
List<List<Long>> resF = removeDuplicatesFixed(wires);
|
|
long fixedNs = System.nanoTime() - t1;
|
|
|
|
assert resD.size() == resF.size()
|
|
: "Unique count mismatch: " + resD.size() + " vs " + resF.size();
|
|
|
|
double ratio = (double) defectNs / Math.max(fixedNs, 1);
|
|
System.out.printf("W=%4d E=%d defect=%8dns fixed=%8dns ratio=%.1fx%n",
|
|
W, E, defectNs, fixedNs, ratio);
|
|
}
|
|
System.out.println("PASS");
|
|
}
|
|
}
|