(Ho aggiunto i tag .NET perché le strutture dati sono per .NET, e questa domanda dovrebbe essere considerata nel contesto delle convenzioni per quella piattaforma.)
Sto scrivendo una libreria di strutture dati immutabili e persistenti per .NET. Una delle mie strutture dati, un tipo di vettore, supporta le seguenti operazioni principali:
- Aggiunta e rimozione alla fine
- Ricerca e aggiornamento per indice
- Avvio della sottosequenza
- (Cose non interessanti come la lunghezza, ecc.)
Inoltre, vi è un'implementazione speciale di operazioni di massa (che coinvolgono sequenze, come l'aggiunta di molti elementi) che è estremamente veloce per i grandi input. Questo rende l'aggiunta di molti elementi alla fine molto, molto velocemente.
Il mio problema è un po 'più complicato rispetto al titolo della domanda. Posso implementare le seguenti operazioni aggiuntive:
- Aggiunta di molti elementi all'inizio
- Inserimento di molti elementi nel mezzo
L'aggiunta di molti elementi alla fine è O(m + logn) , dove m è il numero di elementi da aggiungere. Queste operazioni sarebbero O(n + m) , e se m = n allora sono quasi veloci come aggiunte alla fine. In pratica, sarebbero più veloci di molti ordini di grandezza rispetto a quando l'utente li avesse implementati in modo ingenuo. Tuttavia, per un numero ridotto di elementi, sarebbero comunque molto lenti.
Il mio primo problema è che le normali operazioni sono così veloci che potrebbero confondere gli utenti e indurli a pensare che queste operazioni aggiuntive funzionino in modo simile. A differenza delle raccolte regolari in cui anche List<T>.Insert è veloce, questo può effettivamente rallentare l'applicazione. Come devo affrontare questo?
Il mio secondo problema è che, se implemento queste operazioni aggiuntive, dovrei anche fornire operazioni simili (estremamente inefficienti) che funzionano con singoli elementi? Sembra strano non fornire queste operazioni apparentemente più semplici, e sono sicuro che saranno a portata di mano (a volte le prestazioni non sono affatto importanti), ma quel fattore di sorpresa è ancora peggio qui, dal momento che queste operazioni non possono mai essere efficienti.
Una considerazione simile si applica a un'operazione Skip (terminando la sottosequenza).