commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Kurt Ostfeld (Commented) (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MATH-732) Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x improvement). Preserved public API 100%. Removed unnecessary use of instance variables and instance state.
Date Thu, 09 Feb 2012 04:37:59 GMT

    [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13204252#comment-13204252
] 

Kurt Ostfeld commented on MATH-732:
-----------------------------------

Great news. Thanks for the help! I looked at the updated version of trunk. Here are my thoughts:

- Math functions, like DFT, should be pure functions, which in Java is a static function,
like Math.sqrt. I see your point that similar classes inherit from RealTransformer, so the
DFT class should be consistent with that style. The library should offer both interfaces (static
and RealTransformer instance style) to the user and internally one should call the other.
We should add the unitary option to the static transformInPlace function to be consistent.

- Making bitReversalShuffle2 private sounds like a good idea. I can't think of another external
use for that logic.

- The other changes that you made look great.

Here is some JavaDoc for bitReversalShuffle2:

    /**
     * Performs identical index bit reversal shuffles on two arrays of identical size.
     * Each element in the array is swapped with another element based on the bit-reversal
     * of the index.
     * For example, in an array with length 16, item at binary index 0011 (decimal 3)
     * would be swapped with the item at binary index 1100 (decimal 12).
     *
     * @param a The first array to be shuffled.
     * @param b The second array to be shuffled.
     */

                
> Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x improvement).
Preserved public API 100%. Removed unnecessary use of instance variables and instance state.
> ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
>                 Key: MATH-732
>                 URL: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>            Assignee: S├ębastien Brisard
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png, FastFourierTransformer.java,
FastFourierTransformerTest.java, Main.java
>
>
> I wrote my own Discrete Fourier Transform function in Java and ran some benchmarks and
found that it ran dramatically faster than the Apache library implementation. This is a pretty
straight forward implementation of the standard Cooley Tukey algorithm that I read out of
a textbook. This passes all the Apache library test cases plus several I had written on my
own. I created a source code library patch that preserves the public API completely while
changing the internal implementation to achieve the performance improvement.
> In addition to the performance issue, I suggest that Discrete Fourier Transform functionality
be provided as stateless pure functions (in Java this would be implemented with static methods)
just like most other math functions. As-is, the library requires the user to instantiate a
Transformer instance which maintains instance state, which is an unecessary complexity for
a pure math function. I held off on this change since it would change the public API and affect
existing code. However, I see similar backward compatability breaking API changes are already
in the FastFourierTransformer class in the 3.0 code base.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       

Mime
View raw message