From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id GAA11823; Sat, 6 Dec 2003 06:08:08 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id GAA11209 for ; Sat, 6 Dec 2003 06:08:06 +0100 (MET) Received: from main.gmane.org (main.gmane.org [80.91.224.249]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hB6586129977 for ; Sat, 6 Dec 2003 06:08:06 +0100 (MET) Received: from list by main.gmane.org with local (Exim 3.35 #1 (Debian)) id 1ASUfl-0001Bu-00 for ; Sat, 06 Dec 2003 06:08:05 +0100 X-Injected-Via-Gmane: http://gmane.org/ To: caml-list@inria.fr Received: from sea.gmane.org ([80.91.224.252]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1ASUfk-0001Bm-00 for ; Sat, 06 Dec 2003 06:08:04 +0100 Received: from news by sea.gmane.org with local (Exim 3.35 #1 (Debian)) id 1ASUfk-0003tZ-00 for ; Sat, 06 Dec 2003 06:08:04 +0100 From: Alan Post Subject: [Caml-list] Re: how to calculate a "xor" Date: Sat, 6 Dec 2003 05:08:04 +0000 (UTC) Message-ID: References: <20031205200829.7e29a2c6.Damien.Pous@ens-lyon.fr> X-Complaints-To: usenet@sea.gmane.org User-Agent: slrn/0.9.7.4 (NetBSD) X-Loop: caml-list@inria.fr X-Spam: no; 0.00; damien:01 ens-lyon:01 damien:01 hashing:01 hash:01 wrote:03 linear:06 represented:07 lists:91 lists:91 function:09 decent:09 something:09 tables:10 sort:11 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk In article <20031205200829.7e29a2c6.Damien.Pous@ens-lyon.fr>, Damien wrote: > > Given two sets A and B, I want to calculate A\B _and_ B\A. The sets > are represented by lists. > > without using an order to sort the lists, is there something better > than the following (O(n^2)) ? If you have a decent hashing function, you can get expected linear time by putting the elements into hash tables. ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners