Perl-Sensitive Sunglasses PerlMonks

### Re: searching a vector array

by BrowserUk (Pope)
 on Jun 09, 2011 at 19:12 UTC ( #908986=note: print w/replies, xml ) Need Help??

in reply to searching a vector array

,but how to do a multi intersection and to do it efficiently,

Finding the intersection of multiple bit vectors is just a case of bitwise-anding them together:

#! perl -slw use strict; our \$V //= 20; our \$L //= 72; my @vecs = map { pack 'C*', 0xf0, map rand( 256 ), 1 .. ((\$L-8) / 8)+1; } 1 .. \$V; printf "%2d : %s\n", \$_, unpack 'b*', \$vecs[ \$_ ] for 0 .. \$#vecs; my \$intersect = \$vecs[ 0 ]; \$intersect &= \$vecs[ \$_ ] for 1 .. \$#vecs; printf "** : %s\n", unpack 'b*', \$intersect; __END__ C:\test>908952 -L=64 -V=40 0 : 00001111101000110111011000000010111100010110001010101011010111010 +0011011 1 : 00001111110100001011011011110111100101000011000101101101000101000 +1110011 2 : 00001111001111110100011011101111000101010000111001011110011010110 +0001111 3 : 00001111001000110011101001010110001010000100010010011101110100011 +1101100 4 : 00001111101010011111111001111101000101100110100111101011100100101 +0010000 5 : 00001111111101111101100001000001101011100110011110001111100010010 +0001110 6 : 00001111110010001001011000101100100001101101001110111010100100110 +1100111 7 : 00001111100100010011101101001100011000111101110001111011010000110 +0010011 8 : 00001111011010110100010000011011000111100001010001000110010110100 +1100110 9 : 00001111000000101001110101010101000001110011101001101110001000101 +0101101 10 : 00001111010000111101010000001101110000001100111000100010110101110 +0000101 11 : 00001111110010001000011100110111011110000011111101100010100111100 +0011111 12 : 00001111100110111100010100010111110101110110110111100001100111111 +1100000 13 : 00001111100011111011010101001110111111101001011110001001000001010 +1111101 14 : 00001111111110111001011010110110101100111110011100101111101101000 +1010001 15 : 00001111100110101110001110010011101000110110010100001110110011101 +1111101 16 : 00001111111011110001110011001001011010000100000110111101001111111 +1110101 17 : 00001111001111111010001010001100010010010100100000101111001100111 +0011010 18 : 00001111011000100101001101001101100101001011010001011001000100100 +1011101 19 : 00001111110110100111001101000010101100011000000000100010001111001 +1011101 20 : 00001111010010011101111110100011111011100110101011100111111111111 +1100011 21 : 00001111011001101110110110100001111111101100011100111101011011011 +0011111 22 : 00001111111110110000011110110000011001011100101101010011001111010 +1110111 23 : 00001111111110001000010001011000010011100111101010001000011001001 +0101100 24 : 00001111010010000000111110001101000011010010000101110010111001101 +0000110 25 : 00001111100111000000010000101010101010111000111111010110011010001 +0011101 26 : 00001111001010011000010010011010111111111000111111000001110010110 +0110001 27 : 00001111011011011100101111011010011010010010100110110001110100100 +0111000 28 : 00001111010101110010000011001011111100010001011101000101000001100 +1101100 29 : 00001111100100010001000111010011010100101110101000110111010101101 +0111010 30 : 00001111101110101011011111001101010010001100010010010100001110011 +0000101 31 : 00001111011011000011101101101010001000100010000011101011111100010 +0010000 32 : 00001111110010010011000011110111100100001100011110111111000001110 +0010101 33 : 00001111100011101101101110000110001111011101110101001001100111111 +0001010 34 : 00001111011011000111000100100001100101111000100110010001010011110 +1000111 35 : 00001111111111010000010010100101101101110110100111101110101110010 +0011100 36 : 00001111101100010100001101001000010111000000011011111011001001010 +0000011 37 : 00001111001010001000111101001011110011000001001000011000100010111 +1100101 38 : 00001111001001000100110000111110001011011001011100011011101011101 +0110101 39 : 00001111000111101110011001010100101101001101110110111010111001110 +0101001 ** : 00001111000000000000000000000000000000000000000000000000000000000 +0000000

And that's an O(N) (and very efficient O(N)) process. Or have I misread you?

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.

Create A New User
Node Status?
node history
Node Type: note [id://908986]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (6)
As of 2017-12-15 02:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What programming language do you hate the most?

Results (415 votes). Check out past polls.

Notices?