Groups > comp.programming.threads > #1206

About my ParallelSort library

Path	csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From	"aminer" <aminer@toto.com>
Newsgroups	comp.programming.threads, comp.programming
Subject	About my ParallelSort library
Date	Wed, 31 Oct 2012 19:21:21 -0500
Organization	A noiseless patient Spider
Lines	96
Message-ID	<k6sbo2$anb$2@dont-email.me> (permalink)
Injection-Date	Wed, 31 Oct 2012 23:20:34 +0000 (UTC)
Injection-Info	mx04.eternal-september.org; posting-host="c43ca82f9e8d62a602307fe9d2e9b807"; logging-data="10987"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+ulRDU+lBhNgSYXqv2Adjs"
X-MimeOLE	Produced By Microsoft MimeOLE V6.00.2900.6157
X-RFC2646	Format=Flowed; Original
X-Newsreader	Microsoft Outlook Express 6.00.2900.5931
Cancel-Lock	sha1:az2R6IARG/AiQpKycX/R9nueVNs=
X-Priority	3
X-MSMail-Priority	Normal
Xref	csiph.com comp.programming.threads:1206 comp.programming:2427

Cross-posted to 2 groups.

Show key headers only | 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