Vantaggi della memorizzazione nella cache del conteggio degli elementi in una struttura dati rispetto al calcolo su richiesta?

1

Data una struttura dati, voglio fornire un metodo API Size che restituisce il numero di elementi.

Sto oscillando tra 2 approcci:

  1. Mantenere un conteggio e incrementarlo / ridurlo in risposta a Aggiungi / Elimina chiamate rispettivamente
  2. Esegui un attraversamento per calcolare il conteggio quando viene chiamato Size .

L'approccio n. 2 prenderà O (n) contro O (1) per l'approccio n. 1. Oltre alle prestazioni, altri vantaggi del # 1 rispetto al # 2?

    
posta Jacques René Mesrine 15.05.2014 - 00:28
fonte

1 risposta

1

Mantenendo un conteggio separato, si corre il rischio di errori che causano il conteggio del conteggio con il numero effettivo di elementi nella struttura dati. Ora, se il tuo codice è privo di bug, questo non sarà un problema, ma non puoi garantire che rimarrà privo di bug per sempre (se qualcun altro arriva e cambia qualcosa).

Preferirei quasi sempre l'opzione n. 2 a meno che le misurazioni dimostrino che è necessario ottimizzare le prestazioni.

    
risposta data 15.05.2014 - 00:30
fonte

Leggi altre domande sui tag