65.9K
CodeProject 正在变化。 阅读更多。
Home

不可变数组的 LINQ

Christopher Diggins
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.50/5 (5投票s)

2012年12月28日

MIT

6分钟阅读

viewsIcon

32553

downloadIcon

209

一个类似于 IEnumerable 的扩展方法库，用于处理不可变数组。

介绍 

本文介绍了一个用于处理不可变数组的接口 (IArray)，该接口保证在按索引访问元素或获取数组长度时具有 O(1) 的性能。 IEnumerable 的许多可用扩展方法也适用于 IArray，允许使用 LINQ 查询语法。 IArray 的性能明显优于使用 IEnumerable 扩展方法并将结果转换为 List。

背景  

在某些问题领域，例如 3D 图形，数组处理非常普遍。传统的处理数组的命令式编程技术可能容易出错且冗长。LINQ 所需的代码量大大减少，并且不易出错。不幸的是，LINQ 并非为数组数据类型进行了优化。当对 LINQ 查询生成的 IEnumerable 的结果需要恒定时间随机元素访问时，标准方法是将结果转换为列表或数组。

本文提出了一种新接口 (IArray) 和一组扩展方法，它们提供类似 IEnumerable 的 LINQ 风格方法和语法，但具有数组的性能特征。  

LINQ 

LINQ (Language Integrated Natural Query) 是一组技术，它允许 C# 代码在代码中包含 SQL 风格的查询。LINQ 专为轻松高效地查询数据集而设计。   

LINQ 有两种语法形式：查询语法和方法语法。C# 会自动将查询语法中的代码转换为方法语法。

查询语法： 

    from x in xs where x % 2 == 0 select x * 2 

方法语法：   

    xs.Where(x => x % 2 == 0).Select(x => x * 2) 

这种转换适用于任何数据源，无论它是否实现 IEnumerable。换句话说，如果 xs 支持 Where() 方法并返回一个支持 Select 方法的对象，则可以使用查询语法。IArray 实现利用了这一事实，允许它与 LINQ 查询语法表达式一起使用。  

IEnumerable  

IEnumerable 接口表示一个项目序列。IEnumerable 提供了许多操作来创建具有 O(1) 复杂度的全新序列，例如 Where()、Select()、Take()、Skip() 等。  

IEnumerable 接口具有元素访问 (ElementAt()) 和查询序列中项目数量 (Count()) 的操作，但除了非常特殊的情况外，它们的复杂度为 O(N)。在需要快速随机元素访问的情况下，IEnumerable 支持转换为 List (ToList()) 和 Array (ToArray())。

介绍 IArray

IArray 接口表示一个不可变数组，旨在用于单个元素访问时间恒定的上下文。IArray 具有两个公共只读属性：索引器属性和 count 属性，以及一个 CopyTo() 方法。

public interface IArray<T>
{
    int Count { get; }
    T this[int n] { get; }
    T[] CopyTo(int srcIndex, T[] dest, int destIndex, int len);
}

实现要求是两个属性都具有 O(1) 性能，并且集合在其生命周期内永远不会改变。

构建 IArray 实例

静态类 ImmutableArray 提供了以下用于创建数组的静态方法。

  • IArray<T> Create<T>(IList<T> xs)
  • IArray<T> Create<T>(params T[] args)
  • IArray<T> Create<T>(IEnumerable<T> xs)
  • IArray<T> Nil<T>()
  • IArray<T> Unit<T>(T x)
  • IArray<int> Range<T>(int count)
  • IArray<int> Range<T>(int from, int count)
  • IArray<T> Repeat<T>(T x, int n)
  • IArray<T> Repeat<T>(Func<T> f, int n)
  • IArray<T> Generate<T>(T first, Func<T, bool> invariant, Func<T, T> next)

已为列表、数组和 IEnumerable 实例添加了以下扩展方法以创建不可变数组。 

  • IArray<T> ToIArray<T>(this T[] xs) 
  • IArray<T> ToIArray<T>(this List<T> xs)
  • IArray<T> ToIArray<T>(this IEnumerable<T> xs) 

从数组或列表创建不可变数组时，会创建传入集合的副本。

介绍 ISortedArray 

IArray.OrderBy() 返回一个特殊接口，称为 ISortedArray。此接口具有优化方法，用于查找数组中元素的索引 (IndexOf()) 和检查项是否存在于数组中 (Contains())。这些方法使用二分搜索算法，复杂度为 O(LogN)。ISortedArray 接口还具有 O(1) 实现的 IsOrdered() 和 OrderBy() 方法。 

比较 IArray 和 IEnumerable 的性能 

下表包含 IArray 和 IEnumerable 上常见序列操作的复杂度分析： 

方法  IEnumerableIArray ISortedArray 
ElementAt   O(N)O(1)O(1)
Count O(N)O(1)O(1)
Select / Where O(1)O(N)O(N)
Aggregate  O(N)O(N)O(N)
Take / Skip O(1)O(N)O(N)
First  O(1)O(1)O(1)
Last O(N)O(1)O(1)
All / Any O(N)O(N)O(N)
ToArray / ToListO(N)O(N)O(N)
Min / Max / Sum / AverageO(N)O(N)O(1)
OrderBy O(1)O(NLogN)O(NLogN)
IndexOf O(N)O(LogN)O(LogN)
Contains O(N) O(LogN) O(LogN) 

当 O(1) 实际上等于 O(N) 时

某些返回序列的方法对于 IEnumerable 比 IArray 具有更好的复杂度分析。一些例子是 Select()、Where()、Take() 和 Skip()。如果程序员之后需要快速的随机元素访问，那么生成的 IEnumerable 必须使用 ToArray() 或 ToList() 转换为数组或列表。由于这两个操作的复杂度为 O(N)，因此此成本会主导任何基准测试。

基准测试方法 

为了公平地比较 IEnumerable 和 IArray 的性能，我分析了许多测试用例，这些测试用例包括执行操作和将结果转换为 List 的成本。

以下时间比较是通过对不同大小的输入序列运行测试来完成的。每个测试迭代都包括对结果的比较（不计入计时），以确保两个版本计算相同的结果。给定序列的整个基准测试限制为最多毫秒数。更高的数字表示执行测试所花费的执行时间。下面是负责计算时间的代码部分。

while ((DateTime.Now - start).TotalMilliseconds < MinTimeTrial)
{
    var inputA = gen(count);
    var inputB = inputA.ToIArray();
    var outputA = TimeFunction(() => f(inputA));
    var outputB = TimeFunction(() => g(inputB));
    tr.Result &= cmp(outputA.Item2, outputB.Item2);
    if (!tr.Result)
        throw new Exception("test failed");
    tr.TimeA += outputA.Item1;
    tr.TimeB += outputB.Item1;
}

基准测试结果 

中心

中间测试返回第一个和最后一个项目之间的中间项目。IArray 的复杂度为 O(1)，而 IEnumerable 的复杂度为 O(N)。

IEnumerable xs; xs.ElementAt(xs.Count() / 2);
IArray xs; xs[xs.Count / 2];
大小IEnumerableIArray
10 112.6231 11.2247
100 209.174 3.2049
1000  248.1513 0.424 
10000 251.5417 0.0772
100000 241.6906 0.0289 

Select

Select 测试将 IArray 的 Select() 方法与 IEnumerable 上的相同方法进行比较，然后使用 ToList 转换为列表。总的来说，IArray 的性能大约是 5 倍。
IEnumerable xs; xs.Select(x => x * 10).ToList();
IArray xs; xs.Select(x => x * 10);
大小IEnumerableIArray
10 130.4198 22.8207
100 203.7963 33.9568
1000 219.7549 41.9019
10000 222.4864 42.0895
100000 215.9494 42.8385

其中

Where 测试与 Select 测试类似。性能提升大约在 2.5 倍左右。
IEnumerable xs; xs.Where(x => x & 10 == 0).ToList();
IArray xs; xs.Where(x => x & 10 == 0);
大小IEnumerableIArray
10 87.7143 30.7792
100 169.0739 71.1118
1000 196.1686 83.7951
10000 197.5586 83.4241
100000 195.6574 82.8913

OrderBy

IArray 的 OrderBy 实现返回 ISortedArray 接口。
IEnumerable xs; xs.OrderBy(x => x).ToList();
IArray xs; xs.Where(x => x & 10 == 0);
大小IEnumerableIArray
10 222.2376 30.1089
100 335.6944 38.6848
1000 355.91 77.7343
10000 356.3396 93.0001
100000 400.4608 97.2454

更多基准测试 

在附件项目中，有大量的基准测试，展示了在许多场景中使用 IArray 的性能优势。IArray 的所有源代码也包含在内。

注意：请记住以发布模式编译，并在不附加调试器的情况下运行。

总结 

当程序员想使用 IEnumerable 但需要将其结果转换为数组或列表以获得快速索引时，IArray 可以是一个很好的高性能替代方案。

如果您发现代码或文章有任何错误，或者觉得代码有用，请告诉我，谢谢！  

© . All rights reserved.