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

如果集合包含很多项目（超过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

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

回答

相关问题