English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Objective Caml release 3.08.2
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-11-26 (23:09)
From: Frédéric_Gava <frederic.gava@w...>
Subject: Re: [Caml-list] Objective Caml release 3.08.2
> > A Set.elements without ordering the elements would be more efficient.
> Show us!
Depending of your implementation of Set. In the case of balanced tree, ok,
the time will be the same but this is a special case:

>----- Original Message -----
>From: "skaller" <skaller@users.sourceforge.net>
>So I would tend to think it may well be worthwhile adding
>an unordered set to Ocaml. I guess some operations may
>change from O(log N) to O(1), or from O(N log N) to just O(N),
>eg fold.
----- Original Message -----
From: "Jon Harrop" <jon@jdh30.plus.com>
>Other useful set implementations which do not present elements in-order are
>possible, most notably a hashed set because it has significantly better
>average-case performance.

In the case of associative operator for the fold, the cost would be O(N/p)
in an parallel implementation of Set where p is the number of processors. I
would tend to think it may well be worthwhile.