Re: Efficient selection mechanism? (Thank you all)

Thank you all for your suggestions.

As oiskuu demonstrated, the bit mapped index -- as suggested by Corion, Salva, Choroba & hdb -- is hands down winner in the performance stakes.

By using vec and string-wise boolean operations (Salva,Choroba) rather than numeral ops, I don't have to worry about the size of the small integers outgrowing the platform integer size, which is a slight but possible consideration.

Mixing code from various solutions, this is what I'm using:

use constant MAX   => 20;
use constant BLANK => chr(0) x ((MAX / 8) + 1);
...
    my $key = BLANK;
    vec( $key, $_, 1 ) = 1 for @$_;
    $cache{ $key } = $_;
...
    my @subsel = grep{ ( $_ & $mask ) eq BLANK } keys %cache;
[download]

And that's it. Thank you all.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

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.

Comment on Re: Efficient selection mechanism? (Thank you all) Download Code

Replies are listed 'Best First'.
Re^2: Efficient selection mechanism? (Thank you all) by choroba (Cardinal) on Jan 15, 2014 at 12:18 UTC
I learnt the craft of vec from you here on PerlMonks. لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ	[reply]
Re^3: Efficient selection mechanism? (Thank you all) by BrowserUk (Patriarch) on Jan 15, 2014 at 12:47 UTC
Sometimes, you just need to see your problem through someone else's eyes. I'd been faffing around with multi-level hashes so that given the first quad's numbers I could use them to index down four levels to just that subset that didn't contain those four numbers. Which ought to work, but proved to be clumsy and produced a huge, unwieldy data structure. But the real problem is that once I've found the second non-overlapping quad I then want to find a third that doesn't overlap either of the first two; then a fourth that doesn't overlap any of the first three. And that requires two more, deeper, multi-level data structures be built. With the vec solution I just OR the masks and grep the previous subset again to produce the next. Simple once you've seen it, but I was so locked in on my multi-level hash approach that using bitmasks didn't cross my mind. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' 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]


Perl: the Markov chain saw
	PerlMonks