3

所以我有几个不同的列表，我正在尝试处理并合并到一个列表中。

下面是一段代码，我想看看是否有更好的方法。我问的原因是其中一些列表相当大。我想看看是否有更有效的方法来做到这一点。

如您所见，我正在遍历一个列表，我要做的第一件事是检查 CompanyId 是否存在于列表中。如果是这样，那么我会在列表中找到要处理的项目。

pList 是我的进程列表。我正在将不同列表中的值添加到此列表中。

我想知道是否有一种“更好的方法”来完成存在和查找。 

    boolean tstFind = false;
    foreach (parseAC item in pACList)
    {
        tstFind = pList.Exists(x => (x.CompanyId == item.key.ToString()));

        if (tstFind == true)
        {
            pItem = pList.Find(x => (x.CompanyId == item.key.ToString()));
            //Processing done here.  pItem gets updated here
            ...
         }

顺便说一句，我将研究一种使用连接的方法，看看它是否更快。但我还没有到达那里。上面的代码是我第一次解决这个问题，它似乎有效。但是，由于我有时间，我想看看是否还有更好的方法。

非常感谢任何输入。

时间发现：

  • 我当前的 Find and Exists 代码大约需要84 分钟才能遍历 pACList 中的 5.5M 项。

  • 使用 pList.firstOrDefault(x=> x.CompanyId == item.key.ToString()); 循环遍历 pACList 中的 550 万个项目需要54 分钟

4

6 回答 6

3

您可以检索项目FirstOrDefault而不是搜索项目两次（第一次定义项目是否存在，第二次获取现有项目）：

var tstFind = pList.FirstOrDefault(x => x.CompanyId == item.key.ToString());

if (tstFind != null)
{            
   //Processing done here.  pItem gets updated here        
}
于 2013-01-28T20:10:37.407 回答
3

是的，使用哈希表，以便您的算法是 O(n) 而不是现在的 O(n*m)。

var pListByCompanyId = pList.ToDictionary(x => x.CompanyId);
 foreach (parseAC item in pACList)
    {
        if (pListByCompanyId.ContainsKey(item.key.ToString()))
        {
            pItem = pListByCompanyId[item.key.ToString()];
            //Processing done here.  pItem gets updated here
            ...
         }
于 2013-01-28T20:13:56.263 回答
2

您可以使用 linq 遍历过滤列表 

foreach (parseAC item in pACList.Where(i=>pList.Any(x => (x.CompanyId == i.key.ToString()))))
    {
            pItem = pList.Find(x => (x.CompanyId == item.key.ToString()));
            //Processing done here.  pItem gets updated here
            ...
    }
于 2013-01-28T20:11:06.187 回答
2

对这种类型的操作使用列表是 O(MxN)（M 是 pACList 的计数，N 是 pList 的计数）。此外，您正在搜索 pACList 两次。为避免该问题，pList.FirstOrDefault请按照@lazyberezovsky 的建议使用。

但是，如果可能的话，我会避免使用列表。由您正在搜索的Dictionary键索引将大大缩短查找时间。

于 2013-01-28T20:12:56.730 回答
2

对另一个列表中的每个项目在列表上进行线性搜索对于大型数据集来说效率不高。最好将键放入可以更有效地搜索的表或字典中，以允许您连接两个表。你甚至不需要自己编写代码，你想要的是一个Join操作。您希望从每个映射到相同键的每个序列中获取所有项目对。

要么拉出下面方法的实现，要么将其更改为适当的类型Foo并将Bar其用作方法。

public static IEnumerable<Tuple<Bar, Foo>> Merge(IEnumerable<Bar> pACList
    , IEnumerable<Foo> pList)
{
    return pACList.Join(pList, item => item.Key.ToString()
        , item => item.CompanyID.ToString()
            , (a, b) => Tuple.Create(a, b));
}

您可以使用此调用的结果将这两个项目合并在一起，因为它们将具有相同的键。

在内部，该方法将创建一个查找表，以便在实际进行搜索之前进行有效搜索。

于 2013-01-28T20:36:17.130 回答
1

  1. 将 pList 转换为 HashSet，然后查询 pHashSet.Contains()。复杂度 O(N) + O(n)

  2. 在 CompanyId 上对 pList 进行排序并执行 Array.BinarySearch() = O(N Log N) + O(n * Log N )

  3. 如果 Max company id 不是太大，只需在第 i 个位置存在具有公司 id i 的项目时创建它们并对其进行数组。没有什么比这更快了。

其中 N 是 pList 的大小，n 是 pACList 的大小

于 2013-01-28T20:15:51.153 回答