持有一百萬件物品的最佳收藏？

如果集合包含很多項目（超過100萬），那麼什麼樣的集合是最好的標準性能。

舉例來說，我創建了簡單的List（10000000）集合並嘗試添加大約500000個不同的項目。運行結束後10秒內首先添加30000件物品，但運行後1分鐘內收集的物品只有60000件，5分鐘後物品150000件。

據我所知，通過添加新項目（因爲每個項目都在「類似等於」時間段內創建），內存使用在收集中存在非線性依賴關係。但我可以犯一個錯誤。

編輯：你是對的，如果沒有樣本，它是不夠清楚。我想填充樹作爲連接列表。您可以在下面找到示例代碼。

public class Matrix 
{ 
    public int Id { get; private set; } 
    public byte[,] Items { get; private set; } 
    public int ParentId { get; private set; } 
    public int Lvl { get; private set; } 
    public int HorizontalCounts 
    { 
     get { return 3; } 
    } 

    public int VerticalCounts 
    { 
     get { return 3; } 
    } 

    public Matrix(int id) : this(id, null, 0, 1) 
    { 
    } 

    public Matrix(int id, byte[,] items, int parentId, int lvl) 
    { 
     Id = id; 
     Items = (items ?? (new byte[HorizontalCounts, VerticalCounts])); 
     ParentId = parentId; 
     Lvl = lvl; 
    } 

    public bool IsEmpty(int hCounter, int vCounter) 
    { 
     return (Items[hCounter, vCounter] == 0); 
    } 

    public Matrix CreateChild(int id) 
    { 
     return (new Matrix(id, (byte[,])Items.Clone(), Id, (Lvl + 1))); 
    } 
} 

public class Program 
{ 
    public static void Main(string[] args) 
    { 
     Matrix node = new Matrix(1); 
     const int capacity = 10000000; 
     List<Matrix> tree = new List<Matrix>(capacity) { node }; 

     FillTree(ref tree, ref node); 

     int l1 = tree.Where(n => (n.Lvl == 1)).Count(); 
     int l2 = tree.Where(n => (n.Lvl == 2)).Count(); 
     int l3 = tree.Where(n => (n.Lvl == 3)).Count(); 
     int l4 = tree.Where(n => (n.Lvl == 4)).Count(); 
     int l5 = tree.Where(n => (n.Lvl == 5)).Count(); 
    } 

    private static void FillTree(ref List<Matrix> tree, ref Matrix node) 
    { 
     for (int hCounter = 0; hCounter < node.HorizontalCounts; hCounter++) 
     { 
      for (int vCounter = 0; vCounter < node.VerticalCounts; vCounter++) 
      { 
       if (!node.IsEmpty(hCounter, vCounter)) 
       { 
        continue; 
       } 

       int childId = (tree.Select(n => n.Id).Max() + 1); 
       Matrix childNode = node.CreateChild(childId); 
       childNode.Items[hCounter, vCounter] = 1; 

       tree.Add(childNode); 

       FillTree(ref tree, ref childNode); 
      } 
     } 
    } 
}

最新版本：我很抱歉，問題是沒有在項目的數量到需要的集合。性能問題在這一行：int childId =（tree.Select（n => n.Id）.Max（）+ 1）;非常感謝您的回答和評論。

來源

2010-09-03 Maxim Polishchuk

您是否有足夠的空間容納百萬件物品？ – 2010-09-03 12:38:49

這是什麼，你試圖用這麼多項目？ – 2010-09-03 12:39:28

我認爲這取決於你將要使用的集合。你打算做很多查找還是要迭代集合？也許一個數組會是一個更好的選擇？ – 2010-09-03 12:40:53

對此的答案取決於。你會做很多插入沒有排序？鏈接列表
你打算做很多查找嗎？哈希映射/字典
你打算只是有一個無序的一組東西？列表和/或數組
你不想重複嗎？設置
你不想重複，但想要快速查找？ HashSet
您是否有一個按鍵排序的有序列表？ TreeMap

來源

2010-09-03 13:22:05 Woot4Moo

謝謝。但我只是想盡可能快地填寫我的清單:) – 2010-09-03 13:26:49

LinkedList imo（15個字符） – Woot4Moo 2010-09-03 13:31:00

@Maxim如果您只是想盡快填寫清單，爲什麼還要幹什麼？假設你想以某種方式將這些項目從列表中退出，這對你使用的數據結構有很大的影響。 – 2010-09-03 15:15:00

如果你想增加一個億名的項目，創建它想：

var myList = new List<MyItem>(1500000);

存儲150萬個引用（或小的結構）也不是很貴，讓列表的自適應增長算法分配的空間將是昂貴的。

來源

2010-09-03 12:51:53

我使用相同的方法創建集合。可能，問題是在遞歸函數中使用堆棧... – 2010-09-03 13:23:37

你想要一個數組，如果你事先知道確切的數量。如果你可以分配一次，然後簡單地填滿，那麼一個簡單的數組是完美的。沒有浪費的內存，最快填充，最快刪除。

來源

2010-09-03 13:17:36

當你處理數百萬（或更多）的項目時，最好使用一個數組。即使您通過使陣列超過絕對必要的數量而浪費了幾千個插槽，所獲得的時間效率也可能會彌補空間效率的損失。

當然，如果您處理的數據量太大而不能完全存儲在內存中，則建議使用基於磁盤的數據結構。

來源

2010-09-03 13:35:40 quanticle

「最好使用數組。」我不同意。列表初始化爲適當的容量將具有相似的空間要求，並且更靈活 – Joe 2010-09-03 14:55:40

除非數組將被創建一次並且存在於應用程序的生命週期中，否則我傾向於建議某種類型的嵌套數組，其中每個數組的大小保持在8000字節以下（如果它包含任何雙精度值 - 精確的浮點數字，或85,000字節，如果沒有。大尺寸的對象被放置在大對象堆上。與普通堆不同，它可以有效地處理許多對象的創建和放棄操作，而大型對象堆在.net 2.0-3.5下處理得很差，在4.0以下只能稍好一些。

如果您不會進行插入或刪除操作，我會建議您最簡單的方法是使用由1024個1024個元素組成的數組。通過索引訪問元素將是一個簡單的事情，將索引右移10，使用結果選擇一個數組，然後使用底部的10位來查找數組中的項目。

如果需要插入和刪除，我會建議使用鋸齒狀數組以及某種數據結構來跟蹤每個子數組的邏輯長度，並幫助將索引轉換爲數組位置。這樣做會避免在執行插入或刪除操作時需要複製大量數據，代價是更昂貴的下標操作。

來源

2011-08-05 21:29:07 supercat

持有一百萬件物品的最佳收藏？

回答

相關問題