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
Operating System:  Status:  None
Assigned to:  None Open/Closed:  Open
Release:  1.10

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.fr/hotmailimode/



-Deleted Account- <bjg>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

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.13-4448.
Corresponding source code