[ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13202115#comment-13202115 ]
Sébastien Brisard commented on MATH-732: ---------------------------------------- Hi Kurt, your implementation is amazingly faster. I think we definitely should go ahead and replace the previous impl. We require all pieces of code (including private methods) to be fully documented. I'll do that, no worries, but I might get back to you (off-list) to get some more information, if you do not mind. Unfortunately, I haven't had time to try and spot the weaknesses of the previous implementation. I suspect this has to do with the use of {{Complex}} arrays, instead of plain {{double}} arrays. Indeed, since {{Complex}} is immutable, we end up creating *a lot* of small objects. In fact, looking at your implementation, I'm wondering whether we should not give up {{Complex[]}} arrays altogether. I would favour a more standard data layout, in a {{double}} array, where {{data[2 * i]}} would be the real part, and {{data[2 * i + 1]}} would be the imaginary part of the specified data. Presently, your implementation takes the real and imaginary parts as two separate arrays. What do you think? I will post this question on the mailing list. Best regards, Sébastien > 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