91 lines
3.4 KiB
Java
91 lines
3.4 KiB
Java
package unit;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.LinkedHashSet;
|
|
import java.util.List;
|
|
|
|
/**
|
|
* hadoop-0001: PendingReconstructionBlocks.PendingBlockInfo.incrementReplicas()
|
|
* uses ArrayList.contains() O(n) inside a for loop — O(n*m) total.
|
|
*
|
|
* Standalone unit test — no JUnit required.
|
|
* Compile: javac -d . HadoopPendingReconstructionTest.java
|
|
* Run: java -ea unit.HadoopPendingReconstructionTest
|
|
*/
|
|
public class HadoopPendingReconstructionTest {
|
|
|
|
static long slowOps;
|
|
static long fastOps;
|
|
|
|
/**
|
|
* Simulates PendingBlockInfo.incrementReplicas() with ArrayList.
|
|
* For each newTarget, ArrayList.contains() scans all existing targets: O(n).
|
|
* Total for m newTargets with n existing: O(m*n).
|
|
*/
|
|
static List<String> slowIncrementReplicas(List<String> existingTargets, List<String> newTargets) {
|
|
slowOps = 0;
|
|
List<String> targets = new ArrayList<>(existingTargets);
|
|
for (String newTarget : newTargets) {
|
|
slowOps++; // loop entry
|
|
for (String existing : targets) { // ArrayList.contains() scan
|
|
slowOps++;
|
|
if (existing.equals(newTarget)) break;
|
|
}
|
|
if (!targets.contains(newTarget)) {
|
|
targets.add(newTarget);
|
|
}
|
|
}
|
|
return targets;
|
|
}
|
|
|
|
/**
|
|
* Patched: LinkedHashSet.add() is O(1) amortised.
|
|
* Total for m newTargets: O(m).
|
|
*/
|
|
static List<String> fastIncrementReplicas(List<String> existingTargets, List<String> newTargets) {
|
|
fastOps = 0;
|
|
LinkedHashSet<String> targets = new LinkedHashSet<>(existingTargets);
|
|
for (String newTarget : newTargets) {
|
|
fastOps++; // O(1) hash add
|
|
targets.add(newTarget);
|
|
}
|
|
return new ArrayList<>(targets);
|
|
}
|
|
|
|
static void run(int nExisting, int mNew, int expectedRatio) {
|
|
// Build existing targets (all unique)
|
|
List<String> existing = new ArrayList<>();
|
|
for (int i = 0; i < nExisting; i++) existing.add("dn-" + i);
|
|
|
|
// newTargets: half duplicates, half new
|
|
List<String> newTargets = new ArrayList<>();
|
|
for (int i = 0; i < mNew / 2; i++) newTargets.add("dn-" + i); // duplicates
|
|
for (int i = nExisting; i < nExisting + mNew / 2; i++) newTargets.add("dn-" + i); // new
|
|
|
|
List<String> slowResult = slowIncrementReplicas(existing, newTargets);
|
|
List<String> fastResult = fastIncrementReplicas(existing, newTargets);
|
|
|
|
boolean resultsMatch = slowResult.equals(fastResult);
|
|
boolean quadraticWorse = slowOps > fastOps * expectedRatio;
|
|
boolean pass = resultsMatch && quadraticWorse;
|
|
|
|
System.out.printf("n=%-4d m=%-4d slow=%6d fast=%4d ratio=%5.1fx match=%b PASS=%b%n",
|
|
nExisting, mNew, slowOps, fastOps, (double) slowOps / fastOps, resultsMatch, pass);
|
|
|
|
if (!pass) {
|
|
throw new AssertionError(
|
|
"FAIL n=" + nExisting + " m=" + mNew +
|
|
" resultsMatch=" + resultsMatch +
|
|
" slowOps=" + slowOps + " fastOps=" + fastOps +
|
|
" needed ratio>" + expectedRatio);
|
|
}
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
System.out.println("=== hadoop-0001: PendingReconstructionBlocks.incrementReplicas() O(n*m) vs O(m) ===");
|
|
run(50, 50, 5);
|
|
run(200, 100, 20);
|
|
run(500, 200, 50);
|
|
System.out.println("3/3 PASS");
|
|
}
|
|
}
|