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

[MacPerl] next



According to Strider:
> 
> First, I'd like to thank everyone for being so helpful. I thought I knew a
> decent amount about Perl- but I haven't worked with large memory chunks
> before. =)
> 
> So- this can't sort, because of a memory error, even if perl is given 20mb
> of RAM. I can't see WHAT could be going wrong. Maybe this is normal... I
> hope not.

Ya Welcome!  :-)  (As I'm sure everyone else is mentally saying too.)

Hmmmmmmmm............

Why not sort it as you read it in?  Especially if you are
attempting to read in a great deal of information at one
time.  Look up the SPLICE and SHIFT commands.  SPLICE takes
things out of an array, SHIFT puts things into an array.

So, let's say you had ten records: 7 9 4 0 2 3 1 6 5 8

You read in the first record and just stick it into the
array.  Then you begin your loop.  You read in the next
record and start by looking at the first record.  If it is
less than that record you just do a SHIFT to insert it
before that record (because you are at the first record).
If the value is greater than that number you go to the last
entry in the array and check against that number (which
right now is still "7").  Since the value is greater than
that value, you simply add it to the end of the array (ie:
$data[++$#data] = $input).  Eventually, you will get to a
point where the number read in is somewhere in the middle.
What you do about that is to simply do the old divide and
conquer routine.  That is to say: You have a low value, a
high value, and a median value.  You check to see if the
new value is higher or lower than the median and adjust the
high or low values accordingly.  Once you get to where the
high (or low) value is only one place away from the median,
you know where to put the next number.  For example:

	Let's say you've gotten through reading things in
	up to the zero (0).  This means the next number to
	read in is the two (2).  Ok, you get into a loop to
	check things out.  The loop looks like this:

	while( $input = <INPUT> ){
		$low = 0;
		$high = $#data;
		$median = ($low + $high)/2;
		$theFlag = 1;
		while( $theFlag > 0 ){
			$theFlag = 0;
			if( $data[$median] > $input ){
#
#	I'm leaving this blank so you can try figuring out how to do this.  :-)
#
#	Rules:
#
#		Since the median number (which, in our case would be 1
#		[which means we are pointing at four (4)])
#		is greater than our input (ie: 2), then the $high value
#		must become the $median value (so $high goes from being
#		three (3) to being one (1)).  Then all we have to do is
#		to reset the flag back to one ($theFlag = 1;) so we can
#		pass through the loop again.
#
#		However, inside of the IF statement, we also have to
#		do another check.  This check is to see if we are only
#		one step away from the median.  Since the median has to
#		be reset to be one-half of whatever $low and $high is
#		and since $low is zero (0) and $high is only one (1),
#		then the median is going to wind up being zero.  Which
#		is only one step away from $high.  So we then know
#		that we need to insert the new number after the median
#		or before the $high location.  Which means that we also
#		have to reset the flag to zero ($theFlag = 0;) because
#		actually - we are through with the WHILE loop.
#
				}
				elsif( $data[$median] < $input ){
#
#	Do the same for here only you are working with the $low
#	value.
#
					}
				else {
#
#	If the values are not lower and they are not higher,
#	then they must be equal.  So just insert it after or
#	before the median.
#
					}
		}

The above loop will actually work even if you only have one
entry put into the array (ie: the 7).  It just seemed a bit
much to do an entire WHILE loop for only the first two
entries.  :-/

Have fun!  :-)

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