* Re: [Caml-list] Map that maintains insertion-order on keys
2016-07-14 18:44 ` Christoph Höger
@ 2016-07-14 19:07 ` Jesper Louis Andersen
2016-07-14 19:10 ` Gabriel Scherer
1 sibling, 0 replies; 5+ messages in thread
From: Jesper Louis Andersen @ 2016-07-14 19:07 UTC (permalink / raw)
To: Christoph Höger; +Cc: caml users
[-- Attachment #1: Type: text/plain, Size: 2600 bytes --]
Perhaps this can be built out of smaller data structures.
Clearly the representation [k1, v1; k2, v2; ...; kn, vn] is a map with the
property, but most operations are in the order of O(n) and thus wholly
unsatisfactory for any map with more than, say, 500 elements.
If you don't need persistence, my intuition would be to use Janes St. Core
and then build it out of Doubly_linked and Map from Core. The idea is that
the map values are elements of the doubly linked list, we wrap Map and
maintain the DL list as well. Then the insertion order can be handled by
the DL list, so asking for the ordered keys is just walking the list in the
direction desired. This keeps the asymptotics of the Map since operations
on the DL list are O(1).
There might be a direct implementation of this idea, but I'll defer that to
people who write OCaml on a daily basis :)
If you *do* need persistence, one way is to keep two maps. One maps a
sequence number to a key. The other maps a key to a pair of a sequence
number and a value. The triple of (sequence_no, order_map, map) should be
persistenly maintainable, under the price of a factor 2 efficiency loss.
Better (functional) data structures may exist for this problem, but I don't
know about them from memory alone.
On Thu, Jul 14, 2016 at 8:44 PM, Christoph Höger <
christoph.hoeger@tu-berlin.de> wrote:
> Am 14.07.2016 um 20:35 schrieb Jesper Louis Andersen:
> > Hi,
> >
> > Could you give some small example of what you want or a more precise
> > definition? I can think of at least 3 ways to parse meaning out of
> > "gives keys in order of insertion", and I don't know which you might
> want.
>
> What I mean is that a map that is created by consecutive Map.add
> applications, yields the keys in the order of the add() applications, i.e.
>
> Map.keys (Map.add k_n v_n (Map.add k_(n-1) v_(n-1) (Map.add ... (Map.add
> k_1 v_1 Map.empty))))) =!= [k_1; ...; k_(n-1); k_n]
>
> it could also yield [k_n; k_(n-1); ... ;k_1], that does not matter that
> much.
>
>
>
>
>
> --
> Christoph Höger
>
> Technische Universität Berlin
> Fakultät IV - Elektrotechnik und Informatik
> Übersetzerbau und Programmiersprachen
>
> Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin
>
> Tel.: +49 (30) 314-24890
> E-Mail: christoph.hoeger@tu-berlin.de
>
> --
> Caml-list mailing list. Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
--
J.
[-- Attachment #2: Type: text/html, Size: 3671 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Caml-list] Map that maintains insertion-order on keys
2016-07-14 18:44 ` Christoph Höger
2016-07-14 19:07 ` Jesper Louis Andersen
@ 2016-07-14 19:10 ` Gabriel Scherer
1 sibling, 0 replies; 5+ messages in thread
From: Gabriel Scherer @ 2016-07-14 19:10 UTC (permalink / raw)
To: Christoph Höger; +Cc: caml users
[-- Attachment #1: Type: text/plain, Size: 1762 bytes --]
You could use a pair of:
- a map and
- a list of weak pointers to keys with a count of present items and deleted
items (you would compact the list whenever there are more deleted items
than present items)
Why the counts: removing items from the list on deletion is too slow.
Why the weak pointers: using keys directly could increase their lifetime
after they have been deleted from the map.
If you don't need deletion, just a list of keys is fine.
On Thu, Jul 14, 2016 at 2:44 PM, Christoph Höger <
christoph.hoeger@tu-berlin.de> wrote:
> Am 14.07.2016 um 20:35 schrieb Jesper Louis Andersen:
> > Hi,
> >
> > Could you give some small example of what you want or a more precise
> > definition? I can think of at least 3 ways to parse meaning out of
> > "gives keys in order of insertion", and I don't know which you might
> want.
>
> What I mean is that a map that is created by consecutive Map.add
> applications, yields the keys in the order of the add() applications, i.e.
>
> Map.keys (Map.add k_n v_n (Map.add k_(n-1) v_(n-1) (Map.add ... (Map.add
> k_1 v_1 Map.empty))))) =!= [k_1; ...; k_(n-1); k_n]
>
> it could also yield [k_n; k_(n-1); ... ;k_1], that does not matter that
> much.
>
>
>
>
>
> --
> Christoph Höger
>
> Technische Universität Berlin
> Fakultät IV - Elektrotechnik und Informatik
> Übersetzerbau und Programmiersprachen
>
> Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin
>
> Tel.: +49 (30) 314-24890
> E-Mail: christoph.hoeger@tu-berlin.de
>
> --
> Caml-list mailing list. Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
[-- Attachment #2: Type: text/html, Size: 2647 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread