•Re: Pair of items

If you know the items are always sorted, there's a routine that's likely to be faster than anything else shown here as I post this:

my $ok = no_common_item_in_these_numeric_sorted_lists(
  [1, 2, 3],
  [2, 4, 6]
);

sub no_common_item_in_these_numeric_sorted_lists {
  my @x = @{+shift}; # these are copies
  my @y = @{+shift};
  ## presuming numeric sorted
  while (@x or @y) {
    shift @x, next if not @y or $x[0] < $y[0];
    shift @y, next if not @x or $x[0] > $y[0];
    return 0; # not ok - we found an identical item
  }
  return 1; # ok - we found no identical items
}
[download]

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.

Comment on •Re: Pair of items Download Code

Replies are listed 'Best First'.
Re: •Re: Pair of items by Simpleton (Initiate) on Jul 31, 2003 at 07:12 UTC
I believe that'd have to be: `while (@x and @y) {` Otherwise it goes into an infinite loop if every element in @x is less than every element in @y.	[reply] [d/l]
•Re: Re: •Re: Pair of items by merlyn (Sage) on Jul 31, 2003 at 11:59 UTC
No, if every element of @x is less than the first element of @y, then all of @x first gets nibbled element by element because of the first statement within the loop, then all of @y gets nibbled element by element because of the second statement within the loop, and then we drop out of the loop. Perhaps you're arguing that I can optimize that to "and". Probably true. But it doesn't break even when it's an "or", unless I'm missing something. I constructed this loop by thinking about loop invariants, a very valuable tool. In this case, we know that no pair of equal numbers can ever get shifted off the lists, and yet we are shifting while we are looping, so we're always moving closer to either an equal pair, or two empty lists. -- Randal L. Schwartz, Perl hacker Be sure to read my standard disclaimer if this is a reply.	[reply]
Re: •Re: Re: •Re: Pair of items by Simpleton (Initiate) on Aug 09, 2003 at 02:25 UTC
Actually, it gets nibbled down by the first statement, and then keeps nibbling at the empty @x because `$x[0] < $y[0]` is true even if @x is empty. Feed the subroutine `([1,2,3], [4,5,6])` and it never exits.	[reply] [d/l] [select]


Perl-Sensitive Sunglasses
	PerlMonks