Page 1 of 1
Reading in lowest-age users... most efficient method?
Posted: Thu Nov 06, 2008 1:07 pm
by darkdss
I'm going down a list of users and I want to store the 5 users with the lowest age.
Currently I am:
I start with an empty array $age of size 5.
1. I read in a user, and put it in my $age[0] spot.
2. Sort the array from low to high.
3. Rinse and repeat until the array is full.
When array $age[0-4] is full I switch to this algorithm.
5. Compare the new age with the $age[4] (since the highest age will always sit here)
6. If the new age is lower than that, I insert it into the array at position $age[4]
7. Sort the array from low to high.
8. Rinse and repeat until I've read all the users.
Does anyone know the best way to approach this problem? I feel like my way is too costly.

Re: Reading in lowest-age users... most efficient method?
Posted: Thu Nov 06, 2008 1:28 pm
by VladSun
Where do you read users' age from? A DB?
Re: Reading in lowest-age users... most efficient method?
Posted: Thu Nov 06, 2008 1:35 pm
by darkdss
Well I read the user data in from a file, so all my information ends up being in an array. Then I need to go find the 5 lowest ages.
My method works but I was just wondering if there is a better way to go about this.
Re: Reading in lowest-age users... most efficient method?
Posted: Thu Nov 06, 2008 1:38 pm
by VladSun
What are the main requirements - memory or speed?
Re: Reading in lowest-age users... most efficient method?
Posted: Thu Nov 06, 2008 1:41 pm
by darkdss
I'm going for speed, lowest runtime (big O).
Re: Reading in lowest-age users... most efficient method?
Posted: Thu Nov 06, 2008 1:47 pm
by VladSun
I would go with a sorting algorithm that takes all the elements and sort them from lowest to higher one at once.
Choose one:
http://en.wikipedia.org/wiki/Sorting_algorithm
And when the 5th element is sorted - break.
PS: WOW I didn't even suppose that there are so many sorting algorithms

Re: Reading in lowest-age users... most efficient method?
Posted: Thu Nov 06, 2008 1:54 pm
by darkdss
Correct.
Basically I was using the built in sort which runs quicksort ( O(n log n)) but I was wondering if there was a better way to do this. Perhaps a more dynamic approach?
Re: Reading in lowest-age users... most efficient method?
Posted: Thu Nov 06, 2008 2:01 pm
by darkdss
Oh I see where you're going with this. I made a mistake in my specification.
Actually all the data is not in an array, and I'm reading it into a file line by line from 3 simultaneous sources. Basically I need to dynamically update the $age list.
Re: Reading in lowest-age users... most efficient method?
Posted: Fri Nov 07, 2008 7:54 am
by Hannes2k
Hi,
check the age during reading.
Does your code looks like:
Code: Select all
$lines = file('ages1.txt');
foreach($files AS $line)
$ages[] = $line;
$lines = file('ages2.txt');
foreach($files AS $line)
$ages[] = $line;
$lines = file('ages3.txt');
foreach($files AS $line)
$ages[] = $line;
For finding the five persons with the lowest age, there is a much simpler solution, if I understood you right.
Just check the age during reading the files. You create an array with 5 elements (all null). For the items in the array there is a requierement: The have to be sorted, e.g. the lowest age is element 0 ($ages[0]) and the highst is the last element ($ages[5]).
If you then read your text files, you just have to check if the new age is lower than the last element of your array:
Code: Select all
$ages = array(null,null,null,null,null);
$lastIndex = count($ages)-1;
$lines = file("ages1.txt");
foreach($lines AS $line) {
$age = intval($line); //To get the age
if($ages[$lastIndex] == null || $age < $ages[$lastIndex])
insert($age, $ages);
}
If you have now found an age which is lower than the highest age in your array (lower than the last element in the array), you have to insert the age into your array, but in a such way, that the array is kept sorted:
Set the last element to null, then go backwards until you find the right position.
If your array looks like:
10 20 30 40
And the new age is 25:
1. 10 20 30 null
2. 10 20 30 30 | 25 < 30, so increase the index of 30 by 1. It's easier just to copy this element
3. 10 20 25 30 | 25 > 20, so replace the element on index 2 with the new age.
If hope you understand what I mean ^^