[erlang-questions] how are implemented lists?

Benoit Chesneau bchesneau@REDACTED
Fri May 22 09:33:24 CEST 2015


Hi,

On Fri, May 22, 2015 at 9:09 AM Erik Søe Sørensen <eriksoe@REDACTED> wrote:

> The "Erlangic" solution would, I think, be to
> - have a process which holds the data;
> - have one table (sorted_set) which contains {Time, Key}, where Time is
> some unique monotonously increasing value (now(), or the recently
> introduced replacement);
> - have another table (set) which contains {Key, Time, Value}.
> The process owns the tables, and inserts/deletes from both on each update.
> In-process data structures could be used instead of tables.
> This gives O(log(N)) update time.
>
Indeed I thought about it, but was afraid it would require to increst the
limit of the number of ETS tables in my case and I am not sure what does it
imply at the moment. The number of queues can be indeed higher than the
current limit.

> Optimizations can be made, but I'd have to know more about the usage
> pattern before I'd go into that...
>

For now I have a process that maintains a queue of items on which I am
doing selective receive to fetch from and append to some items to a queue
using the queue module.  Due to some events an item could have been already
handled on another node I need to discard it in the queue.

Right now to handle that I keep a list of the discarded items apart and
when the discarded item is fetched on queue I ignore it and ask for a new
item. With the drawback that I have to keep a place of where the items are
queued. So i was thinking to have a data structure that would allows me to
quickly check a if the item to discard is queued on that node/process and
then remove it or mark it as removed (The other way to do it would be
filtering the queue  and return the new filtered queue but It would be
quite inefficient imo). Not sure what's the best data structure for it if
it exists.

I guess having an ordset + dict (or maps) - or something like it - could
also do the trick you define above without requiring an ETS but I not sure
if it will perform the same.

Thanks
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20150522/7b8d0d22/attachment.htm>


More information about the erlang-questions mailing list