Нахождение N-го ключа в TreeMap наиболее эффективно - PullRequest
Новая
       13

Нахождение N-го ключа в TreeMap наиболее эффективно

3 голосов
/ 12 марта 2012

У меня есть Scala TreeMap, которая автоматически сортирует ключи.Я хотел бы знать, есть ли более эффективный способ найти 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

Ответы [ 2 ]

3 голосов
/ 12 марта 2012

Неизменные SortedSet и SortedMap пошли недавно капитальный ремонт. Версия 2.10 будет иметь ряд улучшений, включая улучшения поиска первого и последнего элементов и take, drop, slice.

В данный момент предлагаемое вами решение take(N).lastKey не особенно эффективно. Вместо этого я бы сделал iterator.drop(n - 1).next._1. Это также не особенно эффективно, и я бы оценил оба решения, прежде чем выбрать одно.

3 голосов
/ 12 марта 2012

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

...