Programming Forums > Script Programming > Perl

TheAberrant · Jan 29th, 2008, 7:40 PM

The Story...
First post, so hoping to be clear and concise, but might end up wordy since it's pretty late at night.

I've got a parser that has time data along with some additional information contained within a number of logs. I'm creating a summary report of each log, based on information I parse out. One thing I do is determine the time difference between one item and the next, and want to print in this summary the highest five time differences (time difference and time data, as well as another field).

What I'm thinking...
Initially I thought I could use a 2-d Array and check the lowest number first (so $array[4]), and if it's less than that, continue on, if not then check the next element in the array until I find the element that it's less than. At that point I have to loop from the beginning again, shifting all elements down, and then copying the data appropriately.

Another idea was to continually add to the list, then sort every once in a while and just remove all but the top elements (this was something that would be easy to implement, but probably excessively CPU/memory intensive, as I go through about 10-12 thousand lines in each log). I had some other thoughts on Hashes and Linked Lists, but really not sure what the best solution would be. Am I heading in the right direction (so just code as I stated), or is there something easier (or possibly even already implemented...)

Thanks in advanced.

Sane · Jan 29th, 2008, 11:58 PM

So you have a list of values that you need sorted? And then the top 5 values outputted?

I'm confused, where does the problem lie? Why not sort the list of values using a predefined sort function, then output the top 5?

You mention having about 10-12 thousand lines though, so that could be a problem. This is what I would suggest...

Keep track of the best 5 results, in decreasing order. Read in one value at a time, and insert it into the best list if its better than at least the last result.

This method should be extremely fast (basically as fast as possible), and require virtually no memory.

Psuedocode Syntax (Toggle Plain Text)

best array [size 5] set to {-1,-1,-1,-1,-1}
 
for each "time difference"
 
    i = 5
    while (i > 0) and (time > best[i-1])
        i = i - 1
 
    if i < 5
        shift best elements [i ... 5] down to [i+1 ... 5]
        best[i] = time

Example Run:

(Toggle Plain Text)

Input: {1, 4, 0, 5, 2, 1, 3, 2, 1}

1 -> {1, -1, -1, -1, -1}

4 -> {4, 1, -1, -1, -1}

0 -> {4, 1, 0, -1, -1}

5 -> {5, 4, 1, 0, -1}

2 -> {5, 4, 2, 1, 0}

1 -> {5, 4, 2, 1, 1}

3 -> {5, 4, 3, 2, 1}

2 -> {5, 4, 3, 2, 2}

1 -> {5, 4, 3, 2, 2}

As you can see from the psuedocode, it's quite easy to implement. And the reason this is extremely fast, is because half the time nothing will happen to the values you feed it. If you have 12000 numbers, I'd wager at least 10000 of those will bounce right off the end of the array without being inserted. On average, almost all of the numbers will be less than the current best 5, so most numbers never even passes the first condition of the while loop.

Of the ones that do get searched and inserted, it's a maximum depth of 5 into the array, so the sift and shift operations are just a couple cycles on the CPU clock. It's easy, and trust me on this one, it's very fast.

Sane · Jan 30th, 2008, 12:58 AM

This is an interesting problem to think about...

Just an aside from further thought. Even if you were to have the worst-case scenario of increasing input, causing the sift and shift to constantly happen to the left-most element, it's not that big a deal. Every time you insert a new value, it's only 5 elements searched to the left, and 5 elements shifted to the right.

This is roughly the equivilent of looking at 10 elements in an array. Generalize this further, and it's as though you were reading the entire array 10 times in a row. Unsurprisingly, reading an array 10 times is faster than sorting that entire array (unless the array is very small). So even if you were fed sorted input, in an attempt to slow down your algorithm, this "semi-sort" still seems more than optimal. But if you were to increase the size of your best array, to say... 25, then the factor increases to 50 array walkthroughs. At which point, you might want to start rethinking the choice of algorithm.

TheAberrant · Jan 31st, 2008, 10:47 AM

Excellent, thanks for the help. The pseudocode was along the lines of what I wanted to do, so was able to implement it (though need to do some cleanup - right now my entire script is one main function, and is getting to be around 250 lines now). See code snippet below.

(Toggle Plain Text)

$i = $numSpikes - 1;
while (($i > 0) && ($timeDiff > $Spikes[$i-1][0]))
{
	$i--;
}

$x = $i;

if ($i < ($numSpikes - 1))
{
	# Shift everything below i down one 
	while ($i < ($numSpikes - 1))
	{
		$Spikes[$i+1] = $Spikes[$i];
		$i++;
	}

	$Spikes[$x][0] = $timeDiff;
	$Spikes[$x][1] = $tmpTime;
}

One question somewhat related - how do I clear or zero out the array? After each file, I need to reset - I can't think of an easy way other than looping through and setting all the values to zero. With C I'd just use memset - is there an equivalent function in perl?

Thanks

Sane · Jan 31st, 2008, 12:35 PM

I'm not sure if there's an equivilent in Perl, but a function won't buy you any extra time if you thought it might. The function itself still does exactly what one would intuitively expect; it will walk through each element setting each to zero. So it could be easier to write one yourself, then to go looking through the Perl docs for something already written. If you'd like to go searching, you should Google something along the lines of "setting/copying array memory in Perl".

TheAberrant · Feb 2nd, 2008, 1:40 PM

Figured it out - just do:

(Toggle Plain Text)

@Array = ();

That will basically remove everything in the array.

Jan 29th, 2008, 7:40 PM	#1
TheAberrant Newbie Join Date: Jan 2008 Posts: 9 Rep Power: 0	Question with Arrays - creating and updating 'top 5' list The Story... First post, so hoping to be clear and concise, but might end up wordy since it's pretty late at night. I've got a parser that has time data along with some additional information contained within a number of logs. I'm creating a summary report of each log, based on information I parse out. One thing I do is determine the time difference between one item and the next, and want to print in this summary the highest five time differences (time difference and time data, as well as another field). What I'm thinking... Initially I thought I could use a 2-d Array and check the lowest number first (so $array[4]), and if it's less than that, continue on, if not then check the next element in the array until I find the element that it's less than. At that point I have to loop from the beginning again, shifting all elements down, and then copying the data appropriately. Another idea was to continually add to the list, then sort every once in a while and just remove all but the top elements (this was something that would be easy to implement, but probably excessively CPU/memory intensive, as I go through about 10-12 thousand lines in each log). I had some other thoughts on Hashes and Linked Lists, but really not sure what the best solution would be. Am I heading in the right direction (so just code as I stated), or is there something easier (or possibly even already implemented...) Thanks in advanced.

Jan 29th, 2008, 11:58 PM	#2
Sane Programming Guru Join Date: Apr 2005 Posts: 1,722 Rep Power: 5	Re: Question with Arrays - creating and updating 'top 5' list So you have a list of values that you need sorted? And then the top 5 values outputted? I'm confused, where does the problem lie? Why not sort the list of values using a predefined sort function, then output the top 5? You mention having about 10-12 thousand lines though, so that could be a problem. This is what I would suggest... Keep track of the best 5 results, in decreasing order. Read in one value at a time, and insert it into the best list if its better than at least the last result. This method should be extremely fast (basically as fast as possible), and require virtually no memory. Psuedocode Syntax (Toggle Plain Text) best array [size 5] set to {-1,-1,-1,-1,-1} for each "time difference" i = 5 while (i > 0) and (time > best[i-1]) i = i - 1 if i < 5 shift best elements [i ... 5] down to [i+1 ... 5] best[i] = time best array [size 5] set to {-1,-1,-1,-1,-1} for each "time difference" i = 5 while (i > 0) and (time > best[i-1]) i = i - 1 if i < 5 shift best elements [i ... 5] down to [i+1 ... 5] best[i] = time Example Run: (Toggle Plain Text) Input: {1, 4, 0, 5, 2, 1, 3, 2, 1} 1 -> {1, -1, -1, -1, -1} 4 -> {4, 1, -1, -1, -1} 0 -> {4, 1, 0, -1, -1} 5 -> {5, 4, 1, 0, -1} 2 -> {5, 4, 2, 1, 0} 1 -> {5, 4, 2, 1, 1} 3 -> {5, 4, 3, 2, 1} 2 -> {5, 4, 3, 2, 2} 1 -> {5, 4, 3, 2, 2} Input: {1, 4, 0, 5, 2, 1, 3, 2, 1} 1 -> {1, -1, -1, -1, -1} 4 -> {4, 1, -1, -1, -1} 0 -> {4, 1, 0, -1, -1} 5 -> {5, 4, 1, 0, -1} 2 -> {5, 4, 2, 1, 0} 1 -> {5, 4, 2, 1, 1} 3 -> {5, 4, 3, 2, 1} 2 -> {5, 4, 3, 2, 2} 1 -> {5, 4, 3, 2, 2} As you can see from the psuedocode, it's quite easy to implement. And the reason this is extremely fast, is because half the time nothing will happen to the values you feed it. If you have 12000 numbers, I'd wager at least 10000 of those will bounce right off the end of the array without being inserted. On average, almost all of the numbers will be less than the current best 5, so most numbers never even passes the first condition of the while loop. Of the ones that do get searched and inserted, it's a maximum depth of 5 into the array, so the sift and shift operations are just a couple cycles on the CPU clock. It's easy, and trust me on this one, it's very fast. Last edited by Sane; Jan 30th, 2008 at 12:22 AM.

Jan 30th, 2008, 12:58 AM	#3
Sane Programming Guru Join Date: Apr 2005 Posts: 1,722 Rep Power: 5	Re: Question with Arrays - creating and updating 'top 5' list This is an interesting problem to think about... Just an aside from further thought. Even if you were to have the worst-case scenario of increasing input, causing the sift and shift to constantly happen to the left-most element, it's not that big a deal. Every time you insert a new value, it's only 5 elements searched to the left, and 5 elements shifted to the right. This is roughly the equivilent of looking at 10 elements in an array. Generalize this further, and it's as though you were reading the entire array 10 times in a row. Unsurprisingly, reading an array 10 times is faster than sorting that entire array (unless the array is very small). So even if you were fed sorted input, in an attempt to slow down your algorithm, this "semi-sort" still seems more than optimal. But if you were to increase the size of your best array, to say... 25, then the factor increases to 50 array walkthroughs. At which point, you might want to start rethinking the choice of algorithm.

Jan 31st, 2008, 10:47 AM	#4
TheAberrant Newbie Join Date: Jan 2008 Posts: 9 Rep Power: 0	Re: Question with Arrays - creating and updating 'top 5' list Excellent, thanks for the help. The pseudocode was along the lines of what I wanted to do, so was able to implement it (though need to do some cleanup - right now my entire script is one main function, and is getting to be around 250 lines now). See code snippet below. (Toggle Plain Text) $i = $numSpikes - 1; while (($i > 0) && ($timeDiff > $Spikes[$i-1][0])) { $i--; } $x = $i; if ($i < ($numSpikes - 1)) { # Shift everything below i down one while ($i < ($numSpikes - 1)) { $Spikes[$i+1] = $Spikes[$i]; $i++; } $Spikes[$x][0] = $timeDiff; $Spikes[$x][1] = $tmpTime; } $i = $numSpikes - 1; while (($i > 0) && ($timeDiff > $Spikes[$i-1][0])) { $i--; } $x = $i; if ($i < ($numSpikes - 1)) { # Shift everything below i down one while ($i < ($numSpikes - 1)) { $Spikes[$i+1] = $Spikes[$i]; $i++; } $Spikes[$x][0] = $timeDiff; $Spikes[$x][1] = $tmpTime; } One question somewhat related - how do I clear or zero out the array? After each file, I need to reset - I can't think of an easy way other than looping through and setting all the values to zero. With C I'd just use memset - is there an equivalent function in perl? Thanks

Jan 31st, 2008, 12:35 PM	#5
Sane Programming Guru Join Date: Apr 2005 Posts: 1,722 Rep Power: 5	Re: Question with Arrays - creating and updating 'top 5' list I'm not sure if there's an equivilent in Perl, but a function won't buy you any extra time if you thought it might. The function itself still does exactly what one would intuitively expect; it will walk through each element setting each to zero. So it could be easier to write one yourself, then to go looking through the Perl docs for something already written. If you'd like to go searching, you should Google something along the lines of "setting/copying array memory in Perl".

Feb 2nd, 2008, 1:40 PM	#6
TheAberrant Newbie Join Date: Jan 2008 Posts: 9 Rep Power: 0	Re: Question with Arrays - creating and updating 'top 5' list Figured it out - just do: (Toggle Plain Text) @Array = (); @Array = (); That will basically remove everything in the array.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Script Programming > Perl

Question with Arrays - creating and updating 'top 5' list