[Camllist] Explaining bit sets
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20020902 (13:10) 
From:  john.chu@e... 
Subject:  [Camllist] Holding a set of random integers of very wide range? 
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 email 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 openended 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 lowtech 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 camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners