[erlang-questions] how are implemented lists?

[Erik Søe Sørensen]

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.
Optimizations can be made, but I'd have to know more about the usage
pattern before I'd go into that...
/Erik
Den 21/05/2015 18.00 skrev "Benoit Chesneau" <bchesneau@REDACTED>:

>
>
> On Wed, May 20, 2015 at 9:58 AM Håkan Mattsson <hm@REDACTED> wrote:
>
>> On Tue, May 19, 2015 at 5:27 AM, Richard A. O'Keefe <ok@REDACTED>
>> wrote:
>>
>>>
>>> If it weren't for the "concurrent" bit I'd suggest that
>>> one of the set or dictionary data structures in stdlib
>>> might be useful, or one of the Okasaki purely functional
>>> data structures that I thought had been adapted to
>>> Erlang, but can't find.
>>>
>>
>> Perhaps you ar looking for the queue module?
>>
>> It is quite useful when you want to have a list where popping elements
>> from the tail is efficient.
>>
>> /Håkan
>>
>>
> Thanks all for your answers, it's really useful
>
> In fact I wasn't thinking directly to use ETS at first. The geneeral idea
> was indeed to have a sort of queue (pop or tail functions) but with the
> ability to remove one item from it if needed with a performance better than
> O(N). Which is if I understand correctly the case with  a list. In my
> understanding a skip list algorithm would do the trick. Maybe there are
> another data-structure for it that would work better with Erlang?
>
> - benoit
>
>
>>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20150522/3f41a271/attachment.htm>