performance - 最有效地在 TreeMap 中找到第 N 个键

Question

我有一个自动对键进行排序的 Scala TreeMap。我想知道的是，是否有比以下示例更高效的方法来查找 map 中的第 N 个键:

treeMap.take(N).lastKey

谢谢，布鲁斯

编辑:
我使用以下代码创建了一个小测试:

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's 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
  }
}

看来大牛的建议确实更好

结果

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

Answer 1

不可变的 SortedSet 和 SortedMap 最近进行了大修。 2.10 版将进行多项改进，包括改进查找第一个和最后一个元素以及take、drop、slice。

现在，您提出的解决方案 take(N).lastKey 并不是特别有效。相反，我会执行 iterator.drop(n - 1).next._1。它也不是特别有效，我会在选择一个解决方案之前对这两个解决方案进行基准测试。