Le lun. 21 mars 2022 à 23:12, Alex Herbert <alex.d.herb...@gmail.com> a écrit : > > Hi, > > This lost the dev@commons in the to address. I am forwarding to the list to > include the history.
>From a quick read of the quoted messages below, I believe I must point out that there is an FFT implementation in Commons Math.[1] It could be construed as a (high priority) use case. Thus, it should be included in benchmarks and possibly adapted to work with the proposed data-structure(s). Regards, Gilles [1] https://gitbox.apache.org/repos/asf?p=commons-math.git;a=blob;f=commons-math-transform/src/main/java/org/apache/commons/math4/transform/FastFourierTransform.java > > On Sun, 20 Mar 2022 at 16:49, Sumanth Rajkumar <rajkumar.suma...@gmail.com> > wrote: > > > Thanks for the feedback Alex! > > > > As suggested, I reviewed the JTransforms and ComplexUtils class in the > > complex streams package. > > > > The existing complex utils class has methods to convert to and from Array > > data structures (the forms used in JTransform) to Complex class. > > > > I can come up with a Java 8/Streams based API for implementing complex > > FFT algorithms of the types in JTransforms and support various methods in > > ComplexUtils > > The streams based complex operations API should allow for decoupling the > > backing data structures. > > This should make it possible to use single API to create an unit test > > suite to benchmark/compare different backing data structures such as single > > arrays, floats or even polar representations > > > > As part of the project, I could implement a subset of the FFT operations > > in JTransform using the new streams based Complex Numbers API and > > benchmark it against JTransform implementation > > > > > > I understand that we are in the GSOC discussion phase. I am trying to > > understand the background of this project and the requirements in order to > > come up with my GSOC proposal > > > > Can you provide with more information on the envisaged usage of > > Commons-Numbers (especially Complex Numbers), its current usage/users and > > the vision/roadmap for future enhancements > > > > Are we expecting complex-numbers to be an efficient pure java library that > > could be used by other java libraries such as commons-imaging for data > > compression (DCT /JPEG lossy compression)? > > > > Are there other Java/Non-Java (C/Python) libraries that provide similar > > features that I can look into for design inspiration and also benchmark > > Complex Numbers with? > > > > Thanks > > Sumanth > > > > > > On Tue, 15 Mar 2022 at 20:50, Alex Herbert <alex.d.herb...@gmail.com> > > wrote: > > > >> Hi Sumanth, > >> > >> These changes to use static methods with functional interfaces is an > >> improvement. However I would advise that we consider the use cases for this > >> functionality to ensure that any design does not prevent extension and also > >> allows full flexibility to achieve various tasks. > >> > >> For example: > >> > >> - multiply all the complex numbers in one list with another > >> - wrap an existing complex number data structure, for example the FFT > >> result produced by JTransforms [1] > >> > >> This project originates from a previous enhancement request that was made > >> to store a large set of complex numbers efficiently. The argument was that > >> the 16 bytes to store 2 doubles is inflated by the object allocation to > >> store a Complex, perhaps by even double the 16 bytes. The natural storage > >> would be two arrays of doubles, but what about 1 linear array packed as > >> real/imag for each number. This will be able to store half as many numbers > >> but access to each will take advantage of efficient caching when > >> reading/writing memory. The JTransforms library (and others) may have ideas > >> for useful data structures. > >> > >> Unfortunately I cannot find if there was a Jira ticket for this or it is > >> only in the mailing archives. I've added links to the GSoC ticket for the > >> other tickets that mention complex number array utils and streams. However > >> these do not have a use case. Perhaps an investigation of the functionality > >> in the unreleased commons-number-complex-streams package would be the place > >> to start. The original author of that package is not actively involved in > >> the development any more. > >> > >> I should also point out the process for GSoC. It is outlined here [2]. In > >> short the initial period is about understanding what a project may involve. > >> Then you create a proposal for the project that is ranked with all the > >> other potential coders. Some projects are selected. It is only then that > >> the formal coding process begins and you have 12 weeks to create some code. > >> Previous years have had a timeline but this year the only date on the info > >> page is April 4 - 19 for when applications open. So right now we are in the > >> discussion phase. Any code developed now technically cannot be part of > >> GSoC, although this is not strictly enforced. > >> > >> Regards, > >> > >> Alex > >> > >> [1] https://github.com/wendykierp/JTransforms > >> [2] https://summerofcode.withgoogle.com/how-it-works > >> > >> > >> On Tue, 15 Mar 2022 at 02:23, Sumanth Rajkumar < > >> rajkumar.suma...@gmail.com> wrote: > >> > >>> Hi Alex/Gilles > >>> > >>> Thank you both for the detailed review. I think I have a better > >>> understanding now. > >>> > >>> 1) Refactor using Functional Interfaces and move current instance > >>> methods to static methods > >>> > >>> As suggested, I have attempted to refactor the Complex class to extract > >>> the functions out to static methods and use Functional interfaces > >>> > >>> I have added following Complex Functional interfaces similar to > >>> Functions and Operators defined in java.util.function but only using > >>> primitive doubles and avoiding any Object creation overheads > >>> > >>> @FunctionalInterface > >>> public interface ComplexFunction { > >>> <R> R apply(double r, double i, ComplexResult<R> result); > >>> } > >>> > >>> @FunctionalInterface > >>> public interface ComplexBiFunction { > >>> <R> R apply(double r1, double i1, double r2, double i2, > >>> ComplexResult<R> result); > >>> } > >>> > >>> > >>> @FunctionalInterface > >>> public interface ComplexResult<R> { > >>> R apply(double r, double i); > >>> default <V> ComplexResult<V> andThen(Function<? super R, ? extends > >>> V> after) { > >>> Objects.requireNonNull(after); > >>> return (r, i) -> after.apply(apply(r, i)); > >>> } > >>> default ComplexResult<R> compose(ComplexFunction before) { > >>> Objects.requireNonNull(before); > >>> return (r, i) -> before.apply(r, i, (x, y) -> apply(x, y)); > >>> } > >>> } > >>> > >>> > >>> > >>> I have refactored a few Functions (exp, conj, asin) and a few > >>> BFunctions (multiply, divide) as static functions into a new > >>> ComplexFunctions class > >>> > >>> I have modified the existing implementations for above in the Complex > >>> class to use the new static functions using the new Function interfaces > >>> > >>> I have also refactored ComplexList to apply the above function > >>> interfaces in forEach methods as suggested. These apply the results in > >>> place without incurring object overheads > >>> > >>> Refactored source is available here for review > >>> > >>> https://github.com/sumanth-rajkumar/commons-numbers/tree/sumanth-gsoc-22/commons-numbers-complex/src/main/java/org/apache/commons/numbers/complex > >>> > >>> Please let me know if the above changes are on expected lines? > >>> > >>> 2) List Implementation > >>> > >>> Thanks for the feedback on the license issue. I should be able > >>> refactor this as suggested just using the javadoc specifications > >>> > >>> > >>> -Sumanth. > >>> > >>> > >>> On Sun, 13 Mar 2022 at 21:39, Alex Herbert <alex.d.herb...@gmail.com> > >>> wrote: > >>> > >>>> Hi, > >>>> > >>>> Thanks for your interest in Commons Numbers. > >>>> > >>>> On Mon, 14 Mar 2022 at 00:09, Gilles Sadowski <gillese...@gmail.com> > >>>> wrote: > >>>> > >>>> > > > >>>> > > My partial implementation (with TODOs for many operations) is > >>>> available > >>>> > > here. > >>>> > > > >>>> > > >>>> https://github.com/sumanth-rajkumar/commons-numbers/blob/sumanth-gsoc-22/commons-numbers-complex/src/main/java/org/apache/commons/numbers/complex/ComplexList.java > >>>> > >>>> > >>>> Thanks for the implementation idea. This is a literal implementation of > >>>> a > >>>> List<Complex>. I think we should take a step back and find use cases > >>>> for a > >>>> large set of complex numbers. That should drive the API design. > >>>> > >>>> For example a common operation with complex numbers is to conjugate > >>>> multiply the fast fourier transform of two data arrays. The conjugate > >>>> multiply in the frequency domain is equivalent to the correlation in the > >>>> spatial domain. So I would require: > >>>> > >>>> ComplexList a; > >>>> ComplexList b; > >>>> > >>>> a.conj().multiply(b); > >>>> > >>>> But what is the most appropriate method to do this? I do not think we > >>>> want > >>>> to implement full matrix functionality for multiplication of arrays. > >>>> But we > >>>> should allow an API that makes this type of work efficient in terms of > >>>> memory usage, i.e. zero object allocation during computation (avoid > >>>> creating Complex instances) and ideally no intermediate array > >>>> allocation. > >>>> So in the above I do not want to create an entire list of conjugates > >>>> before > >>>> multiplying by another complex number. I also want the option to write > >>>> to a > >>>> new array or back to the original one. > >>>> > >>>> So should we have some type of generic interface for an operation on a > >>>> Complex: > >>>> > >>>> interface ComplexFunction { > >>>> interface ComplexResult { > >>>> void complex(double real, double imag); > >>>> } > >>>> void apply(double re, double im, ComplexResult); > >>>> } > >>>> > >>>> Then a list to allow operations on elements in place. For example to > >>>> compute the conjugate: > >>>> > >>>> ComplexList a; > >>>> a.forEach((re, im, result) -> result.complex(re, -im)); > >>>> > >>>> All operations in the Complex class can be rewritten as static methods > >>>> using a minimal set of functional interfaces. > >>>> > >>>> static void conj(double re, double im, ComplexResult result) { > >>>> result.complex(re, -im); > >>>> } > >>>> > >>>> The operation then becomes: > >>>> > >>>> ComplexList a; > >>>> a.forEach(Complex::conj); > >>>> > >>>> Which is a bit less cumbersome to write. > >>>> > >>>> Operations could be chained using a 'andThen' method in the interface: > >>>> > >>>> ComplexList a; > >>>> a.forEach(((ComplexFunction) Complex::conj).andThen(Complex::sin)); > >>>> > >>>> I've not considered exactly how this will work in practice. > >>>> > >>>> Functions that convert to a real number (such as abs()) could write 0 to > >>>> the imaginary. > >>>> > >>>> The specifics will depend on all the operations in Complex. So a start > >>>> point may be to refactor the class to expose all the instance methods as > >>>> static methods that take input and write the result to a destination. > >>>> These > >>>> can be used by (all) the Complex instance methods. I say (all) as some > >>>> may > >>>> be more efficient to leave as is, namely the simple methods like negate > >>>> or > >>>> conjugate, and the operations with real numbers. > >>>> > >>>> Re: Your code implementation > >>>> > >>>> I notice that the implementation for the expandable array backed list > >>>> and > >>>> hash code generation are "heavily reliant" on the JDK (11?) source for > >>>> ArrayList and Arrays. It is good practice to be aware of the license > >>>> terms > >>>> of any open source code project you may wish to use. The Oracle Open > >>>> JDK license terms are here [1]. This is under the GNU GPL v2 license > >>>> which > >>>> is not permissible to be used in an ASF project [2]. In general it is > >>>> fine > >>>> to look at the JDK source code to see how the function works or find > >>>> bugs. > >>>> However any new code reimplementing the functionality should be done as > >>>> if > >>>> blind to the code and only using a contractual specification of what the > >>>> code is meant to do. The modern javadoc effort by the JDK tries to > >>>> provide > >>>> a very good specification of each method contract. So it is often > >>>> possible > >>>> to write the same function from the javadoc description. An ideal > >>>> javadoc > >>>> should have this as its goal. Effectively this would be someone telling > >>>> you > >>>> what the code does but not showing you how: > >>>> > >>>> 1. A default array size of 10 > >>>> 2. Backing array will grow using a factor of 50% up to the maximum array > >>>> size > >>>> 3. Overflow of the maximum array size will result in OutOfMemoryError > >>>> 4. Index operations outside of the current list size [0, size) will > >>>> throw > >>>> ArrayIndexOutOfBoundException > >>>> 5. etc > >>>> > >>>> Alex > >>>> > >>>> [1] http://openjdk.java.net/legal/gplv2+ce.html > >>>> [2] https://www.apache.org/legal/resolved.html#category-x > >>>> > >>> --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
