Найти N-й ключ в TreeMap наиболее эффективно

Question

У меня есть Scala TreeMap, который автоматически сортирует ключи. То, что я хотел бы знать, если есть более производительный способ найти ключ Nth в карте, чем на следующем примере:

treeMap.take(N).lastKey 

Спасибо, Брюс

EDIT:
я создал небольшой тест, используя следующий код:

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 =8000 
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. Это также не очень эффективно, и я бы сравнил оба решения, прежде чем выбирать их.

Answer 2

Scala и Древовидные карты в сторону, я не уверен, что есть лучше, чем (п) алгоритма O для нахождения Nth элемента в дереве. Для любого узла M, чтобы определить, сколько детей M вам нужно спуститься в каждый ребенок. Поэтому для подсчета первых N узлов вам необходимо спуститься до первых N листьев.