java-topology/defects/hudi/unit/HudiPruneSchemaAlgorithm.java

package unit;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * hudi-0002: InternalSchemaUtils.pruneInternalSchema ArrayList.contains O(N²) + pruneType O(F×D)
 *
 * Part A: topParentFieldIds dedup — ArrayList.contains in forEach = O(N²)
 * Part B: pruneType field membership — List.contains per field visit = O(F×D)
 *
 * Compile: javac -d . HudiPruneSchemaAlgorithm.java
 * Run:     java -ea unit.HudiPruneSchemaAlgorithm
 */
public class HudiPruneSchemaAlgorithm {

    static long compareCount = 0;

    // --- Part A: topParentFieldIds dedup ---

    // Defective: ArrayList.contains dedup — O(N²)
    static List<Integer> deduplicateParentIds_slow(List<Integer> ids) {
        List<Integer> result = new ArrayList<>();
        for (int id : ids) {
            // ArrayList.contains = linear scan
            boolean found = false;
            for (int existing : result) {
                compareCount++;
                if (existing == id) { found = true; break; }
            }
            if (!found) result.add(id);
        }
        return result;
    }

    // Fixed: LinkedHashSet — O(N), preserves insertion order
    static List<Integer> deduplicateParentIds_fast(List<Integer> ids) {
        Set<Integer> seen = new LinkedHashSet<>();
        for (int id : ids) {
            compareCount++;  // one hash op per entry
            seen.add(id);
        }
        return new ArrayList<>(seen);
    }

    // --- Part B: pruneType field membership ---

    // Defective: List<Integer> fieldIds with contains() — O(F×D)
    static int pruneType_slow(int[] schema, List<Integer> fieldIds) {
        int visited = 0;
        for (int fieldId : schema) {
            visited++;
            for (int fid : fieldIds) {
                compareCount++;
                if (fid == fieldId) break;
            }
        }
        return visited;
    }

    // Fixed: Set<Integer> fieldIds with contains() — O(F)
    static int pruneType_fast(int[] schema, Set<Integer> fieldIds) {
        int visited = 0;
        for (int fieldId : schema) {
            visited++;
            compareCount++;  // O(1) hash lookup
            fieldIds.contains(fieldId);
        }
        return visited;
    }

    static void assertEq(String label, Object expected, Object actual) {
        if (!expected.equals(actual)) {
            throw new AssertionError(label + ": expected " + expected + " but got " + actual);
        }
    }

    public static void main(String[] args) {
        int pass = 0;
        int fail = 0;

        System.out.println("hudi-0002: InternalSchemaUtils.pruneInternalSchema");

        // --- Part A tests ---

        // Test 1: correctness of dedup
        try {
            List<Integer> ids = new ArrayList<>();
            for (int i = 0; i < 5; i++) { ids.add(i % 3); }  // [0,1,2,0,1]
            compareCount = 0;
            List<Integer> slow = deduplicateParentIds_slow(ids);
            compareCount = 0;
            List<Integer> fast = deduplicateParentIds_fast(ids);
            assertEq("dedup-size", slow.size(), fast.size());
            assertEq("dedup-content", new HashSet<>(slow), new HashSet<>(fast));
            System.out.println("  PASS dedup-correctness");
            pass++;
        } catch (AssertionError e) { System.out.println("  FAIL dedup-correctness: " + e.getMessage()); fail++; }

        // Test 2: slow > fast at N=300
        {
            List<Integer> ids300 = new ArrayList<>();
            for (int i = 0; i < 300; i++) ids300.add(i % 50);  // 50 unique, many repeats

            compareCount = 0;
            deduplicateParentIds_slow(ids300);
            long slowOps = compareCount;

            compareCount = 0;
            deduplicateParentIds_fast(ids300);
            long fastOps = compareCount;

            System.out.printf("  dedup N=300(50unique): slow=%6d fast=%6d%n", slowOps, fastOps);
            if (slowOps > fastOps * 5) {
                System.out.println("  PASS slow > 5x fast for dedup"); pass++;
            } else {
                System.out.println("  FAIL expected slow > 5x fast for dedup"); fail++;
            }
        }

        // --- Part B tests ---

        // Test 3: correctness — both visit same fields
        try {
            int[] schema = new int[100];
            for (int i = 0; i < 100; i++) schema[i] = i;
            List<Integer> fieldIdList = new ArrayList<>();
            Set<Integer> fieldIdSet = new HashSet<>();
            for (int i = 0; i < 20; i++) { fieldIdList.add(i * 5); fieldIdSet.add(i * 5); }

            compareCount = 0;
            int slowVisited = pruneType_slow(schema, fieldIdList);
            compareCount = 0;
            int fastVisited = pruneType_fast(schema, fieldIdSet);
            assertEq("pruneType-visited", slowVisited, fastVisited);
            System.out.println("  PASS pruneType-correctness");
            pass++;
        } catch (AssertionError e) { System.out.println("  FAIL pruneType-correctness: " + e.getMessage()); fail++; }

        // Test 4: slow > fast at F=500, D=100
        {
            int[] schema500 = new int[500];
            for (int i = 0; i < 500; i++) schema500[i] = i;
            List<Integer> fieldIdList = new ArrayList<>();
            Set<Integer> fieldIdSet = new HashSet<>();
            for (int i = 0; i < 100; i++) { fieldIdList.add(i); fieldIdSet.add(i); }

            compareCount = 0;
            pruneType_slow(schema500, fieldIdList);
            long slowOps = compareCount;

            compareCount = 0;
            pruneType_fast(schema500, fieldIdSet);
            long fastOps = compareCount;

            System.out.printf("  pruneType F=500 D=100: slow=%6d fast=%6d%n", slowOps, fastOps);
            if (slowOps > fastOps * 10) {
                System.out.println("  PASS slow > 10x fast for pruneType"); pass++;
            } else {
                System.out.println("  FAIL expected slow > 10x fast for pruneType"); fail++;
            }
        }

        System.out.println(pass + "/" + (pass + fail) + " PASS");
        if (fail > 0) throw new RuntimeException(fail + " tests failed");
    }
}