[erlang-questions] Ordered set with lower_bound
Richard O'Keefe
<>
Fri Oct 9 04:43:11 CEST 2009
On Oct 9, 2009, at 1:05 PM, Igor Ribeiro Sucupira wrote:
> Hello.
>
> Indeed, I "have hoped for O (1) after the first O (log N) call".
Just off the top of my head, gb_sets iterators give you O(1)
*amortised* time per call to next/1. So the
{geq,leq,range}_{reverse_,}iterator functions I sent in my
previous message give you in O(log N) time an iterator which
subsequently gives you O(1) *amortised* time per call.
> But, thinking again at my case, I don't really need the iterator.
> Given a key K, I believe it will be enough to find the smallest key
> that is greater or equals K.
The gb_set data structure, or any balanced tree, can do that in
O(log N) time too. With the functions in my previous message,
case gb_sets2:next(gb_sets2:geq_iterator(Set, K))
of {M, _} ->
M is the smallest element of Set that
is greater than or equal to K
; none ->
there is no such M
end
will do the trick. You can of course do it more efficiently than that,
but only by writing even more code inside the module.
>
>
More information about the erlang-questions
mailing list