Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
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.


Comment on Re: searching a vector array
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://908986]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (19)
As of 2015-07-30 20:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (273 votes), past polls