Strutture C # dati domanda (Quale collezione da usare?)

Question

Ho bisogno di attuare una vasta collezione di oggetti Widget, ognuna delle quali contiene una stringa di percorso di file unico ( "FilePath"). Ho bisogno di essere in grado di fare quanto segue:

1. Recupera un oggetto Widget rapidamente dato il percorso del file
2. Modificare il percorso del file di un widget senza creare un nuovo oggetto (più altri oggetti possono contenere riferimenti a un singolo widget, e li rintracciare avrebbe un impatto sulle prestazioni)
3. Dato un riferimento Widget, determinare il suo percorso di file

ho pensato di utilizzare un SortedList generico utilizzando il percorso del file come una chiave, ma duplicando il percorso per molte migliaia di oggetti potevano mangiare velocemente la memoria. Ho considerato rimuovere il percorso dall'oggetto e solo memorizzare nella lista delle chiavi, ma che renderebbero requisito 3 sopra difficile da realizzare.

Quello che sto appoggiato verso la società sta rotolando la mia classe derivata da List <> che aggiunge gli oggetti widget in un modo ordinato, e li recupera con una ricerca binaria. Requisito 2 può essere realizzato semplicemente rimuovendo un oggetto dalla lista, cambiando il suo percorso di file, e l'aggiunta di nuovo alla lista.

Ma io sono relativamente nuovo per C # e volevo verificare con le grandi menti qui e vedere se mi manca un'altra soluzione ovvia.

Grazie!

Answer 1

"Duplicazione" le stringhe non utilizzare il doppio della memoria: Dal momento che le stringhe sono oggetti immutabili in C #, sarà solo di memorizzare un altro riferimento (vale a dire di puntatore, 4 o 8 byts) per ogni linea di dizionario:

Dictionary<string, Widget> dict = new Dictionary<string, Widget>();
Widget myWidget = GetSomeWidget();
dict.Add(myWidget.Name, myWidget);

Sarete sempre riutilizzando l'oggetto stringa dalla proprietà del widget, quindi basta andare avanti con il dict e memorizzare il percorso come di proprietà all'interno del widget.

Se non è necessario enumerare i widget in modo ordinato, non utilizzare il SortedList, sarà più lento del Dizionario (O (n log n) inserzione / delezione / recupero vs. O (n media) tempo)

Modifica percorso del widget sarà bisogno di voi per rimuoverlo dal dizionario e aggiungerlo con il percorso modificato, ma si tratta di un'operazione media costante di tempo, quindi dovrebbe essere abbastanza veloce.

E proprio di parlarne: Anche se si dovrebbe spendere una MB di memoria aggiuntiva per ottenere maggiori prestazioni o utilizzando una struttura dati più adatto (e collaudato), non credo che sarebbe un grande problema considerando la quantità di memoria altri applicatins stanno utilizzando (sprecando?) di questi tempi ...

Answer 2

Non puoi utilizzare 2 dictionarys?

Dictionary<string, Widget> WidgetsByPath;
Dictionary<Widget, string> PathsByWidget;

Il trattamento avrà un po 'più in alto (come è necessario aggiornare entrambi i dizionari durante l'inserimento, la modifica o l'eliminazione di elementi), ma probabilmente sarà solo inserire una volta occhiata molte volte quindi dovrebbe essere enought.

Si può anche costruire una semplice classe intorno ad esso:

public class Widgets
{
  public Widget Add(string Path, Widget wdg)
  {
    // Chek it doesn't already exits and all...
    WidgetsByPath.Add(Path, wdg);
    PathsByWidget.Add(wdg, Path);
  }

  public void Delete(string Path)
  {
    Widget w = WidgetsByPath[Path];
    PathsByWidget.Delete(w);
    WidgetsByPath.Delete(Path);
  }
}

Answer 3

"Molte migliaia di oggetti"? Sei sicuro che questa struttura appartiene in memoria a tutti? Suona come un lavoro per un certo tipo di storage permanente per me.

Answer 4

Se si finisce per andare con una struttura di dati personalizzato, vi suggerirei di usare contenimento piuttosto che di derivazione. E 'molto meglio per definire l'interfaccia necessaria come parte di una nuova classe, e mantenere i dettagli di storage interno. Se si dovesse invece derivare da List, sarebbe molto più difficile da far rispettare l'uso corretto della classe, e se hai cambiato idea in seguito, sarebbe più difficile da cambiare le cose.

Answer 5

Credo che è necessario solo un singolo Dizionario e una classe Widget appropriato che contiene riferimenti alla altri widget. Potrebbe contribuire a renderlo un dizionario personalizzato in modo che si può semplicemente aggiungere un widget e farlo derivare la chiave dalla proprietà FilePath del widget.

 public class WidgetDictionary : Dictionary<string,Widget>
 {
     ... provide suitable constructors ...

     public void Add( Widget widget )
     {
         if (widget != null && !this.ContainsKey( widget.FilePath ))
         {
             this.Add( widget.FilePath, widget );
         }
     }
 }

 public class Widget
 {
      public string FilePath { get; set; }

      private List<Widget> widgets = new List<Widget>();
      public IEnumerable<Widget> Widgets
      {
          get { return widgets; }
      }

      ...code to add/remove widgets from list...
 }

Quindi a che fare (1) è sufficiente guardare il widget nella repository widget facendo il percorso del file.

 var repository = new WidgetDictionary();
 string filePath = ...
 var widget = repository[filePath];

Per fare (2) è possibile rimuovere e re-aggiungere il widget al repository dopo aver cambiato il suo percorso di file. I riferimenti al widget di detenuto da altri widget saranno ancora validi.

var widget = repository[filePath];
repository.Remove(filePath);
widget.FilePath = newFilePath;
repository.Add(widget);

 EDIT: this could probably be implemented as a method on the
 dictionary as well.

   public void UpdatePath( Widget widget, string newPath )
   {
       if (string.IsNullOrEmpty(newPath))
          throw new ArgumentNullException( "newPath" );

       var widget = this.ContainsKey(widget.FilePath)
                             ? this[widget.FilePath]
                             : null;

       if (widget != null)
       {           
           this.Remove(widget.FilePath);
       }
       widget.FilePath = newPath;
       this.Add( widget );
    }

Per fare (3) semplicemente fare riferimento alla proprietà.

var filePath = widget.FilePath;

Se si desidera avere automaticamente altri widget rimuovere i loro riferimenti a un widget quando viene cancellata (smaltiti), probabilmente vuole avere la classe Widget implementare IDisposable e hanno la possibilità di aggiungere i gestori di eventi per un evento così dispose che i widget interessati possono registrare un metodo che rimuovere il widget essendo disposto dal loro insieme di widget correlati. Vedere questa sezione MSDN su come impostare e utilizzare i gestori di eventi.

Answer 6

Hai pensato di usare il Path classe ? Internamente il percorso è una stringa e non ci sono metodi ingegnosi per ottenere le varie parti di percorso, vale a dire GetFullPath, GetFileName, eccetera.