Pregunta sobre estructuras de datos de C# (¿Qué colección usar?)

Question

Necesito implementar una gran colección de objetos Widget, cada uno de los cuales contiene una cadena de ruta de archivo única ("FilePath").Necesito poder hacer lo siguiente:

1. Recuperar un objeto Widget rápidamente dada la ruta del archivo
2. Cambiar la ruta del archivo de un widget sin crear un nuevo objeto (varios otros objetos pueden contener referencias a un único widget, y rastrearlos afectaría el rendimiento)
3. Dada una referencia de widget, determine la ruta del archivo

Primero pensé en usar una SortedList genérica usando la ruta del archivo como clave, pero duplicar la ruta para muchos miles de objetos podría consumir memoria rápidamente.Consideré eliminar la ruta del objeto y almacenarla solo en la lista de claves, pero eso haría que el requisito 3 anterior fuera difícil de cumplir.

A lo que me inclino ahora es a desarrollar mi propia clase derivada de List<> que agrega los objetos Widget en un orden ordenado y los recupera con una búsqueda binaria.El requisito 2 se puede cumplir simplemente eliminando un objeto de la lista, cambiando la ruta del archivo y agregándolo nuevamente a la lista.

Pero soy relativamente nuevo en C# y quería consultar con las grandes mentes aquí y ver si me falta otra solución obvia.

¡Gracias!

Answer 1

"Duplicar" las cadenas no van a usar el doble de memoria: Como las cadenas son objetos inmutables en C #, se le acaba de almacenar otra referencia (es decir, puntero, 4 u 8 byts) por entrada en el diccionario:

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

Siempre se va a reutilizar el objeto de cadena de propiedad del widget, por lo que sólo tiene que ir adelante con el dict y almacena la ruta como una propiedad dentro del widget.

Si no es necesario enumerar los widgets en el orden establecido, no utilice el SortedList, será más lento que el diccionario (O (n log n) de inserción / deleción / recuperación frente a O () n promedio tiempo)

Cambiar la trayectoria del widget que se necesita para sacarlo del diccionario y añadirlo a la ruta cambiada, pero esta es una operación promedio constante de tiempo, por lo que debe ser bastante rápido.

Y sólo para mencionar: Incluso si usted tendría que pasar un MB de memoria adicional para conseguir un mayor rendimiento o el uso de una estructura de datos más aptas (y bien probado), no creo que sería un gran problema teniendo en cuenta la cantidad de memoria que no applicatins está usando (perdiendo?) en estos días ...

Answer 2

¿No puedes usar 2 dictionarys?

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

El manejo tendrá un poco más de riesgo (como sea necesario para actualizar ambos diccionarios al insertar, modificar o eliminar elementos) pero probablemente será sólo tiene que insertar una vez que las operaciones de búsqueda muchas veces lo que se debe enought.

Usted puede incluso construir una clase simple alrededor de ella:

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

"Muchos miles de objetos"? ¿Seguro de esta estructura en la memoria pertenece a todos? Suena como un trabajo para algún tipo de almacenamiento persistente para mí.

Answer 4

Si usted termina yendo con una estructura de datos personalizados, se recomienda usar la contención en lugar de derivación. Es mucho mejor para definir la interfaz necesaria como parte de una nueva clase, y mantener los detalles de almacenamiento interno. Si se va a derivar en lugar de la lista, sería mucho más difícil de hacer cumplir el uso adecuado de la clase, y si ha cambiado de opinión más tarde, sería más difícil de cambiar las cosas.

Answer 5

Creo que solo necesitas un Diccionario<Widget> y una clase de Widget apropiada que contenga referencias a los otros Widgets.Podría resultar útil convertirlo en un diccionario personalizado para que pueda simplemente agregar un widget y hacer que derive la clave de la propiedad 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...
 }

Luego, para hacer (1), simplemente busque el widget en el repositorio de widgets por ruta de archivo.

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

Para hacer (2), puede eliminar y volver a agregar el widget al repositorio después de cambiar la ruta del archivo.Las referencias al widget en poder de otros widgets seguirán siendo válidas.

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

Para hacer (3) simplemente haga referencia a la propiedad.

var filePath = widget.FilePath;

Si desea que otros widgets eliminen automáticamente sus referencias a un widget cuando se elimina (elimina), probablemente querrá que la clase Widget implemente IDisposable y tenga la capacidad de agregar controladores de eventos a un evento de eliminación para que los widgets interesados puede registrar un método que eliminará el widget que se está eliminando de su colección de widgets relacionados.Ver esta sección de MSDN sobre cómo configurar y utilizar controladores de eventos.

Answer 6

¿Usted ha considerado el uso de la clase Path? Internamente la camino es una cadena y hay métodos ingeniosos para conseguir diversas partes de trayectoria, es decir GetFullPath, GetFileName, etcétera.