Wagner, David --- Senior Programmer Analyst --- WGO wrote: > On 4/1/06, Frank Bax <[EMAIL PROTECTED]> wrote: >>> At 06:59 PM 3/31/06, Mr. Shawn H. Corey wrote: >>> >>>> On Fri, 2006-31-03 at 15:45 -0800, Tom Phoenix wrote: >>>>> You should loop over the input, pushing each item on to an array. >>>>> If at any time you have 2000 items in the array, sort them and >>>>> discard any you don't want to keep. >>>>> >>>>> $#data = 999 if $#data > 999; # OBperl: one way to >>>>> discard elements >>>>> >>>>> When you finish looping, sort-and-discard again. You'll never need >>>>> more than 2N items in memory at any given time. Does that >>>>> algorithm work for your needs? >>>> >>>> Sorting is not necessary. If he keeps an array of the best, that >>>> means lowest, records then all he has to do is compare every new >>>> entry with the highest. This is called "fail early." This means, >>>> if it's going to fail, it should at the earliest opportunity. If >>>> it succeeds then it searches down thru the list, to find its >>>> place. This is called "succeed early." Given that the procedure >>>> can flip between these two methods, it is faster than any sort. >>> >>> >>> I'm not the OP, but I have a script with a similar problem. The >>> script has some logic that generates many (thousands of billions) >>> of combinations from a little bit of data and only the best 100 >>> combos are output. For each combination produced by script, a value >>> is calculated. I maintain an array of "best" results so far; if >>> size of this array is <100, then a "new" result is automatically >>> added. If there are already 100 items, I find the "worst" entry in >>> the array. If the "new" entry is better than the "worst", the >>> "new" one replaces the "worst". >>> >>> I am not sure how your reference to "fail early" and "succeed >>> early" apply to this situation. >>> >>> At the moment, the array is left unsorted. If I use a sorted >>> array, it needs to resorted every time a "worst" entry is replaced >>> by a "new" >>> entry. Can I avoid sorting the array every iteration? How else to >>> find the "worst" entry? If I replace "worst" with a "new" entry, >>> doesn't the array need to be resorted? How does the cost of >>> searching an unsorted array compare to resorting on every update >>> and searching a sorted array. >>> >>> Tom's idea about growing to 200, then chopping back to 100 also >>> sounds interesting. >>> >> >> Sorting is expensive, but keeping a sorted array isn't always, >> especially if you know that the majority of your data will fall >> outside your window, preferrably high. I'd probably do something >> like the following: >> >> #!/usr/bin/perl >> >> use warnings; >> use strict; >> >> my $keeprecs = 10; # the number of records you want to keep >> my @data = (10,24,5,32,4,9,8,7,6,1,2,0,3); >> my @array; >> >> while (@data) { # probably while <> in production >> my $number = pop @data ; >> if ($number > $array[-1]) { >> next if @array >= $keeprecs; >> # fail early if the number is high and we >> # already have $keeprecs records saved >> push @array, $number; >> } elsif ($number < $array[0]) { >> unshift @array, $number; >> } else { >> my($i, $idx); >> for ($i = 0; $i < @array; $i++) { >> next if $i == 0; >> if (($number < $array[$i]) and ($number > $array[$i-1])) >> { splice @array,$i,0,$number; >> last; >> } >> } >> } >> pop @array if @array > $keeprecs; >> } >> >> print "@array\n"; >> > I am going to give this a try, but the data is truly a random set of > numbers and whether most will be hi or lo, I will leave that for the > processing. Originally it took a little over 3 hours to do the > processing. > > I have added three arrays and one hash. > a) array 1 holds the numberbs being compared ( sorted ) > b) array 2 holds a key to the hash of data needed later associated > with each number c) array 3 has a set of 2000 keys I can rotate > through as I get hits and use the keys. If key is dropped then I push > back on the array and I have at twice the number needed, so should > never have aproblem. > > d) hash data associated w a) ranges from 60 to 800 bytes per > number. > > Again thanks to the list for the help. > > Shawn, I looked at your response, but did not truly understand, so > depending on what happens here, I may need to give yours a short, but > I was not following it. Sorry. > > Wags ;)
I ran it twice over the evening and it added about 8 minutes in processing for the 3 hours 9 minutes from the original processing. I generated an output after every 100k rcds( 100/rcds printed ). For my actual processing, I think I will dump very hour. Thanks again for the insight to give it a shot and for sharing. Wags ;) > >> The efficiency here will depend on the distribution of the data. If >> every new piece of data is > $array[-2] and < $array[-1], then it's >> something on the order of O($keeprecs * N). In the best case >> scenario, with all records falling above the current max, it's O(N). >> In the real world, who knows, but but it should be reasonably fast. >> >> In any case, the key to a project like this is to figure out quickly >> whether you want to keep a particular peice of data, and spend as >> little time as possible on the out of bounds data which, if you want >> 1000 records out of 1,000,000 should be the vast majority of it. >> >> HTH >> -- jay > > > > ******************************************************* > This message contains information that is confidential > and proprietary to FedEx Freight or its affiliates. > It is intended only for the recipient named and for > the express purpose(s) described therein. > Any other use is prohibited. > ******************************************************* -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] <http://learn.perl.org/> <http://learn.perl.org/first-response>