Java TreeMap получает K-й наименьший ключ

Я использую TreeMap и хочу получить K-й наименьший ключ. Я написал следующую реализацию:

public static Long kthKey(TreeMap<Long, MyObject> treeMap, int kth) {
    Long currentKey = treeMap.firstKey();
    for (int i = 1; i < kth; i++) {
        currentKey = treeMap.higherKey(currentKey);
    }
    return currentKey;
}

Это довольно эффективно с точки зрения памяти, но, возможно, не с точки зрения времени работы.

Есть ли более эффективный способ сделать это?


java performance treemap
person zvisofer    schedule 09.08.2014    source источник
comment
Вы должны посмотреть на реализацию этих методов, чтобы принять решение. Я бы, вероятно, использовал treeMap.navigableKeySet() и итератор.   -  person Andrew Logvinov    schedule 09.08.2014

Ответы (1)


arrow_upward
2
arrow_downward

Если вам разрешено использовать итератор, вы можете это сделать.

public <T> static Long kthKey(Map<T, ?> map, int kth) {
    for(T key: map.keySet())
       if(kth-- < 1) return key;
    return null;
}

Стоимость одного итератора не так высока, и если вам нужно этого избежать, я бы посоветовал посмотреть, как этот метод вызывается, и оптимизировать его, например. скажи, что у тебя есть

for (int k = 0; k < mapsize(); k++) {
    Long l = kthKey(map, k);

Вы можете вообще исключить необходимость вызова этого метода.

person Peter Lawrey    schedule 09.08.2014