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 OAA23760; Tue, 27 Aug 2002 14:12:54 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA23623 for ; Tue, 27 Aug 2002 14:12:53 +0200 (MET DST) Received: from fichte.ai.univie.ac.at (fichte.ai.univie.ac.at [131.130.174.156]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g7RCCqf01634 for ; Tue, 27 Aug 2002 14:12:52 +0200 (MET DST) Received: (from markus@localhost) by fichte.ai.univie.ac.at (8.9.3/8.9.3/Debian 8.9.3-21) id OAA00778; Tue, 27 Aug 2002 14:12:43 +0200 Date: Tue, 27 Aug 2002 14:12:43 +0200 From: Markus Mottl To: "Yaron M. Minsky" Cc: Tibor Simko , caml-list@inria.fr Subject: Re: [Caml-list] intersecting huge integer sets Message-ID: <20020827121243.GC32176@fichte.ai.univie.ac.at> Mail-Followup-To: "Yaron M. Minsky" , Tibor Simko , caml-list@inria.fr References: <87n0r835w9.fsf@pcdh91.cern.ch> <1030450016.24909.45.camel@dragonfly.localdomain> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1030450016.24909.45.camel@dragonfly.localdomain> User-Agent: Mutt/1.4i Organization: Austrian Research Institute for Artificial Intelligence Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Tue, 27 Aug 2002, Yaron M. Minsky wrote: > If the sets are really as dense as you say they are (on the order of 50% > of all possible elements), then the fastest thing is probably just to > use a bool array. Such an approach would require 3 passes: one to set > all the elements of the array to false. One to mark the elements > corresponding to set 1 to true, and then one pass over set 2 to see > which of its elements are shared by 1. If this is what is needed, better take bit vectors ("bitv" - also on Jean-Christophe's page). Regards, Markus Mottl -- Markus Mottl markus@oefai.at Austrian Research Institute for Artificial Intelligence http://www.oefai.at/~markus ------------------- 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