Programming Forums - View Single Post - Question with Arrays

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.

Jan 29th, 2008, 11:58 PM	#2
Sane Programming Guru Join Date: Apr 2005 Posts: 1,799 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.