[erlang-questions] Tuples referencing each other problem
Grzegorz Junka
list1@REDACTED
Mon Sep 25 08:35:43 CEST 2017
Fair enough, I missed that you can set ordered_set in ETS, but
nevertheless it won't work with maps. However, even if I use ETS the Key
is still stored twice, isn't? (once as the key for ordered_set, once as
the value when the Id is the key).
On 24/09/2017 16:43, Jesper Louis Andersen wrote:
> Of course it will work: the ETS table is an ordered_set. This ensures
> that you have Term order. Now, in Erlang, numbers and thus integers
> have order less than everything else. In short, min/1 is given by a
> call to ets:first/1. To get max, we observe that the atom 'x' is not
> part of your keys, nor part of the integers. So it is larger than any
> integer. If we ask ets:prev/2 on that 'x', we get max/1.
>
> This covers the range operations on IDs. For the range operations on
> keys, it is even easier because they already have sorted order. You
> can also get rather fast traversal by using ets:select/1,2 and using
> the continuations to walk the data set in larger chunks.
>
> On Sun, Sep 24, 2017 at 6:02 PM Grzegorz Junka <list1@REDACTED
> <mailto:list1@REDACTED>> wrote:
>
> Thanks but that won't work. As mentioned keys must be sorted so
> that I can quickly query for range from min/max key. I could add
> an index but in that case the key would be stored twice, once in
> the index and once in the value, which I wanted to avoid.
>
> GrzegorzJ
>
>
> On 24/09/2017 15:29, Jesper Louis Andersen wrote:
>> Consider an ETS table and insert
>>
>> [{Key, Id}, {Id, Key}]
>>
>> This ensures fast lookup in both directions. Alternatively, run
>> this in a map. I often do this when mapping monitor references in
>> code.
>>
>> On Sat, Sep 23, 2017 at 3:50 PM Grzegorz Junka <list1@REDACTED
>> <mailto:list1@REDACTED>> wrote:
>>
>> Zipper looks interesting but I don't think it would suit
>> here. Keeping
>> paths to leafs could work but since the tree is dynamic those
>> paths
>> would often change and it would be very difficult to update
>> paths that
>> have already been stored.
>>
>> In short, I have keys, which may be any Erlang terms, and
>> numerical Ids
>> assigned to those terms. Keys must be sorted. Numerical Ids are
>> increasing monotonically. Then the following lookups should
>> be efficient:
>>
>> 1. Having a key quickly search for its numeric Id
>> 2. Having a numeric Id quickly get back the key
>>
>> Also the following conditions should be met:
>>
>> 3. The same key should be always assigned the same numeric Id
>> 4. One key has always one numeric Id (and vice versa), so
>> they are
>> always added or removed together
>>
>> Since keys can be of any length I don't want to store them
>> more than
>> once. And since they must be sorted I was thinking about
>> using a B+Tree.
>> Then another structure to map the numeric Id back to their keys.
>>
>> An obvious solution would be to make the B+Tree bidirectional
>> - the key
>> would be recreated by traversing the tree back from a leaf to
>> the root.
>> The other structure would then need to keep a mapping between the
>> numeric Id and the reference to the leaf for the key
>> corresponding to
>> that numeric Id.
>>
>> But an equally valid solution would be to tag all nodes of
>> the B+Tree
>> with numbers and store tags to parents in their children. Then in
>> another structure, e.g. an array, the mapping between the tag
>> and its
>> node. That would also allow to traverse the tree backward
>> from leafs to
>> the root.
>>
>> GrzegorzJ
>>
>>
>> On 22/09/2017 00:37, Richard A. O'Keefe wrote:
>> >
>> >
>> > On 22/09/17 2:23 AM, Grzegorz Junka wrote:
>> >> To answer your question Richard, I don't actually need a
>> cyclical
>> >> structure. As I mentioned, this is a simplification of a
>> more specific
>> >> problem. I didn't want to describe all the specifics to
>> ask a question.
>> >> I need to design a tree, a variant of a HAMT tree, but
>> which can be
>> >> traversed in both directions, from the root to leafs and
>> from leafs to
>> >> the root (independently, i.e. starting from a reference to
>> a leaf rather
>> >> than recursively).
>> >
>> > Of course this pushes back the question a further step.
>> > Why do you want to traverse the tree in both directions?
>> >
>> > Might the "zipper" approach be any use?
>> >
>> > If you want references to leaves, such references could be
>> paths.
>> > I used that technique once in a programming language that used
>> > reference counting, so that link cycles meant no collection.
>> > (Yes, I know modern reference-based collectors have solved that
>> > problem.) I've also used that technique for processing XML in
>> > a pure functional language.
>> >
>> > In an imperative context, that doesn't work very well
>> because the
>> > tree structure might change. The DOM suffers from trying
>> to make
>> > this "work" in some sense, but trying to iterate over a graph
>> > while something else is changing it is never going to be easy.
>> >
>> > It is possible that the Haskell "Functional Graph Library"
>> > may be relevant to your needs.
>> >
>> > _______________________________________________
>> > erlang-questions mailing list
>> > erlang-questions@REDACTED
>> <mailto:erlang-questions@REDACTED>
>> > http://erlang.org/mailman/listinfo/erlang-questions
>>
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED <mailto: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/20170925/bc6d2c3d/attachment.htm>
More information about the erlang-questions
mailing list