sorting question.

[Cogman]

I have a vector filled with points, sometimes it can be very large, other times it can be very small. As it stands, I am using a radix sort. It works, but I am using a couple of lists to do the sort (they are from the STL).

So when I do a profile of the program, the place where I am spending most of my time on this function is calling the new command in the lists. Well, that won't due , So what data structure would you recommend? The radix sort is going to be the fastest way to sort the points (and has been the fastest that I have implemented thus far).

As a small note, I am sorting by distance. from a given point.

*edit* How about a map and just let it do the sorting? that actually might be quicker

 

[Cogman]

Map was not quicker, Ill be better off optimizing my radix sort. Ill probably end up making my own special container.

 

[degibson]

How about using sort() in algorithm.h? How does that perform? Which sort it implements will depend on which STL you have...
http://www.cppreference.com/wiki/stl/algorithm/sort

 

[Cogman]

Originally posted by: degibson
How about using sort() in algorithm.h? How does that perform? Which sort it implements will depend on which STL you have...
http://www.cppreference.com/wiki/stl/algorithm/sort

STL uses a comparison sort. While faster in small arrays, and even sorted arrays, it isn't much faster. Radix sort is a fair amount faster with medium to large data sets.

 

[degibson]

Originally posted by: Cogman

Originally posted by: degibson
How about using sort() in algorithm.h? How does that perform? Which sort it implements will depend on which STL you have...
http://www.cppreference.com/wiki/stl/algorithm/sort

STL uses a comparison sort. While faster in small arrays, and even sorted arrays, it isn't much faster. Radix sort is a fair amount faster with medium to large data sets.

Perhaps you would be well off to move away from lists -- especially if you do a lot of insertions, deletions, manipulations, etc. Lists have lousy locality and no parallelism at all. Would it be possible to switch to vector<> or dumb arrays? (Since you're rolling your own sort anyway...)

Edit: I can't spel.

 

[Cogman]

Originally posted by: degibson

Originally posted by: Cogman

Originally posted by: degibson
How about using sort() in algorithm.h? How does that perform? Which sort it implements will depend on which STL you have...
http://www.cppreference.com/wiki/stl/algorithm/sort

STL uses a comparison sort. While faster in small arrays, and even sorted arrays, it isn't much faster. Radix sort is a fair amount faster with medium to large data sets.

Perhaps you would be well off to move away from lists -- especially if you do a lot of insertions, deletions, manipulations, etc. Lists have lousy locality and no parallelism at all. Would it be possible to switch to vector<> or dumb arrays? (Since you're rolling your own sort anyway...)

Edit: I can't spel.

A dumb array is not possible, and vectors are way slower then lists are for this (I used vectors first). Instead, I'm going to make a special type of list that can transfer nodes to each other. Half the slowdown is waiting for the list to delete/recreate itself.

With a radix sort, parallelism isn't possible at all anyways (well, it might be, but it would be ugly and I don't know that you would gain anything by it).

But as I said, the way a radix sort works makes vectors the much slower alternative. Dumb arrays could be faster, but at a huge memory cost.

 

[Cogman]

well, for any interested I made my custom list that can transfer nodes instead of just copy and pop them. The difference? Using the STL deque it was 7.5-8.0seconds to sort a vector of 307200 points. Using my custom made list, it took 4.5 seconds to sort the exact same data set. I would say thats a pretty good speed increase, wouldn't you

 

[degibson]

Originally posted by: Cogman
well, for any interested I made my custom list that can transfer nodes instead of just copy and pop them. The difference? Using the STL deque it was 7.5-8.0seconds to sort a vector of 307200 points. Using my custom made list, it took 4.5 seconds to sort the exact same data set. I would say thats a pretty good speed increase, wouldn't you

Indeed! Bravo!

Originally posted by: Cogman
With a radix sort, parallelism isn't possible at all anyways (well, it might be, but it would be ugly and I don't know that you would gain anything by it).

I was thinking more of 'parallelism' as in instruction-level parallelism exploited by the host processor. Lists certainly have very little ILP... arrays are often better than lists because there is no serial dependence in an array. But of course, it depends on a lot of things like loop depth and other workload-dependent features of the code, and a great many applications simply do not easily match linear data structures.

Kudos on the speedup

 

[IHateMyJob2004]

Would a hash map work better? What are you trying to do?

 

[Cogman]

Originally posted by: IHateMyJob2004
Would a hash map work better? What are you trying to do?

Sort an array of Points as fast as possible (in order of distance from a center point). The map didn't go faster then a radix sort.

 

[Kntx]

Originally posted by: Cogman
well, for any interested I made my custom list that can transfer nodes instead of just copy and pop them. The difference? Using the STL deque it was 7.5-8.0seconds to sort a vector of 307200 points. Using my custom made list, it took 4.5 seconds to sort the exact same data set. I would say thats a pretty good speed increase, wouldn't you

IMO, a good speed increase is an order of magnitude. Your speed increase is marginal.

/dick

WTG!

 

[dinkumthinkum]

You can merge-sort with lists in constant space and O(n*log(n)) worst-case running time (in the comparison model).

 

[Cogman]

Originally posted by: dinkumthinkum
You can merge-sort with lists in constant space and O(n*log(n)) worst-case running time (in the comparison model).

look up radix sorting, my implementation uses constant space and has O(n*k) run time (Every time). radix sorting will almost always beat merge-sorting, especially since merge sorting relies on recursion. The only time merge sorting will beat radix sorting is when the list is already sorted (not going to happen) and even then it isn't by much.

(btw, the k stands for the number of bytes in the largest variable)

 

[dinkumthinkum]

I know perfectly well what radix sort is. I thought you had not wanted to use it.

 

[Cogman]

Originally posted by: dinkumthinkum
I know perfectly well what radix sort is. I thought you had not wanted to use it.

I was just stating the facts, not yelling at you. Re-read my original post, I wanted to know if there was a data structure that worked better then a list for a radix sort, not if there was a better sorting method.