Sidebar Sidebar
Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.

macOS sorting question.

F

farmerdoug

macrumors 6502a
Original poster
Sep 16, 2008
541
0
I need the top ten values in a set of results. I could either store all the results as they are calculated and then sort; or I could test each value as it is calculated. If is larger than the largest ten up to that point, I could discard the smallest.
Looking for suggestions on the best way.
Thanks.
 
SnowLeopard2008

SnowLeopard2008

macrumors 604
Jul 4, 2008
6,772
17
Silicon Valley
farmerdoug said:
I need the top ten values in a set of results. I could either store all the results as they are calculated and then sort; or I could test each value as it is calculated. If is larger than the largest ten up to that point, I could discard the smallest.
Looking for suggestions on the best way.
Thanks.
Click to expand...

Pick a sorting method. Selection, bubble, etc. I would process the top ten after calculation. Simplifies things a bit.
 
D

dmi

macrumors regular
Dec 21, 2010
162
33
I'd suggest scanning through the results while maintaining a ten element heap structure with the top values seen so far.

You could also do a recursive K-median selection algorithm analogous to quicksort, but although the expected time is O(n), unfortunate choices could make it O(n^2)
A median of medians algorithm can guarantee O(n) performance, but the complication may not be worth it compared to maintaining a heap of just 10 elements.
 
Last edited:
F

farmerdoug

macrumors 6502a
Original poster
Sep 16, 2008
541
0
At the moment I have been doing what dmi has suggest, or close. I scan the top ten every time I have a new value; placing in the right position if is large enough to be included; and shifting the rest down. My guess is that the number of greater values is far less the very large number of total values.

The language is c.
 
D

dmi

macrumors regular
Dec 21, 2010
162
33
With a min heap structure, you can make the scan of the top ten with O( log(10) ) comparisons and shifts, instead of O(10) comparisons and shifts, but 10 may be small enough that it the difference is not worth worrying about.
 
E

Efrem

macrumors regular
Jul 30, 2009
115
15
farmerdoug said:
At the moment I have been doing what dmi has suggest, or close. I scan the top ten every time I have a new value; placing in the right position if is large enough to be included; and shifting the rest down. My guess is that the number of greater values is far less the very large number of total values.

The language is c.
Click to expand...
If, as you seem to have said, you keep the top ten in order, then you don't have to scan them. Just compare the new value with the bottom one in the current Top 10 list.
 
D

dmi

macrumors regular
Dec 21, 2010
162
33
Efrem said:
Just compare the new value with the bottom one in the current Top 10 list.
Click to expand...
And if it is greater than the bottom one, it would have to be inserted in order.
This is easy with a heap structure, but a top 10 list is small enough that shifting the everything down instead may not be too bad.
 
Y

ytk

macrumors 6502
Jul 8, 2010
252
5
The simplest way I can think of to do this is to maintain an array of 11 items, and initially populate it with MINVAL for your data type. As you read each item, place it into a temporary variable. Iterate backwards over the array, starting at position 9 (the tenth element). If the value at that position is less than the read value, move it to the next position up and continue iterating. If it is equal or greater, place the read value at the next position up, and repeat. If you reach the bottom of the list, place the read value in position 0.

This approach is nice because it doesn't require any temporary variables to actually perform the sort other than the one holding the read value and an index variable, and it's probably pretty fast because it only needs to read and write elements that potentially need to be shifted.

If you wanted to improve performance a tiny bit (and we're getting really obsessive here :D), you could eliminate the last conditional (testing whether you've reached the bottom of the list). One way to do this would be with a goto statement (instead of a break) after you've placed the value in its place. The other would be to make your array size 12 items, and populating the the first item with MAXVAL, and all the rest with MINVAL. Then when you are done, you just take [1..10] as your top ten list.
 
F

farmerdoug

macrumors 6502a
Original poster
Sep 16, 2008
541
0
You guys have done yeoman service here. I thought about just looking at the last value or something similar and for some (obviously incorrect) reason rejected it. However, I should do it. Regarding some of the other suggestions, I need to think about them. I didn't grasp the ideas at first reading but will check in to them.

Thanks.
 
chown33

chown33

Moderator
Staff member
Aug 9, 2009
10,743
8,417
A sea of green
dmi said:
And if it is greater than the bottom one, it would have to be inserted in order.
Click to expand...

His point is that it's not necessary to test the new candidate against every member of the top-ten list.

For a fast-rejection, it's only necessary to compare the new candidate with the smallest item already in the top-ten list. If the candidate value is less, then it's rejected because it will certainly be less than every other value already in the top-ten list. We can deduce this because the initial comparison is performed on the smallest value already in the list. Reject/accept is thus determined with one comparison for each new candidate value

This is in direct contrast to the OP's algorithm: "I scan the top ten every time I have a new value". I.e. ten comparisons for each new candidate value.

After reject/accept has been decided, the new candidate replaces the smallest value already in the list (it will certainly be the item removed, since it's smallest). The list is then resorted. I'd probably start with insertion-sort because the list is so small, and only worry about a faster sort if performance was measurably bad. But after eliminating 9X pointless comparisons, my first guess is the gain from that would be worth more than trying to find a faster sort than insertion-sort.
 
Last edited:
D

dmi

macrumors regular
Dec 21, 2010
162
33
chown33 said:
This is in direct contrast to the OP's algorithm: "I scan the top ten every time I have a new value".
Click to expand...
When you scan an ordered top ten list,
(and being ordered seemed to be implied by the statement about placing it in the right position and shifting everything down)
you can stop as soon as you know that everything else in the list is greater than the value you are scanning for.
If the values come in a random order, the expected number of comparisons needed to check n new values would be about n+10*log(n).
The worst case would be 10*n with a linear scan, or log(10)*n with a heap or binary search.

If you keep the list in a heap order rather than a linear order, then instead of 10*log(10) operations to re-sort the list when you replace an element, you 'd only need log(10) operations to restore the heap order.
But, again, 10 may be small enough that even 10^2 operations to re-sort may not be an excessive burden.
 
F

farmerdoug

macrumors 6502a
Original poster
Sep 16, 2008
541
0
I am only comparing to the last item on list; then if I have a new item to insert I figure out where it goes; move everything down; and insert it. I also checked my numbers, I'm saving the top ten out of millions. Saving then sort would definitely be a bad idea. What would help now is if you could tell me how to move a structure from one location to another without doing it element by element.

Thanks.
 
gnasher729

gnasher729

Suspended
Nov 25, 2005
17,980
5,565
farmerdoug said:
I am only comparing to the last item on list; then if I have a new item to insert I figure out where it goes; move everything down; and insert it. I also checked my numbers, I'm saving the top ten out of millions. Saving then sort would definitely be a bad idea. What would help now is if you could tell me how to move a structure from one location to another without doing it element by element.

Thanks.
Click to expand...

For example:

Code: 
memmove (&array [3], &array [2], 7 * sizeof (array [2]));

The first parameter is the destination, the second parameter is the source, and the third parameter is the number of bytes. This particular call will move seven array elements starting with element #2 to the location starting with element #3, and handles overlapping source and destination correctly. In other words, it moves #2 to #8 into the places #3 to #9.

On MacOS X, memmove, memcpy and memset use hand-optimised assembler code that is actually optimised for the particular machine it is running on. There is no way to do the same thing faster. (memcpy cannot be used here because source and destination are overlapping).
 
chown33

chown33

Moderator
Staff member
Aug 9, 2009
10,743
8,417
A sea of green
farmerdoug said:
I am only comparing to the last item on list; ...
Click to expand...

If "last" means "the largest of the top ten", then that's inefficient. If "last" means "the smallest of the top ten", then that's much better. If the reason isn't clear, reread post #11.

A sorted array with the smallest item first and the largest last is called "ascending" order. An array with the largest first and the smallest last is called "descending" order.


What would help now is if you could tell me how to move a structure from one location to another without doing it element by element.
Click to expand...

To move a structure (i.e. a single struct), simply assign it:
Code: 
struct example {
  int foo;
  char bar[10];
};

struct example arry[10];
arry[3] = arry[8];  // copies 8 to 3

struct example * a;
a = &arry[4];
*a = arry[9];  // copies 9 to 4

To move one or more structs in a single move, use memmove or memcpy.

The distinction between the two things -- a single structure vs. one or more -- is that one is a single item, and the other is an array of items.

For the single struct case, it doesn't matter that a single struct contains an array (of char). The struct itself is a single item.
 
Last edited:
D

dmi

macrumors regular
Dec 21, 2010
162
33
In C++ you can maintain a heap with
Code: 
std::pop_heap
and
Code: 
std::push_heap
you can either reverse the Compare operator or negate the values to make it a min heap instead of a max heap

In C, you could build your own like
Code: 
#define heap_size 10
int heap[heap_size];

void down_heap(int p,int root){
  int child;
  while( (child=root*2+1) < heap_size ){
    if( child+1 < heap_size && heap[child+1] < heap[child] ){
      ++child;
    }
    if( heap[child] >= p ){ return; }
    heap[root]=heap[child];
    heap[child]=p;
    root=child;
  }
}

and add maintain it like
Code: 
i=heap_size;
while( scanf("%d",&p ) ){
     if( i==0?heap[0]<p:i-- ){ heap[i]=p; down_heap(p,i); }
}
 
You must log in or register to reply here.
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.
Top Bottom