C# Data Structures Question (Какая коллекция использовать?)

Question

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

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

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

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

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

Спасибо!

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

Answer 5

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

Затем, чтобы сделать (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, чтобы заинтересованные виджеты могли зарегистрировать метод, который удалит виджет, удаляемый из их коллекции связанных виджетов. См. this MSDN section о том, как настроить и использовать обработчики событий.

Answer 6

Вы считаете, что используете класс Path? Внутренне путь - это строка, и существуют отличные способы получения различных частей пути, то есть GetFullPath, GetFileName и т. Д.