On Wed, Mar 18, 2015 at 2:49 PM, martin
I want to find the lowest element in a collection of items which is greatet or equal to a given element. There can be more than one such element in which case I wouldn't care which one I get. I still want to be able to iterate over the elements following the found element. In a way I want the equivalent of
select ... from table where table.x > n
How would I do this efficiently?
I tried using an ordered list, but I would still have to traverse half the list on average.
You could do it in log time (using a binary search algorithm) with an ordered Vector or Array. Lists are not an appropriate data structure for random access.
I suppose I can do this with some sort of tree, but i don't want to write all the code myself. But I couldn't find anything off the shelf.
Data.Map supports that operation in log time with splitLookup. You can use the values of the map to count the occurrences of a given element. If all of the elements are unique you can save a bit of space and use Data.Set instead, which has a splitMember function. -bob