From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 87B5DBC2F for ; Sat, 27 Nov 2004 00:09:03 +0100 (CET) Received: from smtp2.wanadoo.fr (smtp2.wanadoo.fr [193.252.22.29]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id iAQN93ao023674 for ; Sat, 27 Nov 2004 00:09:03 +0100 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf0201.wanadoo.fr (SMTP Server) with SMTP id 217371C00456; Sat, 27 Nov 2004 00:09:03 +0100 (CET) Received: from nono (ARouen-106-1-19-12.w81-49.abo.wanadoo.fr [81.49.250.12]) by mwinf0201.wanadoo.fr (SMTP Server) with SMTP id B74541C00454; Sat, 27 Nov 2004 00:09:02 +0100 (CET) Message-ID: <018a01c4d40d$17084da0$0cfa3151@mshome.net> From: =?iso-8859-1?Q?Fr=E9d=E9ric_Gava?= To: "Christophe TROESTLER" Cc: References: <004f01c4d2fd$b87d6140$b18780d9@mshome.net><1101398012.9291.48.camel@pelican.wigram><008001c4d319$693f0f40$b18780d9@mshome.net> <20041125.193212.53142502.Christophe.Troestler@umh.ac.be> Subject: Re: [Caml-list] Objective Caml release 3.08.2 Date: Sat, 27 Nov 2004 00:10:15 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 X-Miltered: at concorde with ID 41A7B78F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; gava:01 gava:01 caml-list:01 sourceforge:01 ocaml:01 associative:01 tree:02 caml:02 tend:02 tend:02 guess:02 balanced:02 objective:02 frederic:03 frederic:03 X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr X-Spam-Status: No, score=2.2 required=5.0 tests=DNS_FROM_RFC_ABUSE, DNS_FROM_RFC_POST,DNS_FROM_RFC_WHOIS autolearn=disabled version=3.0.0 X-Spam-Level: ** > > 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" >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" >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.