Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Removing redundant powersets with minimal RAM

by Anonymous Monk
on Nov 03, 2006 at 19:00 UTC ( #582138=note: print w/ replies, xml ) Need Help??


in reply to Removing redundant powersets with minimal RAM

I just need a clever way to do the search to reduce the number of checks for the cases where they don't match or there are large sets involved.

There can't be large sets involved.

A tiny little set with only 100 elements has a power set of size 2^100. It would take 952,589,676,412,928 GB just to store a bit vector of that many elements.


Comment on Re: Removing redundant powersets with minimal RAM
Re^2: Removing redundant powersets with minimal RAM
by jimt (Chaplain) on Nov 03, 2006 at 19:16 UTC

    Re-read my post - the whole point is not to store the powerset anywhere. A set with only 100 elements in my scheme needs to be stored only once. That's 13 bytes in a bit vector. The powerset is implied by checking against subsets of it using bitwise & operations.

    The problem is when there are multiple sets, there are multiple checks. 500 sets of 100 elements each only require 6.5k to store in memory, but require up to 500 checks to determine if the set I'm currently working with is a subset of any of them. It's that searching through those sets I want to speed up.

      To succinctly state the original problem, given a set of sets, generate the powerset for all sets but remove all duplicates.

      I guess I'm confused by your stated purpose.

      If you actually generate the power set of just one set with 100 elements (let alone try to consider how it iteracts with any other set!), you'll output a power set consisting of 1,267,650,600,228,229,401,496,703,205,376 elements.

      Where are you going to put this power set once you generate it? It's not like you can store it on your hard drive. It won't fit on any storage device I can concieve of. You certainly can't read it off the screen. I'm confused. :-(

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://582138]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (5)
As of 2014-07-13 11:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (249 votes), past polls