Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling

Re^2: Removing redundant powersets with minimal RAM

by jimt (Chaplain)
on Nov 03, 2006 at 19:16 UTC ( #582146=note: print w/replies, xml ) Need Help??

in reply to Re: Removing redundant powersets with minimal RAM
in thread Removing redundant powersets with minimal RAM

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.

  • Comment on Re^2: Removing redundant powersets with minimal RAM

Replies are listed 'Best First'.
Re^3: Removing redundant powersets with minimal RAM
by Anonymous Monk on Nov 03, 2006 at 22:12 UTC
    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?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://582146]
Discipulus manual work: i just tell the same to my boss: every time the quick solution is to assign some manual data entry task to my group.. because we have not direct access to many databases here..
[LanX]: point is: in high speed trade each bank has to remember what he has to get from the others... so dresdner got billed for losses but couldn't claim gains
Discipulus is this the IT?
[Corion]: Discipulus: Well, in many cases it doesn't make sense to build an interface and complicated program just to enter 20 rows into a database ;) But yes, automating data imports should pay off in the long run
[LanX]: Choroba: this happened before I joined, was still in uni, but my boss was summoned to the CEO of the second biggest German bank at that time and could only say " I told them its not ready" ;)
[LanX]: memories....I missed my connection while chatting
[Discipulus]: in this case Corion we are speaking about software licensing: evry year or two we must rescan the whole ced to produce an excel report, while at every activation / disactivation we update a black box DB: i said that i a week i can produce the perl to..
[Discipulus]: rend out the xls IF i have access to the DB
[choroba]: LanX I miss working in a bank sometimes...
[Corion]: Discipulus: Ooof. Especially yearly things are things I like to automate instead of trying to remember how I did things last year...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (12)
As of 2017-03-29 12:04 GMT
Find Nodes?
    Voting Booth?
    Should Pluto Get Its Planethood Back?

    Results (350 votes). Check out past polls.