Re^2: Better algorithm or data structure?

is it essential that elements of @sets be deleted, or would it suffice to keep the array a constant size, and "undef" elements when appropriate?

Yes. In use, new sets would be added to @sets on the fly. The mechanism is essentially a queue. New sets ("work items") are being continuously added asynchronously with the resources (represented by the booleans) becoming available. If I don't remove completed work items (sets for which all required resources have become available), then the queue would grow endlessly.

But your notion about using hashes is a good one. You've used a hash to index those sets that use a boolean against each boolean. You're undefing rather than splicing to avoid screwing up the indexing. But, if I also use a hash for holding the sets, I can delete a set from %sets, without screwing up the index. And that greatly reduces the number of sets that need to be examined for each boolean.

Thanks. I'll have a go at implementing that tomorrow.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

RIP an inspiration; A true Folk's Guy

Comment on Re^2: Better algorithm or data structure?

Replies are listed 'Best First'.
Re^3: Better algorithm or data structure? by graff (Chancellor) on Aug 30, 2010 at 00:53 UTC
Given this added detail: The mechanism is essentially a queue. New sets ("work items") are being continuously added asynchronously with the resources (represented by the booleans) becoming available. This poses another problem, because the "boolmap" structure will grow continuously. If the "sets" queue can grow to the point that the process blows up after a while, then the accumulation of hash keys in the "boolmap" structure is going to have the same effect. You'll need a little more code (and more execution time -- but hopefully not too much) to delete "boolmap" hash keys as the corresponding sets are deleted. And one more question, which might be unimportant, but the "boolmap" makes it relevant: When adding a new "set" to the queue, what if all the booleans in this set are already true? (Not that I'm curious about that, but it's something the implementation should take into account.)	[reply]
Re^4: Better algorithm or data structure? by BrowserUk (Patriarch) on Aug 30, 2010 at 01:17 UTC
the accumulation of hash keys in the "boolmap" structure is going to have the same effect. Indeed. But once I've found a set ready for removal from the queue, I have the resource identifiers (formerly boolean indexes), and so I know where in the boolmap to look, but I still need to locate the resource identifiers (formerly set indices), in order to remove them. So now the values within the boolmap have to also become hashes rather than arrays to avoid those linear searches. When adding a new "set" to the queue, what if all the booleans in this set are already true? The scope for this is limited, but still possible. The solution is that it is relatively easy to check whether there are any outstanding resources for a given set. If not, it can be processed straight away and doesn't need to be added to the queue. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. RIP an inspiration; A true Folk's Guy	[reply]