how to select random elements of a Data.Set?
Dear all, how would I quickly select an element of a Set (as in Data.Set) uniformly at random? Via the API, this can only be done in linear time? (via toList) If I could access the tree structure, then of course it could be logarithmic. But probably I'd need a weighted selection sooner or later, and this would require some specific code anyway. Or does it not? Actually I need a sequence of such selections (each selected element is deleted immediately). I don't need all elements (so, computing a random permuation might be too much). J.W.
On Fri, Jul 20, 2012 at 01:24:57PM +0000, jwaldmann wrote:
Dear all,
how would I quickly select an element of a Set (as in Data.Set) uniformly at random?
Via the API, this can only be done in linear time? (via toList) If I could access the tree structure, then of course it could be logarithmic.
If you had access to the Set constructors, this would be very easy, as each node caches a size. Unfortunately there does not appear to be any way to do this in sub-linear time via the exposed API, because there is no way to directly access the subtrees. I wonder about the wisdom of exporting a function like -- | Partition a set into two approximately equal-sized subsets. -- If @divide s == (s1,s2)@, then -- * @s1 `intersect` s2 == empty@ -- * @s1 `union` s2 == s@ -- * The sizes of @s1@ and @s2@ differ by at most a constant factor -- (currently, 3). divide :: Set a -> (Set a, Set a) which would give you enough to implement what you want, without breaking the Set abstraction. (However, even though technically it doesn't break any abstraction, it still smells somewhat "implementation-dependent"...) -Brent
There was recently a proposal to add indexing operators to Data.Set.
Until it is accepted, you can simulate Set with Map like this
import Data.Map
type Set a = Map a ()
Data.Map already has indexing operations (e.g. elemAt, deleteAt).
* jwaldmann
Dear all,
how would I quickly select an element of a Set (as in Data.Set) uniformly at random?
Via the API, this can only be done in linear time? (via toList) If I could access the tree structure, then of course it could be logarithmic.
But probably I'd need a weighted selection sooner or later, and this would require some specific code anyway. Or does it not?
Actually I need a sequence of such selections (each selected element is deleted immediately). I don't need all elements (so, computing a random permuation might be too much).
J.W.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Roman I. Cheplyaka :: http://ro-che.info/
Am 20.07.2012 15:24, schrieb jwaldmann:
Dear all,
how would I quickly select an element of a Set (as in Data.Set) uniformly at random?
If you use a "Map a ()" (or Map a a) you can use Map.elemAt. The initial conversion is still linear, though. -- | convert a set into an identity map setToMap :: Ord a => Set.Set a -> Map.Map a a setToMap = Map.fromDistinctAscList . List.map (\ a -> (a, a)) . Set.toList HTH C.
Via the API, this can only be done in linear time? (via toList) If I could access the tree structure, then of course it could be logarithmic.
But probably I'd need a weighted selection sooner or later, and this would require some specific code anyway. Or does it not?
Actually I need a sequence of such selections (each selected element is deleted immediately). I don't need all elements (so, computing a random permuation might be too much).
J.W.
participants (4)
-
Brent Yorgey -
Christian Maeder -
jwaldmann -
Roman Cheplyaka