Finding the lowest element greater or equal than
Hello all, 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. 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.
Hi Martin,
What you want depends on more details. If you just have a list of items,
you can access its first item which is less than some "n" by doing:
headMay (filter (< n) xs)
Would this solution satisfy you? If not -- what condition would not be met?
You mentioned something regarding that with ordered list you'd have to
traverse half of the list on average. What did you mean by that? (I mean,
if you have ordered list, then either its first element is what you need,
or none of them are)
On Wed, Mar 18, 2015 at 11:49 PM, martin
Hello all,
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.
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. _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
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
participants (3)
-
Bob Ippolito -
Konstantine Rybnikov -
martin