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

Question

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

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

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

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

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

Спасибо!

Answer 1

Разве вы не можете использовать 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 2

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

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

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

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

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

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

Answer 3

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

Answer 4

Я думаю, что вам нужен только один словарь и соответствующий класс виджетов, который содержит ссылки на другие виджеты. Это может помочь сделать его пользовательским словарем, чтобы вы могли просто добавить виджет и получить его из ключа 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 5

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

Answer 6

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