C＃數據結構問題（要使用哪個集合？）

我需要實現一個Widget對象的大集合，每個對象都包含一個唯一的文件路徑字符串（「FilePath」）。我需要能夠做到以下幾點：C＃數據結構問題（要使用哪個集合？）

檢索Widget對象迅速給定的文件路徑
改變一個構件而無需創建一個新的對象（其他多個對象可能包含一個單一的引用文件路徑窗口小部件，並跟蹤下來會影響性能）
發出的Widget參考，確定它的文件路徑

我首先想到使用通用的排序列表使用文件路徑作爲重點，但複製路徑的許多數以千計的物體可能會迅速吃掉你p內存。我考慮從對象中移除路徑並僅將其存儲在鍵列表中，但這會使上面的要求3很難完成。

我現在所傾向的是滾動我自己的類，它從列表<>中產生，它按排序順序添加Widget對象，並通過二分搜索來檢索它們。要求2可以簡單地通過從列表中刪除一個對象，更改它的文件路徑並將其添加回列表來完成。

但是我對C＃比較陌生，我想在這裏檢查一下偉大的思想，看看我是否錯過了另一個明顯的解決方案。

謝謝！

來源

2009-04-11 Bill Brooks

「複製」的字符串將不會使用兩倍的存儲器：在詞典中每個條目由於字符串是在c＃不變的對象，就會只存儲另一個參考（即指針，4個或8 byts）：

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

您將始終使用窗口小部件屬性中的字符串對象，所以繼續使用字典並將路徑作爲屬性存儲在窗口小部件中。如果您不需要按排序順序枚舉窗口小部件，不要使用SortedList，它將比字典（O（n log n）插入/刪除/檢索與O（n）平均時間）

更改窗口小部件的路徑將需要您從字典中刪除它並將其添加到已更改的路徑中，但這是一個平均常量時間操作，所以它應該非常快。

並且只是提及它：即使您需要花費一MB額外內存才能獲得更高性能或使用更適合（且經過良好測試）的數據結構，我不認爲這會是考慮到其他應用程序正在使用（浪費？）這些天的內存量的大問題...

來源

2009-04-11 17:19:18 MartinStettner

這個答案和其他人回答了這個問題的部分內容，但這是解決主要問題的答案，也是最簡潔的答案。謝謝！ – 2009-04-11 20:26:38

「成千上萬的物體」？你確定這個結構屬於記憶麼？聽起來像是一種針對某種持久性存儲的工作。

來源

2009-04-11 16:07:41

你不能使用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); 
    } 
}

來源

2009-04-11 16:09:23

+1我只是打算髮表這個。 – 2009-04-11 16:13:03

但是，如果每個Widget包含一個Path成員，那麼我不需要第二個字典。我主要關心的是重複路徑。如果我們假設每條路徑平均爲30個字節，並且我們正在處理（在極端情況下）30k個對象，那麼大概是一個兆字節的重複。 – 2009-04-11 16:31:24

如果用戶恰好在使用大量嵌套的文件，那可能會很快增長！ – 2009-04-11 16:37:31

如果你結束了一個自定義的數據結構中去，我會建議使用圍堵，而非推導。將必要的接口定義爲新類的一部分會更好，並將存儲細節保留在內部。如果你是從List中派生出來的，那麼強化這個類的正確使用將會困難得多，並且如果你後來改變了主意，那麼改變事情就會變得更加困難。

來源

2009-04-11 16:15:58 Charlie

優秀的點。謝謝！ – 2009-04-11 16:25:13

我認爲你只需要一個字典<Widget>和一個合適的Widget類，其中包含對其他Widgets的引用。這可能有助於將其定製爲自定義詞典，以便您可以簡單地添加一個Widget並讓它從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事件，以便感興趣的小部件可以註冊一個方法，該方法將從它們的相關小部件集合中移除正在部署的小部件。有關如何設置和使用事件處理程序，請參見this MSDN section。

來源

2009-04-11 16:37:15 tvanfosson

您是否考慮過使用Path類？內部路徑是一個字符串，並且存在用於獲得各種路徑部分的精妙方法，即GetFullPath,GetFileName等等。

來源

2012-01-07 02:24:45 radarbob

C＃數據結構問題（要使用哪個集合？）

回答

相關問題