in reply to Re^2: Better algorithm or data structure?
in thread Better algorithm or data structure?

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.)

  • Comment on Re^3: Better algorithm or data structure?

Replies are listed 'Best First'.
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.
[reply]

In Section Seekers of Perl Wisdom