-
Notifications
You must be signed in to change notification settings - Fork 0
/
TreeMapBenchmark.scala
83 lines (63 loc) · 2.1 KB
/
TreeMapBenchmark.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import scala.collection.{immutable, mutable}
import scala.util.Random
object TreeMapBenchmark extends App {
def benchmark[T](msg: String)(block: => T) = {
println(s"--- $msg ---")
val t = System.currentTimeMillis()
block
println(s"Took ${System.currentTimeMillis() - t} ms")
}
val insertOps = 1000000
val searchOps = 1000000
val deleteOps = 1000000
// some of the keys are repeated on purpose, to test inserts of existing keys and deletions of non-existing keys
val arr = Array.fill(insertOps)(Random.nextInt() -> Random.nextInt())
var imap = immutable.TreeMap[Int, Int]()
val mmap = mutable.TreeMap[Int, Int]()
val jmap = new java.util.TreeMap[Int, Int]()
println("Total unique elements to insert/get/delete: " + arr.toSet.size)
println()
println("######")
println("Insertion")
println("######")
benchmark("scala.collection.immutable.TreeMap") {
arr.foreach { kv => imap += kv }
}
benchmark("scala.collection.mutable.TreeMap") {
arr.foreach { kv => mmap += kv }
}
benchmark("java.util.TreeMap") {
arr.foreach { kv => jmap.put(kv._1, kv._2) }
}
println()
println("######")
println("Search")
println("######")
val indicesToSearch = List.fill(insertOps) {
if(Random.nextBoolean()) arr(Random.nextInt(insertOps))._1 // existing value
else Random.nextInt() // random value
}
benchmark("scala.collection.immutable.TreeMap") {
indicesToSearch.foreach { k => imap.contains(k) }
}
benchmark("scala.collection.mutable.TreeMap") {
indicesToSearch.foreach { k => mmap.contains(k) }
}
benchmark("java.util.TreeMap") {
indicesToSearch.foreach { k => jmap.containsKey(k) }
}
println()
println("######")
println("Deletion")
println("######")
val indicesToDelete = Random.shuffle(arr.toList).take(deleteOps)
benchmark("scala.collection.immutable.TreeMap") {
indicesToDelete.foreach { kv => imap -= kv._1 }
}
benchmark("scala.collection.mutable.TreeMap") {
indicesToDelete.foreach { kv => mmap -= kv._1 }
}
benchmark("java.util.TreeMap") {
indicesToDelete.foreach { kv => jmap.remove(kv._1) }
}
}