in reply to Searching parallel arrays.

I have the idea of implementing something like a modified Boyer-Moore search on your data structure, but your description and data don't match:

The rule is each array contains a sorted (ascending) sequence of non-contiguous, unique integers, but my @a3 = ( 205, 206, 315 ); contains the two contiguous numbers 205 and 206.

If the data is wrong and the description is right, my algorithm would be to

  1. Take a look at the highest number of the four numbers at the start of the array. This highest number must be present in the sequence, as every array can only contribute one number/entry to the sequence, per sequence. This assumption/consequent is wrong, see Not a Number's reply below.
  2. Then, move forward in the other three arrays up to that number-3, by using a binary search.
  3. Then, look at the number found by the binary search, or if not found the next greater entry. By definition, there are no duplicates, so the elements in the arrays are all different and all equal or greater than $number-3.
  4. Look at the four numbers now. If they make up a sequence all is well. Otherwise, remove all the previous smaller elements from the arrays and start over at step 1.

I think this algorithm optimizes discarding non-matches over finding matches.

Replies are listed 'Best First'.
Re^2: Searching parallel arrays.
by Not_a_Number (Prior) on Dec 08, 2006 at 15:46 UTC

    I'm not sure I fully understand, but wouldn't that approach fail for a configuration like this:

    my @a1 = ( 1, 3, 5 );
my @a2 = ( 2, 4, 6 );
my @a3 = ( 205, 207, 315 );
my @a4 = ( 206, 208, 314 );

    [download]
[reply]
[d/l]

      Indeed - my approach will fail for such configurations, thanks for pointing that out!

[reply]
Re^2: Searching parallel arrays.
by BrowserUk (Patriarch) on Dec 08, 2006 at 20:54 UTC

    Corion++ You're right. My description was lacking in clarity. I was trying to indicate that any sequence of four values found would definitely be spread across 2 or more of the arrays.

    In this case, the example is king.

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]

In Section Seekers of Perl Wisdom