Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re: multi-dimensional range lookup

by BrowserUk (Pope)
on May 08, 2007 at 20:14 UTC ( #614235=note: print w/replies, xml ) Need Help??


in reply to multi-dimensional range lookup

How many images are involved?

You can fully index the colors used in your images using 768 strings. The length of those strings will be one bit for every image. So, you can fully index 1,000,000 images using 96MB.

The data would be represented something like this:

$var = { red => [ 0 => b'0101011100010101111 ...', 1 => b'"1000111100010101100 ...', ... ], green => [ 0 => b'0101011100010101111 ...', ... ], blue => [ 0 => b'0101011100010101111 ...', ... ], };

To lookup all the images that contain red = 12, 13, 14, 15, and greenb = 78, 79, 80, 81 and blue = 23, 24, 25, 26, you simply bitwise-and (&) the appropriate 12 strings together, and then translate whatever bits are left set, back into the identities of the images. Very fast and very memory efficient also.


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: multi-dimensional range lookup
by Joost (Canon) on May 08, 2007 at 21:23 UTC
      ... your code will also match for rgb(2,2,4) etc.

      I do not believe so. Given,

      • picture 1 contains r=1, g=2, b=3
      • picture 2 contains r=2, g=3, b=4

      And assuming for simplicity, 3-bit/color images, the data would be encoded as

      my %lookup = { ## 0 1 2 3 4 5 6 7 red => [ 0b00, 0b10, 0b01*, 0b00, 0b00, 0b00, 0b00, 0b00, ], green => [ 0b00, 0b00, 0b10*, 0b01, 0b00, 0b00, 0b00, 0b00, ], blue => [ 0b00, 0b00, 0b00, 0b10, 0b01*, 0b00, 0b00, 0b00, ], };

      Anding the 3 bitstrings selected by rgb( 2,2,4 ) (* above) together

      0b01 & 0b10 & 0b01 == 00 ==> No hits.

      So, for the simple case of looking up one rgb value at a time, there is no overlap.

      For the more complex case of locating images that contain either rgb( 1,2,3 ) or rgb( 2,3,4 ), there is the problem that oring all six selected bitstrings together would also select rgb( 1,2,4 ) and rgb( 1,3,4 ) and rgb( 2,2,4 ) etc., but that is different from the problem description, which is more akin to r = 1 or 2 and g = 2 or 3, and b = 3 or 4, for which my code algorithm description would work correctly.

      For the case you describe, that of only matching those images that contain either rgb( 1,2,3 ) or rgb( 2,3,4 ), you have to do it in two separate operations. And the individual strings of the first 3 values together and extract the image identities from the result. Then do the second set of three and extract the image identities.

      It's and versus or.


      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.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (8)
As of 2021-06-24 21:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What does the "s" stand for in "perls"? (Whence perls)












    Results (132 votes). Check out past polls.

    Notices?