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

 
 

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

bug #21833: suboptimal performance of gsl permutation?

Submitted by:  -Deleted Account- <bjg>
Submitted on:  Tue 18 Dec 2007 05:48:21 PM UTC  
 
Category: PerformanceSeverity: 2 - Minor
Operating System: Status: None
Assigned to: NoneOpen/Closed: Open
Release: 1.10

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

From: "djamel anonymous" <djam8193ah@hotmail.com>
To: -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>

 

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

Please enter the title of George Orwell's famous dystopian book (it's a date):

 

 

Follows 1 latest change.

Date Changed By Updated Field Previous Value => Replaced By
Sat 09 Feb 2008 04:22:00 PM UTCbjgSeverity3 - Normal=>2 - Minor

Back to the top


Powered by Savane 3.1-cleanup