Version franēaise
Home     About     Download     Resources     Contact us    
Browse thread
Set union/inter/diff efficiency
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@e...>
Subject: Re: [Caml-list] Set union/inter/diff efficiency
    Bonjour,

> Does anyone have any ideas or references on how the union/inter/diff
> functions of the Set module could be optimised by accepting a
> sequence of sets rather than a pair at a time ?

No.

> For example, if A overlaps B overlaps C but A does not overlap C
> then it is probably quicker to compute the union "(A U C) U B"
> rather than "A U B U C".

I remember having discussed with Jean-Christophe Filliātre of the
[compare] implementation of Xavier Leroy. He noticed that it was a
smart lazy linearization of both sets.

In other words you can see it as if one had put a zipper on each set
and one calls when needed the [next] function.

A = 3 -> 5 -> 6 -> 7 -> 10
B = 3 -> 6 -> 8 -> 13

You can say that A < B at the second call of [next]

I suppose you could do a similar thing for union and intersection with
several sets

A = 3 -> 5 -> 6 -> 7 -> 10
B = 3 -> 6 -> 8 -> 13
C = 2 -> 4 -> 5 -> 6

You can call [next] in such a way that the pointers "jump" to an
interesting point. Here, it would be something like

max/min = 3
C -> 4 (first integer >= 3)
max/min = 4
A -> 5 (first integer >= 4)
max/min = 5
B -> 6 (first integer >= 5)
max/min = 6
C -> 6 (...)
A -> 6 (...)
=> output 6 in the intersection

> Better still, does anyone have a replacement Set module which
> implements this functionality?

I am not aware of any in Caml, SML or Haskell but I may be wrong.


        Diego Olivier