dotnet/runtime

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

開放

#96,277 建立於 2023年12月22日

 (12 則留言) (6 個反應) (0 位負責人)C# (5,445 個分叉)batch import
area-System.Linqhelp wantedtenet-performance

倉庫指標

星標
 (17,886 顆星)
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.

貢獻者指南