Created
December 27, 2018 19:10
-
-
Save AbuCarlo/02e7640c0fa629c5c72e0f031f4c4b48 to your computer and use it in GitHub Desktop.
This Groovy script can be used to generate stress tests for the final week's assignment for the Coursera course `Basic Algorithms`
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def UPPER_BOUND = 1000001 // SetWithRangeSums.MODULUS | |
def PROBLEM_SIZE = 100000 | |
def javaSet = new SetWithRangeSums.SummingTreeSet() | |
def avlSet = new SetWithRangeSums.PrincetonAvlTree() | |
/* The inputs from the assignment are about 45 % insertion, 45 % queries, 5 % deletion, | |
and 5% range sums. | |
*/ | |
println(PROBLEM_SIZE) | |
def random = new Random() | |
for (int i = 0; i < PROBLEM_SIZE; ++i) { | |
def operation = random.nextDouble() | |
if (operation < 0.35) { | |
int value = random.nextInt(UPPER_BOUND) | |
println "+ $value" | |
javaSet.add(value) | |
avlSet.add(value) | |
} else if (operation < 0.70) { | |
int value = random.nextInt(UPPER_BOUND) | |
println "? $value" | |
boolean javaContains = javaSet.contains(value) | |
boolean avlContains = avlSet.contains(value) | |
assert javaContains == avlContains | |
} else if (operation < 0.85) { | |
int value = random.nextInt(UPPER_BOUND) | |
println "- $value" | |
javaSet.remove(value) | |
avlSet.remove(value) | |
} else { | |
int from = random.nextInt(UPPER_BOUND) | |
int to = random.nextInt(UPPER_BOUND) | |
println "s $from $to" | |
long javaSum = javaSet.rangeSum(from, to) | |
long avlSum = avlSet.rangeSum(from, to) | |
assert javaSum == avlSum | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment