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 PAA00386; Mon, 2 Sep 2002 15:10:23 +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 PAA32633 for ; Mon, 2 Sep 2002 15:10:22 +0200 (MET DST) Received: from nwkea-mail-1.sun.com (nwkea-mail-1.sun.com [192.18.42.13]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g82DAKr01009 for ; Mon, 2 Sep 2002 15:10:20 +0200 (MET DST) Received: from eastmail2.East.Sun.COM ([129.148.1.241]) by nwkea-mail-1.sun.com (8.9.3+Sun/8.9.3) with ESMTP id GAA29899 for ; Mon, 2 Sep 2002 06:10:19 -0700 (PDT) Received: from hue.East.Sun.COM (hue.East.Sun.COM [129.148.222.57]) by eastmail2.East.Sun.COM (8.9.3+Sun/8.9.3/ENSMAIL,v2.1p1) with ESMTP id JAA24996 for ; Mon, 2 Sep 2002 09:10:18 -0400 (EDT) Received: (from chuj@localhost) by hue.East.Sun.COM (8.11.6+Sun/8.11.6) id g82DAIb28805; Mon, 2 Sep 2002 09:10:18 -0400 (EDT) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15731.25402.232987.3449@gargle.gargle.HOWL> Date: Mon, 2 Sep 2002 09:10:18 -0400 From: john.chu@east.sun.com To: Caml-list@inria.fr Subject: [Caml-list] Holding a set of random integers of very wide range? In-Reply-To: References: <3D70203F.1000106@ozemail.com.au> X-Mailer: VM 7.00 under 21.1 (patch 9) "Canyonlands" XEmacs Lucid Reply-To: john.chu@east.sun.com Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Diego Olivier Fernandez Pons writes: > If you give me some more informations (on typical ranges that you can > find in unicode subsets) I will be able to give more precise answers This brings up a possibly related question that I have. For reasons I tried to explain in a previous draft of this e-mail and has been cut due to the amount of space it took, I need to generate multiple permuted lists of integers ranging from 0 to approximately 2^100 (or more, it's a bit open-ended unfortunately). Since I only need one value at a time, I can use a lazy list for this. i.e., the head holds a value and the tail is a suspension of the state I need to generate the next value. No big deal there. The big deal, for me anyways, is that the state I need is tracking the integers that I've already used (so that I don't generate the same one twice) given that the range of possible values is so large. I'm currently using the very low-tech solution of maintaining a list of ranges of used values. (i.e., when I use a value that would link 2 different ranges, I go coalesce the list. The worst case would be if I picked all the odd integers or all the even integers.) Given the recent talk of Patricia trees and bit sets, I was wondering if some variant of either one of those, or some other representation would be better for what I'm doing? (I figure at the very least I ought to be using a tree of ranges of used values. I'm currently using the Big_int module to represent my integers.) BTW, it's extremely unlikely I will ever need every single value in the lazy list. I will probably have queried the garbage collector and declared defeat long before then. I'm hoping that, at worst, I will need only several thousand values from each permuted list. But I don't want to precompute them since I may not need several thousand values from some lists and others might need more. So I want to generate only the numbers that are necessary. (Sorry, this bit only makes sense if you knew what I'm using this for. The short description would be backtracking to find a set of variable values which satisfy a bunch of contraints where there can be multiple possible solutions of which I want a random one where variable values can be mapped onto a potentially very large range of integers. I'm applying as many constraints before backtracking as possible to reduce the state space to search.) Thanks. john ------------------- 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