[OT] Algorithm question

[Mike B Johnson via Digitalmars-d]

On Monday, 1 May 2017 at 04:15:35 UTC, H. S. Teoh wrote:
> I'm been thinking about the following problem, and thought I'd 
> pick the brains of the bright people around these parts...
>
> [...]


Since most real world problems would require selecting elements 
more than once it may be far more efficient to sort by 
P(x)(filter) then simply select a random element.

e.g.,

a = A.filter(x->P(x))  // Creates a new set a where only the 
elements of A that satisfy P(x) are added

...

e = a.random;


this is O(1) if you only have to filter once(you can create a 
container that always "sorts" on P(x) so to speak.. like a sorted 
dictionary).