User Info  Posts 
Brad  Collect Lowest Numbers Algorithm  #1  I'm looking for an algorithm (or PHP code, I suppose) to end up with the 10 lowest numbers from a group of numbers. I was thinking of making a ten item array, checking to see if the current number is lower than one of the numbers in the array, and if so, finding the highest number in the array and replacing it with the current number. However, I'm planning on finding the lowest 10 numbers from thousands, and was thinking there might be a faster way to do it. I plan on implementing this in PHP, so any native PHP functions are usable. posted date: 20081229 14:39:00



kawhi  Re: Collect Lowest Numbers Algorithm  #2  


Bombe  Re: Collect Lowest Numbers Algorithm  #3  Sort the array and use the ten first/last entries.Honestly: sorting an array with a thousand entries costs less time than it takes you to blink. posted date: 20081229 14:43:00 


Zoredache  Re: Collect Lowest Numbers Algorithm  #4  Where are you getting this group of numbers?If your List of numbers is already in an array you could simply do a sort(), and then a array_slice() to get the first 10. posted date: 20081229 14:46:00 


Andrew Coleson  Re: Collect Lowest Numbers Algorithm  #5  Naive approach is to just sort the input. It's likely fast enough, so just try it and profile it before doing anything more complicated.Potentially faster approach: Linearly search the input, but keep the output array sorted to make it easier to determine if the next input belongs in the array or not. Pseudocode: output[09] = input[09];sort(output);for i=10..n1 if input[i] < output[9] insert(input[i]) where insert(x) will find the right spot (binary search) and do the appropriate shifting.But seriously, just try the naive approach first. posted date: 20081229 14:47:00 


Nils Pipenbrinck  Re: Collect Lowest Numbers Algorithm  #6  Hi Bombe! Nice to see you here... posted date: 20081229 14:49:00 


Bombe  Re: Collect Lowest Numbers Algorithm  #7  Nils, even nicer to meet you here. :) posted date: 20081229 14:55:00 


Rob Kennedy  Re: Collect Lowest Numbers Algorithm  #8  What you're looking for is called a selection algorithm. The Wikipedia page on the subject has a few subsections in the selecting k smallest or largest elements section. When the list is large enough, you can beat the time required for the naive "sort the whole list and choose the first 10" algorithm. posted date: 20081229 15:13:00 


Ole Helgesen  Re: Collect Lowest Numbers Algorithm  #9  I doesn't matter much for a small array, but as it gets larger a fast and easy way to increase processing speed is to take advantage of array key indexing, which for 1 mill. rows will use about 40% of the time. Example: // sorting array values$numbers = array();for($i = 0; $i < 1000000; ++$i){ $numbers[$i] = rand(1, 999999);}$start = microtime(true);sort($numbers);$res = array_slice($numbers, 0, 10, true);echo microtime(true)  $start . "\n";// 2.6612658500671print_r($res);unset($numbers, $res, $start);// sorting array keys$numbers = array();for($i = 0; $i < 1000000; ++$i){ $numbers[rand(1, 999999)] = $i;}$start = microtime(true);ksort($numbers);$res = array_keys(array_slice($numbers, 0, 10, true));echo microtime(true)  $start . "\n";// 0.9651210308075print_r($res); But if the array data is from a database the fastest is probably to just sort it there: SELECT number_column FROM table_with_numbers ORDER BY number_column LIMIT 10 posted date: 20081229 15:38:00 


Kent Fredric  Re: Collect Lowest Numbers Algorithm  #10  +1, if you can think of a way to do this faster than quicksort, then you wouldn't have asked this question :D posted date: 20081229 16:09:00 


Kent Fredric  Re: Collect Lowest Numbers Algorithm  #11  1. Naive approaches may work for all your tests, and then randomly die one day in the real world. Leave the fancy tricks up to the experts. Use something that exists unless you know you can do better. posted date: 20081229 16:10:00 


Andrew Coleson  Re: Collect Lowest Numbers Algorithm  #12  Sounds like you need more representative tests. And you misread, the "Naive approach" was the first half, which is the same as the answer you voted up. You wanted to disagree with the "potentially faster approach." posted date: 20081229 16:15:00 


select page: « 1 2 » 