oggetti - strutture dati java




Prestazioni di hash set e array list (3)

Ho implementato un metodo che scorre semplicemente attorno a una serie di file CSV che contengono dati su un numero di moduli diversi. Questo aggiunge quindi "moduleName" in un hashSet. (Codice mostrato sotto)

Ho usato un hashSet in quanto garantisce che non vengano inseriti duplicati al posto di un ArrayList che dovrebbe utilizzare il metodo contain () e scorrere l'elenco per verificare se è già presente.

Credo che l'utilizzo del set di hash abbia prestazioni migliori rispetto a un elenco di array. Sono corretto affermando che?

Inoltre, qualcuno può spiegarmi:

  1. Come utilizzare le prestazioni per ciascuna struttura dati se utilizzata?
  2. Qual è la complessità usando la notazione O grande?

    HashSet<String> modulesUploaded = new HashSet<String>();
    
    for (File f: marksheetFiles){
        try {
            csvFileReader = new CSVFileReader(f);
            csvReader = csvFileReader.readFile();
            csvReader.readHeaders();
    
            while(csvReader.readRecord()){
                String moduleName = csvReader.get("Module");
    
                if (!moduleName.isEmpty()){
                    modulesUploaded.add(moduleName);
                }
            }
    
        } catch (IOException e) {
            e.printStackTrace();
        }
    
        csvReader.close();
    }
    return modulesUploaded; 
    

    }


Credo che l'utilizzo del set di hash abbia prestazioni migliori rispetto a un elenco di array. Sono corretto affermando che?

Con molte voci (qualunque cosa significhi), sì. Con dimensioni di dati ridotte, tuttavia, la ricerca lineare lineare potrebbe essere più veloce dell'hashing. Dove esattamente è il break-even, devi solo misurare. Il mio istinto è che con meno di 10 elementi, la ricerca lineare è probabilmente più veloce; con più di 100 elementi l'hashing è probabilmente più veloce, ma questo è solo il mio sentimento ...

La ricerca da un HashSet è costante, O (1), a condizione che l'implementazione di hashCode degli elementi sia sensata. La ricerca lineare da una lista è il tempo lineare, O (n).


Dipende dall'uso della struttura dei dati.

Stai archiviando i dati in HashSet e per il tuo caso per la memorizzazione HashSet è migliore di ArrayList (dato che non vuoi inserire voci duplicate). Ma solo la memorizzazione non è il solito intento.

Dipende dal modo in cui desideri leggere ed elaborare i dati memorizzati. Se si desidera l'accesso sequenziale o l'accesso basato su indice casuale, ArrayList è migliore o se l'ordine non è importante, HashSet è migliore.

Se l'ordine conta ma vuoi fare molte modifiche (aggiunte e cancellazioni) la LinkedList è migliore.

Per accedere a un particolare elemento HashSet avrà una complessità temporale come O (1) e se tu avessi usato ArrayList sarebbe stato O (N) come tu stesso hai indicato che avresti dovuto scorrere l'elenco e vedere se l'elemento è non presente.


Il mio esperimento mostra che HashSet è più veloce di un ArrayList partire da raccolte di 3 elementi in modo inclusivo.

Una tabella completa dei risultati

| Boost  |  Collection Size  |
|  2x    |       3 elements  |
|  3x    |      10 elements  |
|  6x    |      50 elements  |
|  12x   |     200 elements  |  <= proportion 532-12 vs 10.000-200 elements
|  532x  |  10.000 elements  |  <= shows linear lookup growth for the ArrayList




hashset