Вопрос о структурах данных C # (Какую коллекцию использовать?)

Question

Мне нужно реализовать большую коллекцию объектов виджета, каждый из которых содержит уникальную строку пути к файлу ("FilePath").Мне нужно быть в состоянии сделать следующее:

1. Быстрое извлечение объекта виджета с учетом пути к файлу
2. Измените путь к файлу виджета без создания нового объекта (несколько других объектов могут содержать ссылки на один виджет, и отслеживание их может повлиять на производительность)
3. Учитывая ссылку на виджет, определите путь к его файлу

Сначала я подумал об использовании универсального SortedList, использующего путь к файлу в качестве ключа, но дублирование пути для многих тысяч объектов может быстро израсходовать память.Я рассматривал возможность удаления пути из объекта и сохранения его только в списке ключей, но это затруднило бы выполнение требования 3, приведенного выше.

К чему я сейчас склоняюсь, так это к созданию моего собственного класса, производного от List<> который добавляет объекты виджета в отсортированном порядке и извлекает их с помощью двоичного поиска.Требование 2 может быть выполнено простым удалением объекта из списка, изменением пути к его файлу и добавлением его обратно в список.

Но я относительно новичок в C #, и я хотел посоветоваться с присутствующими здесь великими умами и посмотреть, не упускаю ли я еще одно очевидное решение.

Спасибо!

Answer 1

"Дублирование" строк не приведет к удвоению объема памяти:Поскольку строки являются неизменяемыми объектами в c #, вы просто сохраните другую ссылку (т.е.указатель, 4 или 8 байтов) на каждую запись в словаре:

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

Вы всегда будете повторно использовать объект string из свойства виджета, поэтому просто продолжайте с dict и сохраните path как свойство внутри виджета.

Если вам не нужно перечислять виджеты в отсортированном порядке, не используйте SortedList, это будет медленнее, чем Словарь (O (n log n) вставка / удаление / извлечение по сравнению сO(n) среднее время)

Для изменения пути к виджету потребуется удалить его из словаря и добавить с измененным путем, но это операция со средним постоянным временем, поэтому она должна быть довольно быстрой.

И просто для того, чтобы упомянуть об этом:Даже если вам пришлось бы потратить один МБ дополнительной памяти для повышения производительности или использования более подходящей (и хорошо протестированной) структуры данных, я не думаю, что это было бы большой проблемой, учитывая объем памяти, который используют другие приложения (тратят впустую?) в наши дни ...

Answer 2

Разве вы не можете использовать 2 словаря?

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

Обработка потребует немного больше накладных расходов (поскольку вам нужно обновлять оба словаря при вставке, изменении или удалении элементов), но вы, вероятно, будете просто вставлять один поиск много раз, так что этого должно быть достаточно.

Вы даже можете создать вокруг него простой класс:

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

"Многие тысячи объектов"?Вы уверены, что эта структура вообще хранится в памяти?По-моему, это похоже на работу для какого-то типа постоянного хранилища.

Answer 4

Если вы в конечном итоге перейдете к пользовательской структуре данных, я бы предложил использовать сдерживание, а не деривацию.Гораздо лучше определить необходимый интерфейс как часть нового класса и сохранить сведения о хранилище внутренними.Если бы вы вместо этого производили от List, было бы намного сложнее обеспечить правильное использование класса, и если бы вы позже передумали, было бы сложнее что-то изменить.

Answer 5

Я думаю, вам нужен только один словарь<Widget> и соответствующий класс виджетов, который содержит ссылки на другие виджеты.Это могло бы помочь сделать его пользовательским словарем, чтобы вы могли просто добавить виджет и заставить его извлекать ключ из свойства FilePath виджета.

 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...
 }

Затем, чтобы выполнить (1), вы просто ищете виджет в репозитории виджетов по пути к файлу.

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

Чтобы выполнить (2), вы можете удалить и повторно добавить виджет в репозиторий после изменения пути к его файлу.Ссылки на виджет, хранящиеся в других виджетах, по-прежнему будут действительны.

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

Чтобы выполнить (3), просто обратитесь к свойству.

var filePath = widget.FilePath;

Если вы хотите, чтобы другие виджеты автоматически удаляли свои ссылки на виджет при его удалении (утилизации), вы, вероятно, захотите, чтобы класс Widget реализовал IDisposable и имел возможность добавлять обработчики событий к событию dispose, чтобы заинтересованные виджеты могли зарегистрировать метод, который удалит удаляемый виджет из их коллекции связанных виджетов.Видишь этот раздел MSDN о том, как настроить и использовать обработчики событий.

Answer 6

Рассматривали ли вы возможность использования Path класс?Внутренне в path - это строка, и существуют отличные методы для получения различных частей пути, т. е. GetFullPath , GetFileName, et cetera.