92 lines
3.4 KiB
Java
92 lines
3.4 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* Unit test for DuckStation duckstation-0001:
|
|
* Cheats::GetCodeListUniquePrefixes uses std::find on a growing std::vector
|
|
* inside a loop over all cheat codes, giving O(N^2) behaviour.
|
|
*
|
|
* PS1 cheat databases (GameShark, CodeBreaker) contain 100s to 1000s of codes
|
|
* per game. This function is called every time our cheat settings UI tab opens.
|
|
*
|
|
* Defect file: src/core/cheats.cpp line 614
|
|
* Pattern: for each code, std::find(ret.begin(), ret.end(), prefix)
|
|
* Fix: insert into unordered_set for O(1) membership test per code.
|
|
*/
|
|
public class CheatsUniquePrefixesTest {
|
|
|
|
// --- Defective: O(N^2) linear scan dedup ---
|
|
static List<String> getUniquePrefixesDefective(List<String> codes) {
|
|
List<String> ret = new ArrayList<>();
|
|
for (String code : codes) {
|
|
// Simulate GetNameParentPart: prefix is everything before '/'
|
|
int slash = code.lastIndexOf('/');
|
|
String prefix = (slash >= 0) ? code.substring(0, slash) : "";
|
|
if (prefix.isEmpty()) continue;
|
|
if (!ret.contains(prefix)) { // O(N) scan per code
|
|
ret.add(prefix);
|
|
}
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
// --- Fixed: O(N) with hash set ---
|
|
static List<String> getUniquePrefixesFixed(List<String> codes) {
|
|
List<String> ret = new ArrayList<>();
|
|
Set<String> seen = new HashSet<>();
|
|
for (String code : codes) {
|
|
int slash = code.lastIndexOf('/');
|
|
String prefix = (slash >= 0) ? code.substring(0, slash) : "";
|
|
if (prefix.isEmpty()) continue;
|
|
if (seen.add(prefix)) {
|
|
ret.add(prefix);
|
|
}
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
int NUM_GROUPS = 200;
|
|
int CODES_PER_GROUP = 5;
|
|
int N = NUM_GROUPS * CODES_PER_GROUP;
|
|
|
|
// Build test data: codes named "Group_N/Code_M"
|
|
List<String> codes = new ArrayList<>(N);
|
|
for (int g = 0; g < NUM_GROUPS; g++) {
|
|
for (int c = 0; c < CODES_PER_GROUP; c++) {
|
|
codes.add("Group_" + g + "/Code_" + c);
|
|
}
|
|
}
|
|
|
|
// Correctness check
|
|
List<String> defResult = getUniquePrefixesDefective(codes);
|
|
List<String> fixResult = getUniquePrefixesFixed(codes);
|
|
Collections.sort(defResult);
|
|
Collections.sort(fixResult);
|
|
assert defResult.equals(fixResult)
|
|
: "Prefix list mismatch: defective=" + defResult.size() + " fixed=" + fixResult.size();
|
|
assert fixResult.size() == NUM_GROUPS : "Expected " + NUM_GROUPS + " unique prefixes";
|
|
|
|
// Warm up
|
|
for (int i = 0; i < 100; i++) {
|
|
getUniquePrefixesDefective(codes);
|
|
getUniquePrefixesFixed(codes);
|
|
}
|
|
|
|
// Benchmark
|
|
int ITER = 1000;
|
|
long t0 = System.nanoTime();
|
|
for (int i = 0; i < ITER; i++) getUniquePrefixesDefective(codes);
|
|
long defectNs = System.nanoTime() - t0;
|
|
|
|
t0 = System.nanoTime();
|
|
for (int i = 0; i < ITER; i++) getUniquePrefixesFixed(codes);
|
|
long fixedNs = System.nanoTime() - t0;
|
|
|
|
double ratio = (double) defectNs / fixedNs;
|
|
System.out.printf("GetCodeListUniquePrefixes N=%d codes (%d groups) defect=%.1fms fixed=%.1fms ratio=%.1fx%n",
|
|
N, NUM_GROUPS, defectNs / 1e6, fixedNs / 1e6, ratio);
|
|
|
|
assert ratio > 2.0 : "Expected >2x speedup, got " + ratio;
|
|
System.out.println("PASS");
|
|
}
|
|
}
|