[erlang-questions] Ordered set with lower_bound
Igor Ribeiro Sucupira
Fri Oct 9 02:05:10 CEST 2009
Indeed, I "have hoped for O (1) after the first O (log N) 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.
So, ets:lookup/2, maybe followed by ets:next/2, would do.
Thanks for the answers.
On Thu, Oct 8, 2009 at 8:32 PM, Paul Mineiro <paul-trapexit@REDACTED> wrote:
> On Thu, 8 Oct 2009, Igor Ribeiro Sucupira wrote:
>> I need some ordered set that allows me to "search and then iterate"
>> efficiently. In other words, I need this functionality:
>> After looking at the documentation for gb_sets and ordsets, I have
>> concluded that Erlang does not provide that functionality and I'll
>> have to roll my own. Is it the right conclusion? :-)
> ets:next/2 on an ordered_set table acts like that. "efficiently" ...
> well, it'll be O (log N) per call, you might have hoped for O (1) after
> the first O (log N) call. also you might not like the constant factors.
> benchmark to be sure.
> -- p
> p.z. perhaps ets:slot/2 is faster?
> erlang-questions mailing list. See http://www.erlang.org/faq.html
> erlang-questions (at) erlang.org
"The secret of joy in work is contained in one word - excellence. To
know how to do something well is to enjoy it." - Pearl S. Buck.
More information about the erlang-questions