On 11/14/2011 04:23 PM, David Cournapeau wrote:

...

On Mon, Nov 14, 2011 at 12:46 PM, Andreas Müller wrote:

...

Hi everybody. When I did some normalization using numpy, I noticed that numpy.std uses more ram than I was expecting. A quick google search gave me this: http://luispedro.org/software/ncreduce The site claims that std and other reduce operations are implemented naively with many temporaries. Is that true? And if so, is there a particular reason for that? This issues seems quite easy to fix. In particular the link I gave above provides code. The code provided only implements a few special cases: being more efficient in those cases only is indeed easy. I am particularly interested in the std function. Is this implemented as a separate function or an instantiation of a general reduce operations?

_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion The'On-line algorithm' (http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_alg...) http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_alg... could save you storage. I would presume if you know cython that you can

On 11/14/2011 10:05 AM, Andreas Müller wrote: probably make it quick as well (to address the loop over the data). Bruce

On 11/15/2011 05:46 PM, Andreas Müller wrote:

On 11/15/2011 04:28 PM, Bruce Southey wrote:

...

On 11/14/2011 10:05 AM, Andreas Müller wrote:

...

On 11/14/2011 04:23 PM, David Cournapeau wrote:

...

On Mon, Nov 14, 2011 at 12:46 PM, Andreas Müller wrote:

...

Hi everybody. When I did some normalization using numpy, I noticed that numpy.std uses more ram than I was expecting. A quick google search gave me this: http://luispedro.org/software/ncreduce The site claims that std and other reduce operations are implemented naively with many temporaries. Is that true? And if so, is there a particular reason for that? This issues seems quite easy to fix. In particular the link I gave above provides code. The code provided only implements a few special cases: being more efficient in those cases only is indeed easy. I am particularly interested in the std function. Is this implemented as a separate function or an instantiation of a general reduce operations?

_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion The'On-line algorithm' (http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_alg...) http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_alg... could save you storage. I would presume if you know cython that you can probably make it quick as well (to address the loop over the data).

My question was more along the lines of "why doesn't numpy do the online algorithm".

To be more precise, even not using the online version but computing E(X^2) and E(X)^2 would be good. It seems numpy centers the whole dataset. Otherwise I can't explain why the memory needed should depend on the number of examples.

On 11/15/2011 06:02 PM, Warren Weckesser wrote:

On Tue, Nov 15, 2011 at 10:48 AM, Andreas Müller mailto:amueller@ais.uni-bonn.de> wrote:

On 11/15/2011 05:46 PM, Andreas Müller wrote:

...

On 11/15/2011 04:28 PM, Bruce Southey wrote:

...

On 11/14/2011 10:05 AM, Andreas Müller wrote:

...

On 11/14/2011 04:23 PM, David Cournapeau wrote:

...

On Mon, Nov 14, 2011 at 12:46 PM, Andreas Müller mailto:amueller@ais.uni-bonn.de wrote:

...

Hi everybody. When I did some normalization using numpy, I noticed that numpy.std uses more ram than I was expecting. A quick google search gave me this: http://luispedro.org/software/ncreduce The site claims that std and other reduce operations are implemented naively with many temporaries. Is that true? And if so, is there a particular reason for that? This issues seems quite easy to fix. In particular the link I gave above provides code.

The code provided only implements a few special cases: being more efficient in those cases only is indeed easy.

I am particularly interested in the std function. Is this implemented as a separate function or an instantiation of a general reduce operations?

_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org mailto:NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion

The'On-line algorithm' (http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_alg...) http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_alg... could save you storage. I would presume if you know cython that you can probably make it quick as well (to address the loop over the data).

My question was more along the lines of "why doesn't numpy do the online algorithm".

To be more precise, even not using the online version but computing E(X^2) and E(X)^2 would be good. It seems numpy centers the whole dataset. Otherwise I can't explain why the memory needed should depend on the number of examples.

Yes, that is what it is doing. See line 63 in the function _var(), which is called by _std(): https://github.com/numpy/numpy/blob/master/numpy/core/_methods.py

Thanks for the clarification. I thought the function was somewhere in the C code - don't know why. I'll see if I can reformulate the function.

On Tue, Nov 15, 2011 at 16:55, Gael Varoquaux wrote:

On Tue, Nov 15, 2011 at 05:46:52PM +0100, Andreas Müller wrote:

...

   My question was more along the lines of "why doesn't numpy do the online    algorithm".

It's probably a matter of nobody having had the time and the urge to code it, _and_ do all the extra steps necessary to integrate to the core numpy: working on n dimensions, suporting all the options of the current implementation, doing the tests, doing the docs.

I don't think that anybody would frown upon a pull request that implements a better algorithm. It's just work, as you know given your contributions to other project.

Actually, last time I suggested it, it was brought up that the online algorithms can be worse numerically. I'll try to find the thread. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth."   -- Umberto Eco

On 11/15/2011 07:03 PM, Gael Varoquaux wrote:

On Tue, Nov 15, 2011 at 05:57:14PM +0000, Robert Kern wrote:

...

Actually, last time I suggested it, it was brought up that the online algorithms can be worse numerically. I'll try to find the thread. Indeed, especially for smallish datasets where the memory overhead is not an issue. I think that this is a common situation for which there is not _one_ good algorithm to solve the problem. IMHO the best way forward is to propose several options to the user, either with several function, or with a keyword argument.

I thought it would be possible to do the "two pass algorithm" (as wikipedia calls it) without copying the dataset. I guess I didn't really think it through. That should be possible doing a custom reduce operation, right? I don't know in how far this would have numerical problems.