I need to solve a very large
O(10^10) linear selection problem in a distributed memory machine, is there any library that will solve it for me?
In shared memory machines, e.g.
std::nth_element does it in average
O(n) but deterministic
O(n) algorithms also exist. I could live with something worse as long as it's easy to implement. I would also prefer for it to work on input iterator/input ranges than to have linear complexity in order to save memory. I have a dataset that I want to postprocess and then use as input to the linear selection algorithm, it would be better if I could do it "on the fly". I also only want to solve the linear selection problem for certain values, and wouldn't care to solve it multiple times, once for each value.