Gamma di valori basata sui valori chiave

Quello che stai descrivendo è una matrice sparse sulla quale desideri effettuare una selezione dell'intervallo.

Ho intenzione di iniziare con no, né una HashMap né una LinkedHashMap faranno ciò che vuoi in modo ottimale. La ragione per questo per trovare gli elementi in un intervallo HashMap è effettivamente camminare su una lista non ordinata - O (n). La LinkedHashMap potrebbe essere leggermente più ottimale di terribile se gli elementi vengono inseriti in LinkedHashMap in ordine ordinato e non ne vengono aggiunti di nuovi in seguito. Non è ancora un approccio ottimale perché invece di O (n) si ottiene O (n / m) (perché si smette di camminare nell'elenco dopo aver superato l'intervallo) che è ancora efficacemente O (n). Non è possibile eseguire una ricerca binaria nell'elenco di LinkedHashMap.

Quindi, guardiamo alcune altre strutture. Quello che sei veramente dopo è SortedMap interfaccia. Ti consente di estrarre rapidamente la mappa secondaria da una chiave all'altra con SortMappaMappa sottomarca (K da Key, K a Key) che è quello che vuoi fare. Scegli una di queste classi e avrai ciò che cerchi.

Potresti quindi ottenere i valori per ciascuno dei submap e fare un boolean retainTutti (Raccolta c) di un set all'altro.

Questa è la risposta facile. È efficacemente l'approccio elenchi di elenchi per la matrice sparsa. Potresti, comunque, codificare la matrice invece in qualche altro formato che ti offre un'opzione sub-sub più diretta. Questo non è qualcosa che fa parte della libreria standard Java e potresti trovarti a scendere questo percorso per scrivere il tuo implementazione in quel caso.

Se vedi la possibilità in futuro che questo può essere il caso, dovresti considerare di scrivere la tua interfaccia per la matrice sparsa e quindi implementare una classe dietro di essa che fa le ricerche che vuoi . In questo modo se in un secondo momento decidi che è necessario modificare l'implementazione per qualche motivo, si tratta di cambiare l'implementazione (una nuova classe che avvolge qualcos'altro) piuttosto che modificare tutto il codice per gestire una struttura diversa.

Mentre la tua soluzione basata su una treemap di treemaps funzionerà, ed è molto meglio della soluzione di hashmap con cui hai iniziato, potresti voler esaminare la possibilità di usare un QuadTree, che è una struttura simile a una TreeMap ma con una coppia di coordinate come chiave piuttosto che una sola. Ciò rende particolarmente selezionabile la selezione di intervalli rettangolari. Ci sono molte implementazioni disponibili per Java che possono essere trovate con un rapido google.

Dovresti dare un'occhiata in via definitiva al albero k-d . Questa struttura viene in genere utilizzata per rispondere a domande come "Esiste questo punto?", "Dov'è l'ufficio postale più vicino?" O "Chi sono gli impiegati tra i 30 e i 40 anni e pagati tra 2K e 3K?"

Quindi, il tuo problema è un tipico problema di ricerca di intervallo per il quale questa struttura è particolarmente adatta. Secondo Wikipedia, il tempo peggiore per il tuo problema, con questa struttura, è O (kN ^ (1- (1 / k)), dove k è il numero di dimensioni (2, nel tuo caso) e N è il numero dei nodi nell'albero.

Alcune limitazioni, tuttavia:

• Costruire un albero k-d richiede molto tempo, perché devi determinare il punto "mediano" per ottenere un albero equilibrato. Ciò significa che devi ordinare i tuoi punti ... Puoi decidere di non usare il punto mediano come base per i tuoi piani di scissione, ma potresti ottenere un albero sbilanciato, che sarà meno efficiente. Come compromesso, puoi scegliere il punto mediano tra un sottoinsieme del tuo punto, per evitare una selezione pessima.
• Se devi aggiungere o rimuovere punti, può essere fatto in tempo utile. Ma è probabile che queste operazioni squilibrino l'albero, quindi le tue prestazioni diminuiranno nel tempo, a meno che tu non spenda altro tempo per riequilibrarlo. Se devi aggiungere / rimuovere punti frequentemente e se le tue dimensioni hanno dimensioni fisse, potresti considerare quadtrees in alternativa.

Non l'ho mai usato, ma a quanto pare Java ML ha una decente implementazione di alberi k-d.

Invece di due hash di coordinate, puoi usare un elenco di Point2D e scorrere attraverso di esso. E estrai una lista filtrata di quanto puoi In questo modo, viene eseguito un solo ciclo.

    int distance = 200;
    Point2D.Double refPoint = new Point2D.Double(0,0);

    List<Point2D.Double> pointstoSearch = new ArrayList<Point2D.Double>();
    List<Point2D.Double> filtered = new ArrayList<Point2D.Double>();
    List<Point2D.Double> POIs = new ArrayList<Point2D.Double>();
    POIs.add(new Point2D.Double(99d,100d));
    POIs.add(new Point2D.Double(101.8, 202.3));        
    POIs.add(new Point2D.Double(-50, -98));      

    //filtering
    for (Point2D.Double point : POIs) {
       if (point.distance(refPoint)<= distance) filtered.add(point);
    }

    //now search only the matching points//filtering
    for (Point2D.Double poi : filtered) {
        for (Point2D.Double point : pointstoSearch) {
            if (poi.equals(point)) //match
        }
    }

Per la massima efficienza, e se la mappa delle coordinate cercate (POI nel mio campione) è ~ costante, dovresti considerare l'uso di quadtree struttura.