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

Question

在阅读我的解释之前，我想告诉您，我需要优化处理时间来比较两个巨大的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，其性能差异可以忽略不计。

Answer 1

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

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

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

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

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

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

我的列表都没有自动重叠范围（注释）

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