Investigate optimizing some OrderBy().Take calls to use a PriorityQueue
#96.277 aberto em 22 de dez. de 2023
Métricas do repositório
- Stars
- (17.886 stars)
- Métricas de merge de PR
- (Mesclagem média 12d 11h) (661 fundiu PRs em 30d)
Description
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.