使用大量对象,需要更好(排序)的性能

Question

我有一个巨大的(~100,000)对象集合,我无法控制(让我们称之为masterList).它们很简单,有几个领域

public class TheirObject{
public String GUID;
public int blah1;
public string blah2;
...
}

我有另外几万个GUID(作为字符串列表)的集合,我需要为列表中的每个GUID创建一个子对象列表,其中包含masterList中具有相同GUID的任何一个.

这是一些简单的代码:

 List<String> GUIDs;
 List<TheirObject> masterList;
 List<TheirObject> filteredList;
 foreach(String GUID in GUIDs)
 {
      filteredList = new List<TheirObject>();
      foreach(TheirObject tho in masterList)
           if(tho.GUID == GUID)
                filteredList.Add(tho);
      //do stuff with filteredList
 }

但是,这需要几个小时!我相信,有一个很大更快的方式做到这一点,涉及到排序的名单,然后二进制搜索查找perhaphs,但我无法弄清楚如何做到这一点在C#.几个TheyObjects在masterList中具有相同的GUID,所以我认为我不能使用SortedList.救命!

Answer 1

使用LINQ的直接代码方法类似于:

var lookup = masterList.ToLookup(tho => tho.GUID);
// Now you have a hash-table based lookup containing the lists of TheirObject grouped by GUID
foreach(string GUID in GUIDs)
{
    filteredList = lookup[GUID].ToList();
    // Do your stuff with filteredList
}

这里的关键是不要多次迭代巨大的列表,这就是杀死性能的原因.相反,迭代它一次并构建有效的查找.这个初始构建需要一些时间,后续查找几乎不需要时间和(接近)O(1).

现在,如果列表真的很大并且内存约束不允许您构建更适合查找的数据结构,我可能会尝试将工作卸载到数据库,如评论中所建议的那样.