Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.programming.threads > #1206

About my ParallelSort library

Cross-posted to 2 groups.

Show all headers | View raw

Hello all,

I have done some tests with my ParallelSort library and
i have noticed that it can give up to 3.8x scalability with
strings, and it give  3x scalability with integers..

The complexity of ParallelSort using mergesort for exemple, is:

((n/p)* log(n/p)) + O(n/p)


And as you know:

If f1 is O(g1) and f2 is O(g2),
then f1 + f2 is O(max (f1, f2)), where
max (f1, f2) (x) = max (f1 (x), f2 (x)); for every  x

So the complexity of my Parallel Sort library using mergesort
is:

(n/p)* log(n/p))  // p is the number of cores.


Also i have implemented Parallel MergeSort and Parallel Quicksort,
but MergeSort is faster and the reccurence equation of the complexity of 
mergesort is:

T(n) = 2 * T(n/2) + n

cause it take O(n) for the merging part.

It gives:

T(n) = 2 * T(n/2) + n

= 2 (2T(n/4) +n/2) + n

=4T(n/4)+n+n

=4T(n/4)+2*n

=4 (2T(n/8) +n/4) + 2*n

=8T(n/8)+n+2n

=8T(n/8)+3*n

=2k T(n/2^k) + k*n

We want:

n/2k = 1

n = 2k

log n = k

so the reccurence equation gives:

= nT(1) +n*log(n)

= n+ (n * log(n))

So the mergesort complexity in the best case and in the worst case is:

n * log(n)

But the complexity of the quicksort in the worst case is:

T(n)= n + T(n-1)

it gives:

T(n) = n + (n-1) + T(n-2)

T(n) = n + (n-1) + (n-2)+ T(n-3)

T(n) = 1 + 2+ 3+.+N

T(n) = O(n^2)  // n power of 2


You can download Parallel Sort library from:

http://pages.videotron.com/aminer/



Thank you,
Amine Moulay Ramdane.


 

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar

Thread

About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 19:21 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 19:50 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 20:40 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 20:48 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 21:08 -0500

csiph-web