GNU 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 |
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 | Severity | 3 - Normal | ![]() |
2 - Minor |
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/