in reply to Efficient selection mechanism?

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.

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]

      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]

In Section Seekers of Perl Wisdom