dotnet/runtime

Investigate optimizing some OrderBy().Take calls to use a PriorityQueue

Open

#96,277 创建于 2023年12月22日

在 GitHub 查看
 (12 评论) (6 反应) (0 负责人)C# (5,445 fork)batch import
area-System.Linqhelp wantedtenet-performance

仓库指标

Star
 (17,886 star)
PR 合并指标
 (平均合并 12天 11小时) (30 天内合并 661 个 PR)

描述

Order/OrderBy.Take is currently an O(N log N) operation that allocates an array of length N and keeps all the data around until the relevant portion of the data is consumed. With a PriorityQueue, however, for OrderBy(...).Take(T) this would instead be O(N log T), and it would only need to keep space proportional to T, not N, so if T is significantly smaller than N (which in typical use is the case, often with a small T value passed to Take), this could lead to significant throughput and memory consumption benefits.

Variations of this with OrderByDescending are also possible. It'd also be possible to accomodate OrderBy().Skip(S).Take(T); the priority queue would then need to maintain S+T values, so the benefits would diminish as S grew. However, from an algorithmic complexity perspective, S+T <= N, which means O(N log (S+T)) <= O(N log N). Of course, we'd still need to be careful, since the constants here do matter from a throughput perspective.

贡献者指南