L’esecuzione più veloce la ricerca di – raccolta che lo devo usare?

So:

  • Se avete bisogno di un rapido accesso a elementi con l’indice, ArrayList dovrebbe essere scelta.
  • Se avete bisogno di accedere rapidamente agli elementi utilizzando una chiave, utilizzare HashMap.
  • Se avete bisogno di aggiungere velocemente e la rimozione di elementi, utilizzare LinkedList (ma è molto povera, in cerca di prestazioni).

Per eseguire il più veloce di ricerca, sulla base dei dati memorizzati in un oggetto da collezione, il cui prelievo è consigliabile utilizzare?

Sotto è il mio codice:

    public void fillAndSearch(Collection<Student> collection) {
      if(collection!=null){
        for (int i=0; i<=10; i++) {
            Student student = new Student("name" + i, "id" + i);
            collection.add(student);
        }
      }
        //here We have to perform searching for "name7" or "id5",
        //then which implementation of collection will be fastest?
    }

class Student {
    String name;
    String id;

    Student(String name, String id) {
        this.name = name;
        this.id = id;
    }
} 
usare ArrayList perché la ricerca in base indicizzazione
I dati sono SEMPRE in forma di collection.get(i) = [name_i, id_i]? (con lo stesso valore di i per l’indice, il nome e l’id)?
Durante la ricerca, l’accesso veloce è primordiale, così HashMap o ArrayList (si pensi elenco ordinato e dicotomia). Ma nel tuo caso, vorrei creare un’istanza di un HashMap<String, Student>, e mappare l’id e il nome dello studente, così potrete trovare il vostro studente in O(1) (se non c’è collisione hash) !
Utilizzare java.util.HashMap per memorizzare gli Oggetti e l’uso della Chiave, ovvero il nome o l’id, due mappe in realtà uno con la chiave come il nome di altri con la chiave come id
collezione.get(i) è sempre un oggetto di studente che è una raccolta tutto,io non sono in grado di raggiungere U correttamente quello che U chiedendo?

OriginaleL’autore | 2015-05-19

3 Replies
  1. 11

    La cosa che è spesso ignorato quando si confrontano ArrayList e LinkedList è la cache e la gestione della memoria ottimizzazioni. ArrayList è effettivamente solo un array, il che significa che è memorizzato in un continuo spazio in memoria. Questo permette al Sistema Operativo di utilizzare ottimizzazioni come “quando un byte in memoria di accesso più probabile che il byte successivo sarà accessibile al più presto”. A causa di questo, ArrayList è più veloce di LinkedList, ma in un caso: quando l’inserimento/eliminazione di un elemento all’inizio della lista (perché tutti gli elementi dell’array deve essere spostato). Aggiunta/eliminazione, alla fine o in mezzo, scorrere, l’accesso all’elemento sono tutti più veloci in caso di ArrayList.

    Se è necessario per la ricerca di studente con il nome dato e id, mi sembra una mappa con chiave composita – Map<Student, StudentData>. Vorrei raccomandare di utilizzare HashMap attuazione, a meno che non è necessario essere in grado di cercare la raccolta e il recupero di tutti gli elementi ordinati per chiave nel qual caso TreeMap potrebbe essere un’idea migliore. Anche se ricordo che HashMap ha O(1) tempo di accesso, mentre TreeMap ha O(logn) tempo di accesso.

    Io non sono abbastanza sicuro di quello che si sta cercando di ottenere – perché la ricerca in questo collezione a tutti? Cosa vuoi trovare in là?

    OriginaleL’autore Jaroslaw Pawlak

  2. 1

    Con restrizioni, si dovrebbe utilizzare HashMap.
    Essa vi darà la ricerca rapida, come si desiderava.

    Se ti interessa l’attraversamento di elementi in un ordine specifico, si dovrebbe scegliere il diagramma ad albero (ordine naturale) o LinkedHashMap (inserimento dell’ordine).

    Se la vostra collezione è garantita immutabile, è possibile utilizzare ordinati ArrayList con binario di ricerca, vi farà risparmiare un po ‘ di memoria. In questo caso, è possibile cercare solo da una specifica chiave, che è auspicabile in molte applicazioni del mondo reale.

    Comunque, si dovrebbe essere davvero enorme numero di elementi (milioni/miliardi) per sentire la differenza tra O(logN) soluzioni di e O(1) soluzioni.

    Se volete saperne di più sulle strutture di dati, vi consiglio di rivedere Algoritmi di corso all’università di Princeton nel coursera.com

    OriginaleL’autore AdamSkywalker

  3. 0

    C’è nulla di male nel mantenere diverse collezioni, per l’accesso ai dati più veloce.

    In questa situazione vorrei utilizzare 2 HashMap<String, Student>‘s. Uno per ogni ricerca-chiave.

    (PS: O se non si sa che tipo di parola chiave è usato per la ricerca, quindi è possibile memorizzare nella stessa mappa).

    OriginaleL’autore bvdb

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *