NavigableMap vs. SortedMap?

Question

C'è qualche motivo per utilizzare SortedMap anziché NavigableMap, oltre alla versione JVM? (NavigableMap è presente solo dal 1.6;

Sto cercando di trovare il valore con la chiave più grande tale che il tasto < = chiave di riferimento K0. Non riesco a capire come fare questo con un SortedMap (se fosse rigorosamente <, quindi chiamerei headMap() e poi lastKey() e poi get()), ma NavigableMap.floorEntry() sembra essere esattamente ciò di cui ho bisogno.

---

precisazione: tanto per fare un esempio, sto movimentazione gamme sparse di numeri di versione con diversi modelli di comportamento. Le chiavi potrebbero essere [0, 2, 5], in modo che i numeri di versione 0 e 1 vengano gestiti dal valore alla chiave # 0, i numeri di versione 2-4 vengono gestiti dal valore alla chiave # 2 e i numeri di versione> = 5 ottenere gestito dal valore alla chiave # 5.

Answer 1

Personalmente, sono un grande sostenitore nell'usare l'interfaccia meno specifica che ti fornisce ciò di cui hai bisogno. Questo rende le tue intenzioni più chiare e pone meno restrizioni sulle tue possibili implementazioni.

La maggior parte degli sviluppatori desidera raccolte ordinate per scopi di iterazione e, forse, per prestazioni di accesso casuale. Ho visto pochissimi casi in cui avevo bisogno di un elemento vicino.

Se è necessaria questa funzionalità, procedere. Penso che TreeMap implementa effettivamente NavigableMap. Ma quando non ne hai bisogno, perché limitarti?

Answer 2

C'è qualche motivo per utilizzare SortedMap invece di NavigableMap, oltre alla versione JVM?

Sì, posso pensare ad un esempio. Il fornitore della mappa potrebbe averlo impacchettato con Collections.unmodifiableSortedMap, quindi anche se la fonte era TreeMap (che implementa NavigableMap), si ha solo un riferimento a SortedMap e non è possibile trasmetterlo a NavigableMap.

Sto cercando di trovare il valore con la chiave più alta tale che il tasto < = chiave di riferimento K0. Non riesco a capire come farlo con un SortedMap

Bene ci sono due casi: o la mappa contiene una corrispondenza esatta per la chiave o non lo fa. Quindi, prima cerca una corrispondenza esatta e solo se non esiste allora m.headMap(key).lastKey() darà la risposta giusta.

---

Ciò farlo (anche se non è così efficace come un vero e proprio 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(); 
} 

Answer 3

Quando si lavora con numeri interi è possibile utilizzare x < A + 1 al posto di x < = A e hai finito. Intendo headmap (A + 1), ecc, dovrebbe fare il lavoro. Altrimenti, opterei per la soluzione di finnw poiché è più chiaro di qualsiasi cosa io possa uscire.

Answer 4

"[NavigableMap] ha lo scopo di sostituire l'interfaccia SortedMap." http://download.oracle.com/javase/6/docs/technotes/guides/collections/changes6.html

Nonostante questo, sono d'accordo con Uri:.. Utilizzare l'interfaccia meno specifica è possibile

Answer 5

Credo che l'utilizzo di iteratori è meglio che usare headMap e tailMap, perché non è efficace ho provato la seguente codice per i casi e funziona bene e floorEntry2 è tre volte più veloce rispetto 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"); 
     } 

    } 

} 

Answer 6

v'è alcuna ragione per usare SortedMap invece di NavigableMap, oltre alla versione JVM?

Sì, se è necessario restituire una mappa non modificabile e non si sta utilizzando Google Guava.

NavigableMap ha lo scopo di sostituire SortedMap. NavigableMap aggiunge metodi all'interfaccia SortedMap che sono necessari abbastanza spesso, sono facili da aggiungere a un implementatore di mappe, ma sono scomodi da scrivere in termini di metodi SortedMap esistenti. Restituire SortedMap invece di NavigableMap farà sì che chi chiama il tuo codice lavori inutilmente.

È spiacevole che Collections.unmodifiableNavigableMap non sia stato fornito. IMO era probabilmente una svista, ma non è stato corretto in JDK 1.7, quindi forse qualcuno ha avuto un motivo per lasciarlo fuori. Suggerisco di usare com.google.common.collect.Maps.unmodifiableNavigableMap.