Perl: the Markov chain saw 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 drinking their drinks and smoking their pipes about the Monastery: (5)
As of 2017-08-21 10:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (321 votes). Check out past polls.

Notices?