Your best bet is to find the Nth key in TreeMap
I have a Scala TreeMap that sorts the keys automatically. I would like to know if there is a more efficient way to find the Nth key in a map than the following example:
treeMap.take(N).lastKey
Thanks Bruce
EDIT:
I created a small test using the following code:
class Test {
var treeMap = new scala.collection.immutable.TreeMap[Double,String]()
val numberOfEntries = 1000
(0 until numberOfEntries) map { i => {treeMap += {i.toDouble -> i.toString}}}
val iterations = 2000
var N = 1
while(N < numberOfEntries) {
// my original version
var i = 0
val start1 = System.nanoTime()
while(i < iterations) {
i += 1
val v = treeMap.take(N).lastKey
}
val end1 = System.nanoTime()
val elapsed1 = end1 - start1
// Daniel suggestion
i = 0
val start2 = System.nanoTime()
while(i < iterations) {
i += 1
val v = treeMap.keysIterator.drop(N - 1).next
}
val end2 = System.nanoTime()
val elapsed2 = end2 - start2
println("N = %d, elapsed1 = %d, elapsed2 = %d".format(N,elapsed1,elapsed2))
N += 50
}
}
object Test {
def main(args:Array[String]) {
val test = new Test
}
}
Looks like Daniel's suggestion is really better
results
N = 1, elapsed1 = 956492000, elapsed2 = 700300000
N = 51, elapsed1 = 1103271000, elapsed2 = 936045000
N = 101, elapsed1 = 1286896000, elapsed2 = 1041744000
N = 151, elapsed1 = 1368854000, elapsed2 = 1199766000
N = 201, elapsed1 = 1584878000, elapsed2 = 1333284000
N = 251, elapsed1 = 1790965000, elapsed2 = 1468806000
N = 301, elapsed1 = 2052298000, elapsed2 = 1649021000
N = 351, elapsed1 = 2294625000, elapsed2 = 1819525000
N = 401, elapsed1 = 2529855000, elapsed2 = 1961699000
N = 451, elapsed1 = 2762582000, elapsed2 = 2100127000
N = 501, elapsed1 = 2977613000, elapsed2 = 2232108000
N = 551, elapsed1 = 3211812000, elapsed2 = 2384940000
N = 601, elapsed1 = 3437116000, elapsed2 = 2539431000
N = 651, elapsed1 = 3652749000, elapsed2 = 2650910000
N = 701, elapsed1 = 3900431000, elapsed2 = 2807085000
N = 751, elapsed1 = 4123141000, elapsed2 = 2934904000
N = 801, elapsed1 = 4337909000, elapsed2 = 3060158000
N = 851, elapsed1 = 4554490000, elapsed2 = 3188378000
N = 901, elapsed1 = 4768488000, elapsed2 = 3306528000
N = 951, elapsed1 = 4978839000, elapsed2 = 3413813000
source to share
Immutable SortedSet
and SortedMap
have been recently redesigned. Version 2.10 will have a number of improvements, including improvements to search for the first and last elements and take
, drop
, slice
.
The solution you are proposing is take(N).lastKey
not particularly effective at this time. I would do instead iterator.drop(n - 1).next._1
. It's not particularly efficient, and I would compare both solutions before choosing one.
source to share
Scala and TreeMaps aside, I'm not sure if there is a better O (n) algorithm for finding the Nth element in a tree. For any node M, to determine how many children of M you need to descend into each child. Therefore, to count the first N nodes, you need to go down to the first N leaves.
source to share