Groups > comp.programming.threads > #1210

Re: About my ParallelSort library

Path	csiph.com!usenet.pasdenom.info!news.albasani.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	Re: About my ParallelSort library
Date	Wed, 31 Oct 2012 21:08:19 -0500
Organization	A noiseless patient Spider
Lines	127
Message-ID	<k6si10$fs7$2@dont-email.me> (permalink)
References	<k6sbo2$anb$2@dont-email.me>
Injection-Date	Thu, 1 Nov 2012 01:07:44 +0000 (UTC)
Injection-Info	mx04.eternal-september.org; posting-host="c43ca82f9e8d62a602307fe9d2e9b807"; logging-data="16263"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18K67Tahh4BrL4g6jf9cMyq"
X-MimeOLE	Produced By Microsoft MimeOLE V6.00.2900.6157
X-RFC2646	Format=Flowed; Response
X-Newsreader	Microsoft Outlook Express 6.00.2900.5931
Cancel-Lock	sha1:qlwzMBW3MT5jnMkZ6RmuEwaZf/8=
X-Priority	3
X-MSMail-Priority	Normal
Xref	csiph.com comp.programming.threads:1210 comp.programming:2432

Cross-posted to 2 groups.

Show key headers only | View raw

To explain more:

The best case complexity of ParallelSort using mergesort  is:

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

the ((n/p)* log(n/p)) is the complexity of the sorting part.

O(n/p) is the best case complexity of the merging part.

so the best case complexity  is:  ((n/p)* log(n/p))

The worst case complexity of parallel sort library using mergesort is:

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

the ((n/p)* log(n/p)) is the complexity of the sorting part.

O(n) is the worst  case complexity of the merging part.

so the worst case complexity is approximatly: O(n)



Amine Moulay Ramdane.


"aminer" <aminer@toto.com> wrote in message 
news:k6sbo2$anb$2@dont-email.me...
>
> 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 — Previous 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