Re: Compare two arrays of simple numbers

That can be solved in linear time with an auxiliary array.

sub comp {
 my ($a, $b) = @_;
 return 0 if @$a != @$b;
 my @c;
 ++$c[$_] for @$a;
 --$c[$_] for @$b;
 $_ != 0 && return 0 for grep defined, @c;
 return 1;
}
[download]

Comment on Re: Compare two arrays of simple numbers Download Code

Replies are listed 'Best First'.
Re^2: Compare two arrays of simple numbers by erroneousBollock (Curate) on Oct 03, 2007 at 08:27 UTC
return 0 if @$a != @$b; Well that's (worst case) `O(n)` right there. :-) Does `!=` even have a meaning in list context ? Update: Ouch, I'm so wrong it's ridiculous. -David	[reply] [d/l] [select]
Re^3: Compare two arrays of simple numbers by Prof Vince (Friar) on Oct 03, 2007 at 08:36 UTC
Well that's (worst case) O(n) right there. :-) That's what linear means. Does != even have a meaning in list context ? Edit: It doesn't force scalar context, but seems to compare array lengths. See : `sub zero { return (0, 0) } print +(zero() == 2) ? "scalar\n" : "list\n"; my @a = (0, 1); my @b = (1, 0); my @c = (0, 2 , 1); print +(@a == @b) ? "same length\n" : "not\n"; print +(@a == @c) ? "same length\n" : "not\n";` [download] Anyway, I think perl doesn't actually build the lists and directly optimize that to the array size, which should make it constant time.	[reply] [d/l]