Structures de données C# Question (Quelle collection utiliser?)

Question

J'ai besoin d'implémenter une grande collection d'objets Widget, chacun contenant une chaîne de chemin de fichier unique ("FilePath"). Je dois être en mesure de faire ce qui suit:

1. Récupérer un objet Widget rapidement donné le chemin du fichier
2. Modifier le chemin du fichier d'un Widget sans créer un nouvel objet (plusieurs autres objets peuvent contenir des références à un seul Widget, et les traquer aurait un impact sur la performance)
3. avec une référence de Widget, déterminer son chemin de fichier

J'ai d'abord pensé à l'aide d'un SortedList générique en utilisant le chemin du fichier comme une clé, mais dupliquer le chemin pour beaucoup des milliers d'objets pourraient rapidement vous manger p mémoire. J'ai considéré enlever le chemin de l'objet et le stocker seulement dans la liste des clefs, mais cela rendrait l'exigence 3 ci-dessus difficile à accomplir. Ce à quoi je m'appuie maintenant, c'est de rouler ma propre classe dérivée de la liste <> qui ajoute les objets Widget dans un ordre trié, et les récupère avec une recherche binaire. L'exigence 2 peut être accomplie simplement en supprimant un objet de la liste, en changeant son chemin de fichier, et en l'ajoutant à la liste.

Mais je suis relativement nouveau à C# et je voulais vérifier avec les grands esprits ici et voir s'il me manque une autre solution évidente.

Merci!

Answer 1

« Dupliquer » les chaînes ne seront pas utiliser deux fois la mémoire: Puisque les chaînes sont des objets immuables en C#, vous simplement stocker une autre référence (c.-à-pointeur, 4 ou 8 byts) par entrée dans le dictionnaire:

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

Vous réutiliserez toujours l'objet chaîne de la propriété du widget, donc continuez avec le dict et stockez le chemin en tant que propriété dans le widget. Si vous n'avez pas besoin d'énumérer les widgets dans un ordre trié, n'utilisez pas la SortedList, elle sera plus lente que l'insertion/suppression/extraction du Dictionnaire (O (n log n) vs O (n) Pour modifier le chemin du widget, vous devrez le supprimer du dictionnaire et l'ajouter avec le chemin modifié, mais il s'agit d'une opération à temps constant moyen, donc cela devrait être assez rapide. Et juste pour le mentionner: même si vous deviez dépenser un Mo de mémoire supplémentaire pour obtenir plus de performance ou utiliser une structure de données mieux adaptée (et bien testée), je ne pense pas que ce soit un grand problème compte tenu de la quantité de mémoire que d'autres applicatins utilisent (gaspillent?) ces jours-ci ...

Answer 2

"Plusieurs milliers d'objets"? Êtes-vous sûr que cette structure appartient à la mémoire du tout? Cela ressemble à un travail pour un certain type de stockage persistant pour moi.

Answer 3

Vous ne pouvez pas utiliser 2 dictionnaires?

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

Le traitement aura un peu plus de frais généraux (que vous avez besoin de mettre à jour les dictionnaires lors de l'insertion, la modification ou la suppression d'éléments) mais vous aurez probablement il suffit d'insérer une fois rechercher plusieurs fois il devrait être enought.

Vous pouvez même construire une classe simple autour:

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 4

Si vous finissez par aller avec une structure de données personnalisée, je suggère d'utiliser le confinement plutôt que de dérivation. Il est préférable de définir l'interface nécessaire dans le cadre d'une nouvelle classe et de conserver les informations de stockage internes. Si vous deviez plutôt dériver de List, il serait beaucoup plus difficile d'imposer une utilisation correcte de la classe, et si vous changiez d'avis plus tard, il serait plus difficile de changer les choses.

Answer 5

Je pense que vous avez seulement besoin d'un seul dictionnaire <Widget> et une classe Widget appropriée qui contient des références aux autres Widgets. Cela peut aider à en faire un dictionnaire personnalisé afin que vous puissiez simplement ajouter un widget et le faire dériver la clé de la propriété FilePath du widget. Ensuite, pour faire (1) il suffit de regarder le widget dans le référentiel du widget par chemin de fichier.

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

Pour faire (2) vous pouvez supprimer et rajouter le widget au référentiel après avoir modifié son chemin de fichier. Les références au widget détenues par d'autres widgets seront toujours valides.

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); 
    } 

Pour faire (3) simplement référence à la propriété.

var filePath = widget.FilePath; 

Si vous voulez avoir automatiquement d'autres widgets supprimer leurs références à un widget lorsqu'il est supprimé (placé), vous aurez probablement envie d'avoir la classe Widget mettre en œuvre IDisposable et ont la possibilité d'ajouter des gestionnaires d'événements un événement de disposition afin que les widgets intéressés puissent enregistrer une méthode qui supprimera le widget étant éliminé de leur collection de widgets associés. Voir this MSDN section pour savoir comment configurer et utiliser les gestionnaires d'événements.

Answer 6

Avez-vous envisagé d'utiliser la classe Path? En interne le chemin est une chaîne et il existe des méthodes astucieuses pour obtenir diverses parties de chemin, c'est-à-dire GetFullPath, GetFileName, et cetera.