优化两个非常大的列表的C#循环比较

问题描述 投票:2回答:1

在阅读我的解释之前,我想告诉您,我需要优化处理时间来比较两个巨大的c#列表,在嵌套循环中逐个索引进行比较。

当然是我使用C#创建的.Net Core应用程序。

在我的算法中,我必须创建一个包含某些整数范围的非常长的列表,如下所示。

internal class Global
{
    public string ChromosomeName { get; set; }
    public int start { get; set; }
    public int end { get; set; }
    public string Cluster { get; set; }
    public string Data { get; set; }
} 
var globals = new List<Global>();// somewhere in my method.

现在此列表将非常庞大,例如,它将具有这样存储的值。这是我的主要列表,因此其名称为'globals'

index 0 = start=1, end=400 ....
index 1 = start=401, end=800....
index (last) = start= 45090000 , end= 45090400 ...

这些只是粗略的估计值,因此您知道它将是一个巨大的清单。

现在在我的算法中,我实际上要做的是

  • 因此,我获取一个文本文件,读取该文件并将其数据存储在另一个列表中,该列表具有与代码中上面显示的属性完全相同的属性。
  • 现在我有2个列表,全局列表和我从文件中读取的其他列表。
  • 它们都是非常大的列表
  • 现在,我必须在嵌套循环中逐个索引地比较它们两者。
  • 外循环将迭代我的全局列表,而内循环将迭代我的其他列表(我从文件中读取)。
  • 一次完成嵌套循环后,我读取了另一个文件并创建了另一个列表,然后以相同的方式将该列表与全局列表进行比较。
  • 因此,将有一个全局列表,该列表将在嵌套循环中按索引进行索引比较,其中还有约10个以上的列表,它们几乎与全局列表本身一样大。

下面是为嵌套的foreach循环显示的伪代码。

foreach(var item in globals)
{
    var value=0;
    foreach(var item2 in otherHugeList)
    {
        compareMethod(item,item2);
        //below is the actual code of wht kind of comparison I am doing,     just if i guyx want to know, I am actually finding the overlap between two ranges.
       //value += Math.Max(0, Math.Min(range1.end, EndList[i]) -  Math.Max(range1.start, StartList[i]) + 1);
    }
}

我能做到这一点的最快方法是什么,因为现在要花几个小时以上,而我感到沮丧,我取消了该过程,因为我不知道要花多长时间。因此,我什至无法在较小的文件上得到结果。

我需要知道最快的方法,我应该使用任何与.Net core兼容的库吗?还是多线程?我对线程的概念并不满意。

P.S:我使用了Parallel.ForEach,其性能差异可以忽略不计。

c# list loops optimization .net-core
1个回答
6
投票

如果需要对两个列表分别进行10 6个元素的逐元素比较,则需要进行10 12个比较。它使您没有希望在相当长的时间内完成操作,因此解决此问题的关键是大大减少比较次数。

进行减少的确切方法取决于您正在运行的比较类型,所以让我们以帖子中的重叠计算为例。

[您知道,当以下陈述之一为真时,范围R和Q之间没有重叠:

  • R的上限低于Q的下限,或
  • R的下限高于Q的上限。

如果您的范围以随机顺序显示在列表中,则无济于事。但是,如果您对范围的下限进行排序,并按上限对关系进行解析,则将可以使用二进制搜索为您比较的每个范围找到列表的相关部分,即重叠的元素是可能。

假设同一列表上的范围之间几乎没有重叠,这将使比较次数从每个元素大约一百万减少到每个元素不到一百,从而使性能提高了1000倍。

我的列表都没有自动重叠范围(注释)

然后,您可以通过对两个范围列表进行排序,然后在单个循环中对其进行迭代,来使用merge algorithm的变体。将两个数组的索引设置为零,然后一次遍历两个列表。如果全局列表上的当前范围低于比较列表上当前范围的start级别,请继续前进到全局列表的下一个元素;否则,请移至比较列表的下一个元素。两个索引将彼此“追逐”,直到以2M为增量到达两个列表的末尾。

热门问题
推荐问题
最新问题