bugGNU Scientific Library - Bugs: bug #21833, suboptimal performance of gsl...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #21833: suboptimal performance of gsl permutation?

Submitter:  -Deleted Account- <bjg>
Submitted:  Tue 18 Dec 2007 05:48:21 PM UTC
   
 
Category:  Performance Severity:  2 - Minor
Priority:  5 - Normal Operating System: 
Status:  None Assigned to:  None
Open/Closed:  Open Release:  1.10

Discussion

Tue 18 Dec 2007 05:48:21 PM UTC, original submission:  

From: "djamel anonymous" <djam8193ah@hotmail.com>
To: -email is unavailable-
Subject: gsl permutation
Date: Wed, 24 Jan 2007 07:42:06 +0000

Hi.
i am sending you this email about a possible issue in glibc permutation
algorithm.i think it has qudratic worst case running time.for example if we
have the permutation
1,2,3,4,,,,,n,0
we will permute all elements in first iteration then for each iteration we
will traverse on average half the cycle (which is of size n) before we know
that the elements of cycle have already been permuted.there is two possible
solutions to make the algorithm linear:
1-at each step we traverse the full cycle and permute all elements in the
cycle.for each permuted element i  we assign p[i]=i.the disavantage of this
is that it will destroy the original permutation.
2-use a bit array of size n bits.each time we permute an element we set the
relevant bit.if at iteration i we find that bit i is already set we skip to
next iteration.the disavantage of this is that it equires additional storage
allocation.
best regards.

_______________________________________________________________
MSN Hotmail sur i-mode™ : envoyez et recevez des e-mails depuis votre
téléphone portable ! http://www.msn ... /hotmailimode/



-Deleted Account- <bjg>

 

Attached Files

This item currently has no attached files.

 

Dependencies

This item does not depend on any other items.

No items depend on this one.

 

Mail Notification Carbon-Copy List

 

History

Follows 1 latest change.

Date Changed by Updated Field Previous Value => Replaced by
2008-02-09 bjg Severity3 - Normal 2 - Minor

Back to the top

Powered by Savane 3.16-1eaf.
Corresponding source code