[Date Prev][Date Next][Thread Prev][Thread Next] [Search] [Date Index] [Thread Index]

Re: [MacPerl] Got it...



Mark Manning/Muniz Eng. writes:
|		$theFlag = 0;
|		for( $i=0; $i<=$#data; $i++ ){
|			if( $data[$i] eq $_ ){
|				$theFlag = 1;
|				break;
|				}
|			}
|		next if $theFlag > 0;
|		$data[++$#data] = $_;
|		}

This is on the right track. However, it's still O(n^2). If you keep
@data sorted, you can do a binary search and reduce the run time to
O(nlogn). For a 4.7mb file, this will probably be a big win. It might
also pay to keep it in a tree instead of a list, so perl isn't having
to scoot big numbers of array elements around when you insert a new
string. Of course you could always just keep a hash: $data{$_} = 1
automatically uniqify's the data, but then you have the overhead of
the hash. But that's almost always the trade-off you make: speed vs.
memory.

Brian

***** Want to unsubscribe from this list?
***** Send mail with body "unsubscribe" to mac-perl-request@iis.ee.ethz.ch