Archived

This topic is now archived and is closed to further replies.

Hippokrates

Have to sort really fast

Recommended Posts

What would be the fastest method to sort a linked list? I have a list of 3D Objects that have to be sorted by z order because the might contain transparency. So how can I possibly sort them at a speed that allows me to do this per-frame?

Share this post


Link to post
Share on other sites
Have them allways be sorted as you update and objects position if it changes in the z direction compare it to it''s neibours. If it exceed or is less the one of them, you know it''s time for them to swap positions.

When you add a new object to the list, make sure you add it to the right place in the list so that it perserves the sort order.

Share this post


Link to post
Share on other sites
herm.. you could use a std::set, which automatically sorts items as they''re placed in the set.

There''s no random access tho, so you''d actually have to traverse the whole set, just like a list, to find a particular element.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
if your problem is due to transparency, then you could also disable depth buffer writes when drawing a (possibly) transparent object.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
A fast way to do it is to do a bubble sort and amortize the sort over time. You do one pass on the list per frame. Not a full sort, just one pass. Over a small period of time your list will sort. This works well for lists that have good time coherency, ie. don''t change much over time.

If you''ve put yourself in a situation where you need to sort a large very-unsorted list every frame you should rethink your design. Sorting that much every frame means you''ve made some bad design choices...

Share this post


Link to post
Share on other sites
If you use std::list, it has a sort member function which uses this frightening code (VS.NET):

  
void sort()
{ // order sequence, using operator<

if (2 <= size())
{ // worth sorting, do it

const size_t _MAXBINS = 25;
_Myt _Templist(this->_Alval), _Binlist[_MAXBINS + 1];
size_t _Maxbin = 0;

while (!empty())
{ // sort another element, using bins

_Templist.splice(_Templist.begin(), *this, begin());
size_t _Bin;

for (_Bin = 0; _Bin < _Maxbin && !_Binlist[_Bin].empty();
++_Bin)
{ // merge into ever larger bins

_Binlist[_Bin].merge(_Templist);
_Binlist[_Bin].swap(_Templist);
}

if (_Bin == _MAXBINS)
_Binlist[_Bin - 1].merge(_Templist);
else
{ // spill to new bin, while they last

_Binlist[_Bin].swap(_Templist);
if (_Bin == _Maxbin)
++_Maxbin;
}
}

for (size_t _Bin = 1; _Bin < _Maxbin; ++_Bin)
_Binlist[_Bin].merge(_Binlist[_Bin - 1]); // merge up

swap(_Binlist[_Maxbin - 1]); // replace from last bin

}
}

Share this post


Link to post
Share on other sites
Well, I use this lists for my so called sprites (so called, because they are in a way normal 3D objects except that they are always quads).
So I can`t know how many sprites I have got but I don`t think it will become thousands. More like something below 100 because I can reload them per map. It could even be less.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
About that bubble sort, he actually didn''t say to do a full bubble sort each time, just one pass through it each frame. As long as the positions don''t change too radically, it should keep everything close enough and still be fast. Interesting idea, and worth a try, I think.

Karg

Share this post


Link to post
Share on other sites
from memory there is a qsort() function or something like that around the shop...

look at that just found it in msdn. its used on arrays and is very generic:


void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

Remarks

The qsort function implements a quick-sort algorithm to sort
an array of num elements, each of width bytes. The argument
base is a pointer to the base of the array to be sorted.
qsort overwrites this array with the sorted elements.
The argument compare is a pointer to a user-supplied routine
that compares two array elements and returns a value
specifying their relationship. qsort calls the compare routine
one or more times during the sort, passing pointers to two
array elements on each call:

compare( (void *) elem1, (void *) elem2 );

The routine must compare the elements, then return one of the following values:

Return Value Description
<0 elem1 less than elem2
0 elem1 equivalent to elem2
>0 elem1 greater than elem2


last I knew nobody can come up with an algorithm which was better an O(n*log(n)) which I *believe* quicksort is.

just another suggestion
Toby

Gobsmacked - by Toby Murray

[edited by - tobymurray on August 16, 2002 1:40:36 PM]

Share this post


Link to post
Share on other sites
qsort() is only for arrays, and he has a linked list. But you''re right, it''s one hella fast way to sort arrays.

Speaking of which, the std::list sort function is also O(n log n).

Share this post


Link to post
Share on other sites
Bubble sort seems the most appropriate in your situation.

However, instead of using a linked list, you could make an array of pointers, and use quick sort. Why do you need a list?

Cédric

Share this post


Link to post
Share on other sites
Thanks for all the answers.
I do use a list because I want to be able to dynamically create and destroy sprites.
I could of course maintain an internal pointer array, which is modified everytime I add/remove an element.

BTW: I also have to group the sprites by texture. Is there a way to avoid destroying the z order when doing so ?

Share this post


Link to post
Share on other sites
which sorting algorithm is fast depends also on the size of the list/array whatever. if you have a small list < 100 elements. bubblesort can be appropriate. but if you have a big list quicksort will be very much faster. for medium list sizes is insertion sort not a bad choise. quicksort is not always the fastest one for small/medium lists because it has some overhead in the algorithm. and it also depends if the arrays are somehow pre-sorted or totaly clutterd.

Share this post


Link to post
Share on other sites
qsort needs constant-time random access to elements in order to approach that limit. Since random access to lists is O(N), you''re not even going to get close with qsort on a list.

Share this post


Link to post
Share on other sites
and then there was std::vector
also you should keep transperent objects and non transparent objects seperate to reduce what may be potentially sorted, as the saying goes "the fastest operation is one you never do".

[edited by - a person on August 16, 2002 4:02:39 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Hippokrates
Well, I use this lists for my so called sprites (so called, because they are in a way normal 3D objects except that they are always quads).
So I can`t know how many sprites I have got but I don`t think it will become thousands. More like something below 100 because I can reload them per map. It could even be less.


You can have array 100 pointers and sort them using qsort(). Since you are talking below 100.

Share this post


Link to post
Share on other sites
The best solution presented thus-far is maintaining the sorted order of the list at all times.
The fastest sort is the insertion sort. It''s O(n), n/2 nominially, and requires no copying for list.

That said, if you''re compiling with MSVC, use vector. It''s as faster or faster than a list for virtually all operations (yes even insertions and splices), unless you have well over ten thouasand nodes.
The BGL group did performance test on thier graph algorithms and were somewhat surprised by these results. The problem is that MSVC is extremely good at optimizing vector operations, and is exetremely slow when allocating & deallocating memory.



qsort significantly degrades in performance when the list is already or nearly sorted.

The only reason to ever use a bubble sort, is because it''s too hard to make a real sorting algorithm, or you need to fit the sorting algorithm in about 50bytes of code space.

Share this post


Link to post
Share on other sites
Is it possible to use a BSP? Even to make the whole thing dynamic it''d take no time to pull one out, change its Z and then put it back in according to its new Z.

Share this post


Link to post
Share on other sites
quote:
Original post by DrPizza
I think you should be able to radix sort them quite effectively, if a little memory-intensively.
IIRC, radix sorting a linked list takes a little over 1k of stack space. Not quite what I'd call memory-intensive.

EDIT: make that 2k, actually.

[edited by - Beer Hunter on August 17, 2002 5:04:55 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
so you need them sorted by z and by texture? Try two lists with pointers to the data. So they would both have the same pointers, but in different order.

Share this post


Link to post
Share on other sites