Re:My Favorite Algorithm: Linear Time Median Finding
by cerved on Friday July 26, 2024 @07:45AM
(#41077810)
what's preventing you from doing it in one pass?
Re:My Favorite Algorithm: Linear Time Median Finding
by davidmurdoch on Friday July 26, 2024 @11:15AM
(#41079299)
Does C# have the plumbing for this built in? It's been 7 years since using it so I might not be remembering correctly.
Re:My Favorite Algorithm: Linear Time Median Finding
by neonsunset on Friday July 26, 2024 @12:17PM
(#41079854)
IEnumerable<T>.Max and .Min are the same as they were just significantly faster through the use of SIMD: https://github.com/dotnet/runtime/blob/ebbebaca1184940f06df6...
You could implement a similar (and simpler) fast path for types with contiguous memory by performing min and max per iteration instead.
Re:My Favorite Algorithm: Linear Time Median Finding
by davidmurdoch on Saturday July 27, 2024 @10:33AM
(#41086856)
I was thinking LINQ was optimized to do a single enumeration for cases such as this. Can LINQ be easily, naturally, and idiomatically used with `IEnumerable<T>.Max` and `.Min` to avoid looping twice, or is it more of a more rigorous and intentional optimization the engineer would have to seek out?
Re:My Favorite Algorithm: Linear Time Median Finding
by _dain_ on Friday July 26, 2024 @11:16AM
(#41079304)
What's wrong with doing it in two passes? N iterations each doing 2 operations is exactly the same cost as 2*N iterations each doing 1 operation. Because multiplication is commutative.
Re:My Favorite Algorithm: Linear Time Median Finding
by srcreigh on Friday July 26, 2024 @12:10PM
(#41079775)
It’s more like 2NM where M is loading the data from disk/memory. One pass is 2N+M.
Why go to the store and back twice to buy two things instead of buying two things in one trip? ;p
Re:My Favorite Algorithm: Linear Time Median Finding
by jiggawatts on Friday July 26, 2024 @08:01PM
(#41083439)
I think you meant 2N+2M vs 2N+M, but yes, that’s the point: not reading twice is cheaper because unlike in traditional big-O analysis compute is cheap but data access is very expensive.
Re:My Favorite Algorithm: Linear Time Median Finding
by srcreigh on Sunday July 28, 2024 @08:44AM
(#41092819)
Yep, thx.
Re:My Favorite Algorithm: Linear Time Median Finding
by buildbot on Friday July 26, 2024 @11:21AM
(#41079367)
This is true, but a big advantage of the single pass method is data reuse. Instead of loading each element twice, you load each element once. Per bit, reading/writing to external memory is massively more energy intensive than any compute op. Orders of magnitude more.
As an example: computing the .min() and .max() of an enumerable is two passes even though it could be done with one pass.
I'd love to see a language embrace a more efficient style similar to how a SQL does it, where you can elegant request this as a single pass over the data: "SELECT min(x), max(x) FROM y"