通用列表性能优化

Question

我正在尝试优化通用列表的算术运算。 我有3个可空双精度列表，如下所定义。

List<double?> list1 = new List<double?>();
List<double?> list2 = new List<double?>();
List<double?> listResult = new List<double?>();

int recordCount = list1.Count > list2.Count ? list2.Count : list1.Count;

for (int index = 0; index < recordCount; index++)
{
      double? result = list1[index] + list2[index];
      listResult.Add(result);
}

有没有办法在处理大量列表时使这个操作运行更快？

谢谢你的参与。

- Alan B

---

你是如何在将它们相加之前填充列表的？如果数据来自数据库，从数据库获取结果求和会更快。 - Jeremy Thompson

你知道如果这两个列表的大小不同，这段代码会产生ArrayOutOfBoundsException吗？ - juergen d

@juergend 不，他首先找到哪个列表更短 -- 第5行。 - Jay

你能利用数据并行性吗？（即你是否拥有多核CPU？） - mattypiper

是的，我正在四核上运行它。 - Alan B

Answer 1

如果我的列表很大，有没有办法使这个操作运行得更快？

你可以将结果的列表创建移动到计数之后：

List<double?> list1 = new List<double?>();
List<double?> list2 = new List<double?>();

int recordCount = list1.Count > list2.Count ? list2.Count : list1.Count;
List<double?> listResult = new List<double?>(recordCount);

这将让您指定结果所需的确切容量，并避免列表内部的重新分配。对于“巨大列表”，这可能是最慢的部分之一，因为随着列表变得越来越大，内存分配和复制将是最慢的操作。

另外，如果计算简单，您可以潜在地使用多个核：

List<double?> list1 = new List<double?>();
List<double?> list2 = new List<double?>();

int recordCount = list1.Count > list2.Count ? list2.Count : list1.Count;

var results = new double?[recordCount]; // Use an array here

Parallel.For(0, recordCount, index => 
    {
        double? result = list1[index] + list2[index];
        results[index] = result;
    });

考虑到这里的“工作”非常简单，为了充分利用并行性能，您可能需要定制分区器（详见如何：加快小循环体速度）：

var results = new double?[recordCount]; // Use an array here
var rangePartitioner = Partitioner.Create(0, recordCount);

Parallel.ForEach(rangePartitioner, range => 
    {
        for (int index = range.Item1; index < range.Item2; index++)
        {
            results[index] = list1[index] + list2[index];
        }
    });

如果这不是瓶颈，你可以使用LINQ来将其转换为一行代码：

var results = list1.Zip(list2, (one, two) => one + two).ToList();

然而，如果性能真的是瓶颈，那么这将比自己处理循环略微低效。

- Reed Copsey

---

我非常确定列表realloc会使用某种类型的增长/指数/斐波那契/其他扩展增长系统，所以可能并不像你想象的那么糟糕。但是我同意只分配一次是一个很好的优化，并且也很容易实现。 - mattypiper

@mattypiper 是的 - 它从4个元素开始，每次加倍。然而，对于非常大的列表来说，这可能是昂贵的，因为每次重新分配都需要复制现有列表。 - Reed Copsey

由于该操作非常简单，因此并行改进可能是最有可能导致性能提高的方法，假设您正在运行具有多个核心、处理器或超线程的系统。 - Craig Suchanec

@CraigSuchanec 是的-但是由于这么简单，它可能需要一个自定义分区器...我要进行编辑。 - Reed Copsey

@CraigSuchanec 已完成 - 如果工作确实如此简单，那么这将更好。 - Reed Copsey

Answer 2

如果您提前知道列表的大小，那么简单数组应该运行得更快。可以像这样创建：

double?[] Array1 = new double?[10];

- Steve Wellens

Answer 3

你可以做的第一件事是指定结果列表的容量。

List<double?> listResult = new List<double?>(recordCount);

这将预先分配结果空间，节省每次List.Add()调用的时间。

如果你真的担心性能问题，可以将列表分成块，并启动多个线程来处理部分结果集，然后在完成时将完整集合合并在一起。

- Mike Parkhill

Answer 4

var result = from i in
            Enumerable.Range(0, Math.Min(list1.Count, list2.Count))
            select list1.ElementAtOrDefault(i) + list2.ElementAtOrDefault(i);
foreach (var item in result)
{
Debug.Write(item.Value);
}

- Jeremy Thompson

Answer 5

如果您有能力使用原始数组而不是列表，那么肯定可以使其更快 - 具体多快取决于您想要降到多低级别。在纠正了您源代码中的一些错误后，我编写了三个不同版本。其中一个按照您的代码方式，通过创建结果新列表（我利用了它的容量构造函数，避免了大量的中间分配）。

我还编写了一个将两个数组相加并生成第三个数组的版本，从去掉 List 的视角来提高效率。

最后，我编写了一个使用不安全代码和指针将第一个数组添加到第二个数组的版本。

比较结果如下：

Timings: 500000 iterations of 10000-item lists
  Lists:           00:00:13.9184166
  Arrays (safe):   00:00:08.4868231
  Arrays (unsafe): 00:00:03.0901603

Press any key to continue...

我使用的代码可以在这个Github Gist中找到。

不安全的代码可能会过度优化，但是看到这三个示例之间的差异还是很明显的。为了清晰起见，我建议坚持使用安全的代码并使用数组。

- Ben