196 lines
9.2 KiB
Java
196 lines
9.2 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* Unit test for opencv-0002: G-API pattern_matching O(M×(E+S)) → O(M+E+S)
|
||
*
|
||
* Simulates the classification loop in passes/pattern_matching.cpp:
|
||
* For each matched node, check if it's in patternEndOpNodes or patternStartOpNodes.
|
||
* Defective: std::find on vector inside loop over M matched nodes
|
||
* Fixed: unordered_set lookup O(1) after O(E+S) construction
|
||
*
|
||
* Compile: javac -d . GapiPatternMatchingAlgorithm.java
|
||
* Run: java -ea unit.GapiPatternMatchingAlgorithm
|
||
*/
|
||
public class GapiPatternMatchingAlgorithm {
|
||
|
||
// Simplified node handle as integer ID
|
||
static class NodeHandle {
|
||
final int id;
|
||
NodeHandle(int id) { this.id = id; }
|
||
@Override public boolean equals(Object o) { return o instanceof NodeHandle && ((NodeHandle)o).id == id; }
|
||
@Override public int hashCode() { return id; }
|
||
}
|
||
|
||
static class MatchEntry {
|
||
final NodeHandle patternNode;
|
||
final NodeHandle testNode;
|
||
MatchEntry(NodeHandle p, NodeHandle t) { patternNode = p; testNode = t; }
|
||
}
|
||
|
||
static class ClassificationResult {
|
||
final Map<NodeHandle, NodeHandle> endOps = new LinkedHashMap<>();
|
||
final Map<NodeHandle, NodeHandle> startOps = new LinkedHashMap<>();
|
||
final List<NodeHandle> internals = new ArrayList<>();
|
||
}
|
||
|
||
// ── defective implementation ──────────────────────────────────────────────
|
||
|
||
static ClassificationResult defectiveClassify(
|
||
List<MatchEntry> matchedNodes,
|
||
List<NodeHandle> patternEndOpNodes,
|
||
List<NodeHandle> patternStartOpNodes) {
|
||
ClassificationResult result = new ClassificationResult();
|
||
for (MatchEntry me : matchedNodes) {
|
||
// O(E) linear scan
|
||
boolean cond1 = false;
|
||
for (NodeHandle n : patternEndOpNodes) if (n.equals(me.patternNode)) { cond1 = true; break; }
|
||
|
||
// O(S) linear scan
|
||
boolean cond2 = false;
|
||
for (NodeHandle n : patternStartOpNodes) if (n.equals(me.patternNode)) { cond2 = true; break; }
|
||
|
||
if (cond1) result.endOps.put(me.patternNode, me.testNode);
|
||
if (cond2) result.startOps.put(me.patternNode, me.testNode);
|
||
if (!cond1 && !cond2) result.internals.add(me.testNode);
|
||
}
|
||
return result;
|
||
}
|
||
|
||
// ── fixed implementation ──────────────────────────────────────────────────
|
||
|
||
static ClassificationResult fixedClassify(
|
||
List<MatchEntry> matchedNodes,
|
||
List<NodeHandle> patternEndOpNodes,
|
||
List<NodeHandle> patternStartOpNodes) {
|
||
// O(E+S) set construction
|
||
Set<NodeHandle> endSet = new HashSet<>(patternEndOpNodes);
|
||
Set<NodeHandle> startSet = new HashSet<>(patternStartOpNodes);
|
||
|
||
ClassificationResult result = new ClassificationResult();
|
||
for (MatchEntry me : matchedNodes) {
|
||
boolean cond1 = endSet.contains(me.patternNode); // O(1)
|
||
boolean cond2 = startSet.contains(me.patternNode); // O(1)
|
||
|
||
if (cond1) result.endOps.put(me.patternNode, me.testNode);
|
||
if (cond2) result.startOps.put(me.patternNode, me.testNode);
|
||
if (!cond1 && !cond2) result.internals.add(me.testNode);
|
||
}
|
||
return result;
|
||
}
|
||
|
||
// ── equivalence check ─────────────────────────────────────────────────────
|
||
|
||
static boolean resultsEqual(ClassificationResult a, ClassificationResult b) {
|
||
return a.endOps.equals(b.endOps) &&
|
||
a.startOps.equals(b.startOps) &&
|
||
new HashSet<>(a.internals).equals(new HashSet<>(b.internals));
|
||
}
|
||
|
||
// ── tests ─────────────────────────────────────────────────────────────────
|
||
|
||
static int pass = 0, total = 0;
|
||
|
||
static void assertTrue(String name, boolean cond) {
|
||
total++;
|
||
if (cond) { pass++; System.out.println("PASS " + name); }
|
||
else System.out.println("FAIL " + name);
|
||
}
|
||
|
||
// Build M matched nodes: pattern IDs 0..M-1, each matched to test ID M+i
|
||
static List<MatchEntry> buildMatches(int M) {
|
||
List<MatchEntry> matches = new ArrayList<>();
|
||
for (int i = 0; i < M; i++)
|
||
matches.add(new MatchEntry(new NodeHandle(i), new NodeHandle(M + i)));
|
||
return matches;
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
// Test 1: empty matched nodes → everything empty
|
||
{
|
||
ClassificationResult d = defectiveClassify(Collections.emptyList(),
|
||
Collections.emptyList(), Collections.emptyList());
|
||
ClassificationResult f = fixedClassify(Collections.emptyList(),
|
||
Collections.emptyList(), Collections.emptyList());
|
||
assertTrue("empty-defective", d.endOps.isEmpty() && d.startOps.isEmpty() && d.internals.isEmpty());
|
||
assertTrue("empty-fixed", f.endOps.isEmpty() && f.startOps.isEmpty() && f.internals.isEmpty());
|
||
}
|
||
|
||
// Test 2: no end/start ops → all internal
|
||
{
|
||
List<MatchEntry> matches = buildMatches(5);
|
||
ClassificationResult d = defectiveClassify(matches, Collections.emptyList(), Collections.emptyList());
|
||
ClassificationResult f = fixedClassify(matches, Collections.emptyList(), Collections.emptyList());
|
||
assertTrue("all-internal-defective", d.internals.size() == 5 && d.endOps.isEmpty());
|
||
assertTrue("all-internal-fixed", f.internals.size() == 5 && f.endOps.isEmpty());
|
||
}
|
||
|
||
// Test 3: first and last are start/end, rest are internal
|
||
{
|
||
List<MatchEntry> matches = buildMatches(6);
|
||
List<NodeHandle> endOps = Arrays.asList(new NodeHandle(5)); // last
|
||
List<NodeHandle> startOps = Arrays.asList(new NodeHandle(0)); // first
|
||
ClassificationResult d = defectiveClassify(matches, endOps, startOps);
|
||
ClassificationResult f = fixedClassify(matches, endOps, startOps);
|
||
assertTrue("start-end-defective",
|
||
d.endOps.size() == 1 && d.startOps.size() == 1 && d.internals.size() == 4);
|
||
assertTrue("start-end-fixed",
|
||
f.endOps.size() == 1 && f.startOps.size() == 1 && f.internals.size() == 4);
|
||
assertTrue("start-end-equiv", resultsEqual(d, f));
|
||
}
|
||
|
||
// Test 4: node is both start and end (diamond pattern)
|
||
{
|
||
List<MatchEntry> matches = Arrays.asList(
|
||
new MatchEntry(new NodeHandle(0), new NodeHandle(10)));
|
||
List<NodeHandle> endOps = Arrays.asList(new NodeHandle(0));
|
||
List<NodeHandle> startOps = Arrays.asList(new NodeHandle(0));
|
||
ClassificationResult d = defectiveClassify(matches, endOps, startOps);
|
||
ClassificationResult f = fixedClassify(matches, endOps, startOps);
|
||
assertTrue("both-start-end-defective",
|
||
d.endOps.size() == 1 && d.startOps.size() == 1 && d.internals.isEmpty());
|
||
assertTrue("both-start-end-fixed",
|
||
f.endOps.size() == 1 && f.startOps.size() == 1 && f.internals.isEmpty());
|
||
}
|
||
|
||
// Test 5: larger graph — E=10 end ops, S=10 start ops, M=100 matched
|
||
{
|
||
List<MatchEntry> matches = buildMatches(100);
|
||
List<NodeHandle> endOps = new ArrayList<>();
|
||
List<NodeHandle> startOps = new ArrayList<>();
|
||
for (int i = 90; i < 100; i++) endOps.add(new NodeHandle(i));
|
||
for (int i = 0; i < 10; i++) startOps.add(new NodeHandle(i));
|
||
ClassificationResult d = defectiveClassify(matches, endOps, startOps);
|
||
ClassificationResult f = fixedClassify(matches, endOps, startOps);
|
||
assertTrue("large-graph-equiv", resultsEqual(d, f));
|
||
assertTrue("large-graph-counts",
|
||
f.endOps.size() == 10 && f.startOps.size() == 10 && f.internals.size() == 80);
|
||
}
|
||
|
||
// Test 6: performance — M=500 matched, E=100 end ops, S=100 start ops
|
||
{
|
||
List<MatchEntry> matches = buildMatches(500);
|
||
List<NodeHandle> endOps = new ArrayList<>();
|
||
List<NodeHandle> startOps = new ArrayList<>();
|
||
for (int i = 400; i < 500; i++) endOps.add(new NodeHandle(i));
|
||
for (int i = 0; i < 100; i++) startOps.add(new NodeHandle(i));
|
||
|
||
long t0 = System.nanoTime();
|
||
for (int r = 0; r < 500; r++) defectiveClassify(matches, endOps, startOps);
|
||
long tDef = System.nanoTime() - t0;
|
||
|
||
t0 = System.nanoTime();
|
||
for (int r = 0; r < 500; r++) fixedClassify(matches, endOps, startOps);
|
||
long tFix = System.nanoTime() - t0;
|
||
|
||
double ratio = (double) tDef / tFix;
|
||
System.out.printf(" Perf M=500 E=S=100: defective=%.1fms fixed=%.1fms ratio=%.1fx%n",
|
||
tDef / 1e6, tFix / 1e6, ratio);
|
||
assertTrue("perf-speedup", ratio > 2.0);
|
||
}
|
||
|
||
System.out.println(pass + "/" + total + " PASS");
|
||
assert pass == total : pass + "/" + total + " passed";
|
||
}
|
||
}
|