A quale volume è considerata una struttura dati specifica utile

Question

A quale volume è considerata una struttura dati specifica utile

#1 da (4 voti)
#2 da (3 voti)
#3 da (2 voti)

3

Ho avuto questa discussione con i colleghi prima. Abbiamo dovuto memorizzare users di id e faremo principalmente operazioni Add / Get su di esso. Ho proposto di utilizzare un Dictionary che sembra la scelta logica. Il mio collega ha affermato che il Dictionary era inutile in quel caso perché non avevamo molti utenti (forse 150).

Ho proposto il dizionario perché so, in teoria, che è la migliore struttura dati per questo scenario. Nel caso in cui ho 150 utenti (che è un numero arbitrario), c'è davvero una differenza di prestazioni tra l'accesso O (1) di un Dictionary e l'accesso O (n) di un List ?

Ha proposto il List perché il Dictionary sembrava inutile in quel caso.

Abbiamo finito per utilizzare Dictionary perché se l'applicazione dovesse crescere, avremmo più utenti e il Dictionary si sarebbe rivelato utile.

Anche se la domanda è rimasta, ci sono scenari in cui non dovremmo considerare quali strutture di dati usare?

data-structures

posta IEatBagels 03.12.2015 - 21:12

fonte

3 risposte

Leggi altre domande sui tag data-structures

Downcasting automatico È strano se i nodi di una lista collegata contengono riferimenti all'oggetto List?

score 4 · Answer 1

Il tuo collega ha una strana logica. Un dizionario potrebbe non avere un vantaggio in termini di prestazioni se il numero di elementi è piccolo, ma ciò non significa che ci sia qualche vantaggio nell'utilizzare una lista!

Se il numero di operazioni è ridotto, la differenza di prestazioni è probabilmente non importante in entrambi i casi, quindi è necessario scegliere la struttura dati più semplice da utilizzare per l'attività in corso. Se vuoi archiviare gli utenti per id, un dizionario sembra la scelta naturale.

score 3 · Answer 2

In questo caso, un dizionario è più appropriato, ma qui ci sono due considerazioni:

Come identifichi i dati?
Come si aggiungono o rimuovono i dati?

Una lista accede per indice. Questo è semplicemente l'ordine degli elementi nella struttura dei dati. Un dizionario o una tabella hash aggiunge un altro layer usando una chiave, e il suo hash è l'indice nella matrice sottostante.

Nel tuo caso hai bisogno di una struttura in cui puoi utilizzare gli ID utente per accedere ai dati. Cosa preferiresti fare?

Questa:

dictionary.get(userId);

O questo:

for (User u : users) {
  if (userId == u.userId) {
    return u;
  }
}

Ha più senso ottenere un utente per ID piuttosto che cercare l'intero elenco (è O (n)) per esso.

L'altra considerazione è come aggiungi o rimuovi i dati. Questo risale all'intera discussione "elenco di elenchi a elenco collegato" che viene insegnata in qualsiasi programma di laurea di primo livello, quindi tralascerò qui. L'altro dettaglio da tenere a mente è che è appropriato anche per i dizionari: è possibile implementarli con un array (tabella hash) o un albero. Ognuno ha vantaggi e svantaggi ed è più efficiente a diversi tipi di mutazioni e accessi.

Nota che in nessun momento "quanti dati ci saranno" entrerà nell'equazione. In genere, le preoccupazioni sopra riportate determinano la selezione della struttura dei dati, non la quantità di dati. L'unica volta che questo dovrebbe essere un problema è se ci sono così tanti dati che non possono essere tutti inseriti nella memoria in una volta.

score 2 · Answer 3

Oltre alle prestazioni, dovresti considerare anche il principio di minima sorpresa per i futuri programmatori: se la ricerca viene eseguita per articolo piuttosto che per indice, ma viene utilizzata una lista, questa è una scelta di design sorprendente e se io sono leggendo il codice, mi porta a perdere tempo a capire perché è implementato in questo modo.

Potrei pensare: "Ha bisogno di essere ordinato da qualche parte?" "Viene ordinato?" "Era pensato per essere ordinato ma non è stato ancora implementato? Doveva essere implementato ma gli sviluppatori si sono dimenticati di farlo?"

In altre parole aumenta la velocità del wtf / minuto, che è un modo per misurare la qualità del codice.