为什么在 Select 之前 运行 LINQ OrderBy 需要更多时间?
Why does it take more time when you run a LINQ OrderBy before Select?
在编写编码问题的解决方案时,我发现我的 LINQ 语句有一个有趣的行为。我有两种情况:
第一个:
arr.Select(x => x + 5).OrderBy(x => x)
第二个:
arr.OrderBy(x => x).Select(x => x + 5)
在使用 System.Diagnostics.Stopwatch 进行一些测试后,我得到了长度为 100_000 的整数数组的以下结果。
对于第一种方法:
00:00:00.0000152
第二个:
00:00:00.0073650
现在我很想知道为什么我先点菜会花更多的时间。我在 google 上找不到东西,所以我自己想了想。
我最终得到了 2 个想法:
1. 第二种情况要转成IOrderedEnumerable再转回IEnumerable,而第一种情况只需要转成IOrderedEnumerable,不需要转回。
2. 你最终有 2 个循环。第一个用于排序,第二个用于 selecting,而方法 1 在 1 个循环中完成所有操作。
所以我的问题是为什么在 select 之前完成订购需要更多时间?
根据您拥有的Linq-provider,可能会对查询进行一些优化。例如。如果您使用某种数据库,您的提供者很可能会为类似于此的两个语句创建完全相同的查询:
select myColumn from myTable order by myColumn;
因此无论您是在 Linq 中先排序还是先 select 排序,性能都应该是相同的。
因为这里似乎没有发生这种情况,您可能使用了根本没有优化的 Linq2Objects。所以你的语句的顺序可能会产生影响,特别是如果你有某种使用 Where
的过滤器,它会过滤掉很多对象,这样后面的语句就不会对整个集合进行操作。
长话短说:差异很可能来自某些内部 initialzation-logic。由于 100000 个数字的数据集并不是很大 - 至少不够大 - 即使一些快速初始化也会产生很大影响。
让我们看一下序列:
private static void UnderTestOrderBySelect(int[] arr) {
var query = arr.OrderBy(x => x).Select(x => x + 5);
foreach (var item in query)
;
}
private static void UnderTestSelectOrderBy(int[] arr) {
var query = arr.Select(x => x + 5).OrderBy(x => x);
foreach (var item in query)
;
}
// See Marc Gravell's comment; let's compare Linq and inplace Array.Sort
private static void UnderTestInPlaceSort(int[] arr) {
var tmp = arr;
var x = new int[tmp.Length];
for (int i = 0; i < tmp.Length; i++)
x[i] = tmp[i] + 5;
Array.Sort(x);
}
为了执行基准测试,让我们 运行 10
次并平均 6
中间结果:
private static string Benchmark(Action<int[]> methodUnderTest) {
List<long> results = new List<long>();
int n = 10;
for (int i = 0; i < n; ++i) {
Random random = new Random(1);
int[] arr = Enumerable
.Range(0, 10000000)
.Select(x => random.Next(1000000000))
.ToArray();
Stopwatch sw = new Stopwatch();
sw.Start();
methodUnderTest(arr);
sw.Stop();
results.Add(sw.ElapsedMilliseconds);
}
var valid = results
.OrderBy(x => x)
.Skip(2) // get rid of top 2 runs
.Take(results.Count - 4) // get rid of bottom 2 runs
.ToArray();
return $"{string.Join(", ", valid)} average : {(long) (valid.Average() + 0.5)}";
}
是时候 运行 看看结果了:
string report = string.Join(Environment.NewLine,
$"OrderBy + Select: {Benchmark(UnderTestOrderBySelect)}",
$"Select + OrderBy: {Benchmark(UnderSelectOrderBy)}",
$"Inplace Sort: {Benchmark(UnderTestInPlaceSort)}");
Console.WriteLine(report);
结果:(酷睿 i7 3.8GHz,.Net 4.8 IA64)
OrderBy + Select: 4869, 4870, 4872, 4874, 4878, 4895 average : 4876
Select + OrderBy: 4763, 4763, 4793, 4802, 4827, 4849 average : 4800
Inplace Sort: 888, 889, 890, 893, 896, 904 average : 893
我没有看到任何 显着差异,Select + OrderBy
似乎比 OrderBy + Select
更有效(大约 2% 的增益)。然而,Inplace Sort 远优于 性能(5
times)比任何 Linq。
在编写编码问题的解决方案时,我发现我的 LINQ 语句有一个有趣的行为。我有两种情况:
第一个:
arr.Select(x => x + 5).OrderBy(x => x)
第二个:
arr.OrderBy(x => x).Select(x => x + 5)
在使用 System.Diagnostics.Stopwatch 进行一些测试后,我得到了长度为 100_000 的整数数组的以下结果。
对于第一种方法:
00:00:00.0000152
第二个:
00:00:00.0073650
现在我很想知道为什么我先点菜会花更多的时间。我在 google 上找不到东西,所以我自己想了想。
我最终得到了 2 个想法:
1. 第二种情况要转成IOrderedEnumerable再转回IEnumerable,而第一种情况只需要转成IOrderedEnumerable,不需要转回。
2. 你最终有 2 个循环。第一个用于排序,第二个用于 selecting,而方法 1 在 1 个循环中完成所有操作。
所以我的问题是为什么在 select 之前完成订购需要更多时间?
根据您拥有的Linq-provider,可能会对查询进行一些优化。例如。如果您使用某种数据库,您的提供者很可能会为类似于此的两个语句创建完全相同的查询:
select myColumn from myTable order by myColumn;
因此无论您是在 Linq 中先排序还是先 select 排序,性能都应该是相同的。
因为这里似乎没有发生这种情况,您可能使用了根本没有优化的 Linq2Objects。所以你的语句的顺序可能会产生影响,特别是如果你有某种使用 Where
的过滤器,它会过滤掉很多对象,这样后面的语句就不会对整个集合进行操作。
长话短说:差异很可能来自某些内部 initialzation-logic。由于 100000 个数字的数据集并不是很大 - 至少不够大 - 即使一些快速初始化也会产生很大影响。
让我们看一下序列:
private static void UnderTestOrderBySelect(int[] arr) {
var query = arr.OrderBy(x => x).Select(x => x + 5);
foreach (var item in query)
;
}
private static void UnderTestSelectOrderBy(int[] arr) {
var query = arr.Select(x => x + 5).OrderBy(x => x);
foreach (var item in query)
;
}
// See Marc Gravell's comment; let's compare Linq and inplace Array.Sort
private static void UnderTestInPlaceSort(int[] arr) {
var tmp = arr;
var x = new int[tmp.Length];
for (int i = 0; i < tmp.Length; i++)
x[i] = tmp[i] + 5;
Array.Sort(x);
}
为了执行基准测试,让我们 运行 10
次并平均 6
中间结果:
private static string Benchmark(Action<int[]> methodUnderTest) {
List<long> results = new List<long>();
int n = 10;
for (int i = 0; i < n; ++i) {
Random random = new Random(1);
int[] arr = Enumerable
.Range(0, 10000000)
.Select(x => random.Next(1000000000))
.ToArray();
Stopwatch sw = new Stopwatch();
sw.Start();
methodUnderTest(arr);
sw.Stop();
results.Add(sw.ElapsedMilliseconds);
}
var valid = results
.OrderBy(x => x)
.Skip(2) // get rid of top 2 runs
.Take(results.Count - 4) // get rid of bottom 2 runs
.ToArray();
return $"{string.Join(", ", valid)} average : {(long) (valid.Average() + 0.5)}";
}
是时候 运行 看看结果了:
string report = string.Join(Environment.NewLine,
$"OrderBy + Select: {Benchmark(UnderTestOrderBySelect)}",
$"Select + OrderBy: {Benchmark(UnderSelectOrderBy)}",
$"Inplace Sort: {Benchmark(UnderTestInPlaceSort)}");
Console.WriteLine(report);
结果:(酷睿 i7 3.8GHz,.Net 4.8 IA64)
OrderBy + Select: 4869, 4870, 4872, 4874, 4878, 4895 average : 4876
Select + OrderBy: 4763, 4763, 4793, 4802, 4827, 4849 average : 4800
Inplace Sort: 888, 889, 890, 893, 896, 904 average : 893
我没有看到任何 显着差异,Select + OrderBy
似乎比 OrderBy + Select
更有效(大约 2% 的增益)。然而,Inplace Sort 远优于 性能(5
times)比任何 Linq。