开发者

performance: sorting 'm' vectors with N/m elems Vs sorting single vector with N elements

Operation A

I have N vectors, each containing certain number of unique 3D points. For Example : std::vector<double*> vec1; and like that

I am performing sort operation on each of the vector like:

 std::sort(vec1.begin(), vec1.end(), sortCriteria());
 std::sort(vec2.begin(), vec2.end(), sortCriteria());
 std::sort(vec3.begin(), vec3.end(), sortCriteria());

Operation B

Suppose I have a vector called "all_point_vector" which holds the 3D points from vec1, vec2, vec3 ...

i.e. 3D points in all_point_vector = points_in_vec1 +.... +points_in_vector3.

and I am performing the sort operation:

std::sort(all_point_vec.begin(), all_point_vec.end(), sortCriteria());

My question is , which of the abo开发者_JAVA百科ve methods (Operation A or B) will be faster in general? sorting a single vector (all_point_vector) or sorting individual vectors. I am just interested in the speed of execution of these two operations.

Thanks


Sorting is an O(n log n) operation. Sorting N vectors with m/N elements will become strictly faster than sorting a single vector of m elements as you increase m.

Which one is faster for any fixed m can only be determined by profiling.


What avakar said, in theory sorting a few short vectors should be faster than sorting the whole, in practice - you should measure. I'd just like to show some more math:

Let there be k sequences and the i-th sequence has ni number of elements. Let the total number of elements be N = n1 + ... + nk. Sorting the individual sequences has complexity O(n1logn1 + ... + nklognk). Sorting the big sequence has complexity O(N logN) = O((n1 + ... + nk)logN) = O(n1logN + ... + nklogN). Now we have to compare

A = n1logn1 + ... + nklognk

B = n1logN + ... + nklogN

Since N > ni for all i, logN > logni for all i. Therefore, B is strictly larger than A, i.e. sorting the entire sequence will take more time.


Sorting a single array of m elements is a different problem from sorting the same number of elements divided into N arrays, because in the divided-case, you still don't have a total order of all the elements.

Assuming m = 1024, in the singleton case, m log m = 1024*10 = 10240.

If N=2 you have 512*9 + 512*9 = 9216, but you still have to do a merge step of 1024 comparisons, and 9216 + 1024 = 10240, so it's the same.

[Actually, at each level of the sorting, the number of comparisons is 1 less than the number of items to merge, but the overall result is still O(n log n)]

ADDED: If, as you commented, you don't need to do the merge, then the divided case is faster. (Of course, in that case, you could divide the m items into N=m arrays and not even bother sorting ;-)

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜