Last active
June 3, 2024 05:00
-
-
Save coderodde/ff712497de1b384559d5d0fc7120ace9 to your computer and use it in GitHub Desktop.
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
package fi.helsinki.cs.rodionef; | |
import com.github.coderodde.util.SkipListMap; | |
import java.util.Comparator; | |
import java.util.HashMap; | |
import java.util.Map; | |
import java.util.Random; | |
import java.util.TreeMap; | |
import java.util.concurrent.ConcurrentSkipListMap; | |
public class SkipListComparison { | |
private static final String INSERT = "insert"; | |
private static final String CONTAINS = "contains"; | |
private static final String DELETE = "delete"; | |
private static final Comparator<Integer> CMP = new Comparator<>() { | |
@Override | |
public int compare(Integer o1, Integer o2) { | |
return o1.compareTo(02); | |
} | |
}; | |
private static final Map<String, Long> DM_SKIP_LIST = new HashMap<>(); | |
private static final Map<String, Long> DM_C_SKIP_LIST = new HashMap<>(); | |
private static final Map<String, Long> DM_TREE_MAP = new HashMap<>(); | |
private static final Map<Integer, Boolean> treeMap = new TreeMap<>(CMP); | |
private static final Map<Integer, Boolean> concurrentSkipListMap = | |
new ConcurrentSkipListMap<>(CMP); | |
private static final Map<Integer, Boolean> skipListMap = | |
new SkipListMap<>(CMP); | |
private static final int ITERATIONS = 10; | |
static { | |
DM_SKIP_LIST.put(INSERT, 0L); | |
DM_SKIP_LIST.put(DELETE, 0L); | |
DM_SKIP_LIST.put(CONTAINS, 0L); | |
DM_C_SKIP_LIST.put(INSERT, 0L); | |
DM_C_SKIP_LIST.put(DELETE, 0L); | |
DM_C_SKIP_LIST.put(CONTAINS, 0L); | |
DM_TREE_MAP.put(INSERT, 0L); | |
DM_TREE_MAP.put(DELETE, 0L); | |
DM_TREE_MAP.put(CONTAINS, 0L); | |
} | |
public static void main(String[] args) { | |
System.out.println("Warming up..."); | |
warmup(); | |
System.out.println("Warming up done!"); | |
System.out.printf("Doing %d benchmark iterations.\n", ITERATIONS); | |
final int totalIterations = 10; | |
for (int iter = 0; iter < totalIterations; iter++) { | |
System.out.printf("Iteration: %d.\n", iter); | |
Integer[] input = getInputIntegerArray(); | |
long ta = System.currentTimeMillis(); | |
for (Integer i : input) { | |
treeMap.put(i, Boolean.TRUE); | |
} | |
long tb = System.currentTimeMillis(); | |
DM_TREE_MAP.put(INSERT, tb - ta); | |
ta = System.currentTimeMillis(); | |
for (Integer i : input) { | |
concurrentSkipListMap.put(i, Boolean.TRUE); | |
} | |
tb = System.currentTimeMillis(); | |
DM_C_SKIP_LIST.put(INSERT, tb - ta); | |
ta = System.currentTimeMillis(); | |
for (Integer i : input) { | |
skipListMap.put(i, Boolean.TRUE); | |
} | |
tb = System.currentTimeMillis(); | |
DM_SKIP_LIST.put(INSERT, tb - ta); | |
ta = System.currentTimeMillis(); | |
for (int i = 0; i < input.length; i++) { | |
treeMap.containsKey(input[i]); | |
} | |
tb = System.currentTimeMillis(); | |
DM_TREE_MAP.put(CONTAINS, DM_TREE_MAP.get(CONTAINS) + tb - ta); | |
ta = System.currentTimeMillis(); | |
for (int i = 0; i < input.length; i++) { | |
concurrentSkipListMap.containsKey(input[i]); | |
} | |
tb = System.currentTimeMillis(); | |
DM_C_SKIP_LIST.put(CONTAINS, DM_C_SKIP_LIST.get(CONTAINS) + tb - ta); | |
ta = System.currentTimeMillis(); | |
for (int i = 0; i < input.length; i++) { | |
skipListMap.containsKey(input[i]); | |
} | |
tb = System.currentTimeMillis(); | |
DM_SKIP_LIST.put(CONTAINS, DM_SKIP_LIST.get(CONTAINS) + tb - ta); | |
Random random = new Random(10); | |
ta = System.currentTimeMillis(); | |
for (int i = 0; i < 1_000_000; i++) { | |
treeMap.remove(random.nextInt()); | |
} | |
for (int i = 0; i < input.length; i++) { | |
treeMap.remove(input[i]); | |
} | |
tb = System.currentTimeMillis(); | |
DM_TREE_MAP.put(DELETE, DM_TREE_MAP.get(DELETE) + tb - ta); | |
ta = System.currentTimeMillis(); | |
for (int i = 0; i < 1_000_000; i++) { | |
concurrentSkipListMap.remove(random.nextInt()); | |
} | |
for (int i = 0; i < input.length; i++) { | |
concurrentSkipListMap.remove(input[i]); | |
} | |
tb = System.currentTimeMillis(); | |
DM_C_SKIP_LIST.put(DELETE, DM_C_SKIP_LIST.get(DELETE) + tb - ta); | |
ta = System.currentTimeMillis(); | |
for (int i = 0; i < 1_000_000; i++) { | |
skipListMap.remove(random.nextInt()); | |
} | |
for (int i = 0; i < input.length; i++) { | |
skipListMap.remove(input[i]); | |
} | |
tb = System.currentTimeMillis(); | |
DM_SKIP_LIST.put(DELETE, DM_SKIP_LIST.get(DELETE) + tb - ta); | |
} | |
printMapStatistics(DM_SKIP_LIST); | |
printMapStatistics(DM_C_SKIP_LIST); | |
printMapStatistics(DM_TREE_MAP); | |
printTotalStatistics(); | |
} | |
private static String getDataStructureName(Map<String, Long> m) { | |
if (m == DM_TREE_MAP) { | |
return "TreeMap"; | |
} | |
if (m == DM_C_SKIP_LIST) { | |
return "ConcurrentSkipListMap"; | |
} | |
if (m == DM_SKIP_LIST) { | |
return "SkipListMap"; | |
} | |
throw new IllegalStateException(); | |
} | |
private static long getAverageDuration(Map<String, Long> map, | |
String operationName, | |
int iterations) { | |
return map.get(operationName) / iterations; | |
} | |
private static void printMapStatistics(Map<String, Long> map) { | |
System.out.printf("%s.%s: %d milliseconds.\n", | |
getDataStructureName(map), | |
INSERT, | |
getAverageDuration(map, INSERT, ITERATIONS)); | |
System.out.printf("%s.%s: %d milliseconds.\n", | |
getDataStructureName(map), | |
CONTAINS, | |
getAverageDuration(map, CONTAINS, ITERATIONS)); | |
System.out.printf("%s.%s: %d milliseconds.\n", | |
getDataStructureName(map), | |
DELETE, | |
getAverageDuration(map, DELETE, ITERATIONS)); | |
} | |
private static long getTotalDuration(Map<String, Long> m) { | |
long duration = getAverageDuration(m, CONTAINS, ITERATIONS); | |
duration += getAverageDuration(m, INSERT, ITERATIONS); | |
duration += getAverageDuration(m, DELETE, ITERATIONS); | |
return duration; | |
} | |
private static void printTotalStatistics() { | |
System.out.printf("TreeMap: %d milliseconds.\n", | |
getTotalDuration(DM_TREE_MAP)); | |
System.out.printf("ConcurrentSkipListMap: %d milliseconds.\n", | |
getTotalDuration(DM_C_SKIP_LIST)); | |
System.out.printf("SkipListMap: %d milliseconds.\n", | |
getTotalDuration(DM_SKIP_LIST)); | |
} | |
private static Integer[] getInputIntegerArray() { | |
Random random = new Random(1); | |
Integer[] input = new Integer[1_000_000]; | |
for (int i = 0; i < input.length; i++) { | |
input[i] = random.nextInt(1_000_000); | |
} | |
return input; | |
} | |
private static void warmup() { | |
Random random = new Random(100L); | |
Integer[] input = getInputIntegerArray(); | |
for (Integer i : input) { | |
treeMap.put(i, Boolean.TRUE); | |
} | |
for (Integer i : input) { | |
concurrentSkipListMap.put(i, Boolean.TRUE); | |
} | |
for (Integer i : input) { | |
skipListMap.put(i, Boolean.TRUE); | |
} | |
for (int i = 0; i < input.length; i++) { | |
treeMap.containsKey(input[i]); | |
} | |
for (int i = 0; i < input.length; i++) { | |
concurrentSkipListMap.containsKey(input[i]); | |
} | |
for (int i = 0; i < input.length; i++) { | |
skipListMap.containsKey(input[i]); | |
} | |
for (int i = 0; i < 1_000_000; i++) { | |
treeMap.remove(random.nextInt()); | |
} | |
for (int i = 0; i < input.length; i++) { | |
treeMap.remove(input[i]); | |
} | |
for (int i = 0; i < 1_000_000; i++) { | |
concurrentSkipListMap.remove(random.nextInt()); | |
} | |
for (int i = 0; i < input.length; i++) { | |
concurrentSkipListMap.remove(input[i]); | |
} | |
for (int i = 0; i < 1_000_000; i++) { | |
skipListMap.remove(random.nextInt()); | |
} | |
for (int i = 0; i < input.length; i++) { | |
skipListMap.remove(input[i]); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment