NavigableMap против SortedMap?

Ответ 1

Лично я очень верю в использование наименее специфического интерфейса, который предоставляет вам то, что вам нужно. Это делает ваши намерения более ясными и ограничивает ваши возможные варианты.

Большинство разработчиков хотят сортировать коллекции для целей итерации и, возможно, для производительности произвольного доступа. Я видел очень мало случаев, когда мне нужен был близкий элемент.

Если вам нужна эта функциональность, продолжайте. Я думаю, что TreeMap фактически реализует NavigableMap. Но когда вам это не нужно, зачем ограничивать себя?

Ответ 2

Есть ли причина использовать SortedMap вместо NavigableMap, помимо версии JVM?

Да, я могу вспомнить один пример. Поставщик карты может обернуть ее с помощью Collections.unmodifiableSortedMap, поэтому, даже если источником был TreeMap (который реализует NavigableMap), у вас есть только ссылка на SortedMap, и вы не можете передать ее в NavigableMap.

Я пытаюсь найти значение с наибольшим ключом, так что ключ <= ссылочный ключ K0. Я не могу понять, как это сделать с помощью SortedMap

Ну, есть два случая: либо карта содержит точное соответствие для ключа, либо нет. Поэтому сначала найдите точное совпадение, и только если он не существует, тогда m.headMap(key).lastKey() даст правильный ответ.

Это будет сделано (хотя это не так эффективно, как реальный NavigableMap):

static <K, V> Map.Entry<K, V> floorEntry(final SortedMap<K, V> m, K key) {
    final SortedMap<K, V> tail; 
    if (m.containsKey(key)) {
        tail = m.tailMap(key);
    } else {
        SortedMap<K, V> head = m.headMap(key);
        if (head.isEmpty()) {
            return null;
        } else {
            tail = head.tailMap(head.lastKey());
        }
    }
    return tail.entrySet()
               .iterator()
               .next();
}

Ответ 3

При работе с целыми числами вы можете использовать x < A + 1 вместо x <= A, и все готово. Я имею в виду headMap (A + 1) и т.д., Должен выполнять эту работу. В противном случае, я бы пошел на финское решение, так как он более ясен, чем все, что я могу предложить.

Ответ 4

Я думаю, что использование итераторов лучше, чем использование headMap и tailMap, потому что оно неэффективно. Я тестировал следующий код для случаев, и он работает хорошо, а floorEntry2 в три раза быстрее, чем floorEntry1.

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;

import java.util.*;
import java.util.Map.Entry;

import org.junit.Before;
import org.junit.Test;


class TestMapUtils <K,V> {

    public TestMapUtils()
    {

    }

    public Map.Entry<K, V> floorEntry1(final SortedMap<K, V> m, K key) {
        final SortedMap<K, V> tail; 
        if (m.containsKey(key)) {
            tail = m.tailMap(key);
        } else {
            SortedMap<K, V> head = m.headMap(key);
            if (head.isEmpty()) {
                return null;
            } else {
                tail = head.tailMap(head.lastKey());
            }
        }
        return tail.entrySet()
                   .iterator()
                   .next();
    }

    public Map.Entry<K, V> floorEntry2(final NavigableMap<K, V> m, K key) {
        Iterator<Map.Entry<K,V>> i = m.entrySet().iterator();
        Entry<K,V> tailEntry = null;
        if (key==null) {
            while (i.hasNext()) {
            Entry<K,V> e = i.next();
            if (e.getKey()==null)
                return null;
            }
        } else {
            while (i.hasNext()) {
            Entry<K,V> e = i.next();
                if (key.equals(e.getKey()))
                {
                    return e;
                }
                else
                {
                    if (((Integer) e.getKey()).intValue() < (((Integer) key).intValue())) {
                        tailEntry = e;
                    }
                }
            }
        }
        return tailEntry;
    }
}

public class TestSortedMap {

    protected TestMapUtils<Integer, Integer> testMapUtils;
    private NavigableMap<Integer, Integer> sortedMap;
    @Before
    public void setUp()
    {
        testMapUtils = new TestMapUtils<Integer, Integer>();
        sortedMap = addElementsToMap();
    }

    private NavigableMap<Integer, Integer> addElementsToMap() {
        NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        map.put(10, 1);
        map.put(20, 2);
        map.put(30, 3);
        map.put(40, 4);
        map.put(50, 5);
        map.put(60, 6);
        return map;
    }

    @Test
    public void testFloorEntry()
    {

        long startTime1 = System.nanoTime();

        Entry<Integer, Integer> entry = testMapUtils.floorEntry2(sortedMap, 30);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 30);

        entry = testMapUtils.floorEntry2(sortedMap, 60);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 60);

        entry = testMapUtils.floorEntry2(sortedMap, 70);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 60);

        entry = testMapUtils.floorEntry2(sortedMap, 55);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 50);

        entry = testMapUtils.floorEntry2(sortedMap, 31);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 30);

        entry = testMapUtils.floorEntry2(sortedMap, 0);
        assertNull(entry);



        long endTime1 = System.nanoTime() - startTime1;

        long startTime2 = System.nanoTime();

        entry = testMapUtils.floorEntry1(sortedMap, 30);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 30);

        entry = testMapUtils.floorEntry1(sortedMap, 60);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 60);

        entry = testMapUtils.floorEntry1(sortedMap, 70);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 60);

        entry = testMapUtils.floorEntry1(sortedMap, 55);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 50);

        entry = testMapUtils.floorEntry1(sortedMap, 31);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 30);

        entry = testMapUtils.floorEntry1(sortedMap, 0);
        assertNull(entry);

        long endTime2 = System.nanoTime() - startTime2;

        if ( endTime2 > endTime1 )
        {
            System.out.println("First Execution is faster.. "+endTime1+", "+endTime2);
        } else if ( endTime1 > endTime2 ) {

            System.out.println("Second Execution is faster.. "+endTime1+", "+endTime2);
        } else {
            System.out.println("Execution times are same");
        }

    }

}

Ответ 5

Есть ли какая-либо причина использовать SortedMap вместо NavigableMap, кроме версии JVM?

Да, если вам нужно вернуть неизменяемую карту, и вы не используете Google Guava.

NavigableMap предназначен для замены SortedMap. NavigableMap добавляет методы к интерфейсу SortedMap, которые необходимы довольно часто, их легко добавить разработчику Map, но их неудобно писать с точки зрения существующих методов SortedMap. Возврат SortedMap вместо NavigableMap приведет к ненужной работе вызывающих программ.

К сожалению, Collections.unmodifiableNavigableMap не был предоставлен. IMO, это, вероятно, было упущением, но оно не было исправлено в JDK 1.7, так что, возможно, у кого-то была причина пропустить это. Я предлагаю использовать com.google.common.collect.Maps.unmodifiableNavigableMap.

Ответ 6

"[NavigableMap] предназначена для замены интерфейса SortedMap." http://download.oracle.com/javase/6/docs/technotes/guides/collections/changes6.html

Несмотря на это, я согласен с Uri: используйте наименее специфический интерфейс, который вы можете.