Timeline for Efficient summation in Python
Current License: CC BY-SA 4.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 16, 2022 at 12:49 | history | edited | dankal444 | CC BY-SA 4.0 |
added 46 characters in body
|
| Dec 6, 2021 at 9:32 | audit | First answers | |||
| Dec 6, 2021 at 10:08 | |||||
| Nov 30, 2021 at 2:06 | audit | First answers | |||
| Nov 30, 2021 at 3:30 | |||||
| Nov 26, 2021 at 2:54 | audit | First answers | |||
| Nov 26, 2021 at 2:55 | |||||
| Nov 12, 2021 at 19:08 | comment | added | dankal444 | @Forss great you noticed it! edited answer and added your fix as method 4. In my tests for any N>200 numpy x*x is faster than pure python | |
| Nov 12, 2021 at 18:15 | history | edited | dankal444 | CC BY-SA 4.0 |
add optimization for fast numpy method
|
| Nov 12, 2021 at 13:44 | comment | added | Kelly Bundy |
@Forss Hmm, right. I used x*x out of habit, though it's a habit partially because of speed. And now that you pointed out, I was disappointed that NumPy doesn't just figure out once that it's one multiplication and applies that epiphany to the whole array. But then I remembered that we're using object and I guess NumPy doesn't make assumptions/typeanalysis there. Without the dtype, it does do x*x and x**2 equally fast. With both solutions using x*x, NumPy is a bit faster for me at n=1000, about equally fast at n=10000, and a bit slower at n=100000.
|
|
| Nov 12, 2021 at 12:17 | comment | added | Forss |
The pure python version is cheating a bit in the comparison by using x*x instead of x**2 like the other methods. Changing to x*x for the numpy solution it is the fastest method for larger n (on my computer).
|
|
| Nov 8, 2021 at 4:37 | comment | added | ramzeek |
Running the correction to a np.object gives me this DeprecationWarning: np.object is a deprecated alias for the builtin .object. To silence this warning, use object by itself. Doing this will not modify any behavior and is safe. Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations
|
|
| Nov 7, 2021 at 21:19 | comment | added | user2357112 | In general, NumPy cannot optimize any operations on arrays of object dtype. Unless you have a very specific, not-performance-related reason to use an object array, it's usually better to use either a list or an array with a native dtype. | |
| Nov 7, 2021 at 21:17 | comment | added | user2357112 |
numpy.object is not a special NumPy thing. It's just object. It's only in the numpy namespace for backward compatibility.
|
|
| Nov 7, 2021 at 16:06 | comment | added | dankal444 | @KellyBundy edited then, thank you, learned a lot by your answers and comments | |
| Nov 7, 2021 at 16:04 | history | edited | dankal444 | CC BY-SA 4.0 |
added 443 characters in body
|
| Nov 7, 2021 at 15:50 | comment | added | Kelly Bundy | I don't think it fits into mine (since I'm only talking about my approach and would like to keep it that way), but it would make yours better. | |
| Nov 7, 2021 at 15:48 | comment | added | dankal444 | @KellyBundy I thought you will add this to your ansewer, I can edit mine if you prefer it this way | |
| Nov 7, 2021 at 15:39 | comment | added | Kelly Bundy | Because at the moment I think it might mislead casual readers into thinking "Ah ok, NumPy makes this fast". Which is wrong, since the NumPy one is faster not because it uses NumPy but because it uses a different algorithm, which the non-NumPy solution could easily use as well, and should use for meaningful comparison. | |
| Nov 7, 2021 at 13:14 | history | edited | Peter Mortensen | CC BY-SA 4.0 |
Active reading [<https://en.wikipedia.org/wiki/NumPy>].
|
| Nov 6, 2021 at 19:27 | comment | added | Kelly Bundy |
I'd try the equivalent non-NumPy version as well, you'll likely find it gets faster than the NumPy version. For example result1 = sum(x*x * ysum for x, ysum in enumerate(itertools.accumulate(range(n+1)))) or ysum = 0; result1 = sum(x*x * (ysum := ysum + x) for x in range(n+1))
|
|
| Nov 6, 2021 at 18:31 | vote | accept | Adam | ||
| Nov 6, 2021 at 17:21 | comment | added | Kelly Bundy | @dankal444 And real fast method 0.000001 s :-P | |
| Nov 6, 2021 at 16:51 | comment | added | dankal444 |
@diggusbickus because np.int64 has only 64 bits to store integers, Python int can be as big as your RAM will allow it. By using "generic" np.object you assure that numpy does not convert int to np.int64.
|
|
| Nov 6, 2021 at 16:40 | comment | added | folen gateis | why np.object instead of np.int64 then? | |
| Nov 6, 2021 at 16:38 | comment | added | dankal444 | For N=100 000, Slow method: 588.831 s Fast method: 0.0500 s | |
| Nov 6, 2021 at 16:37 | history | answered | dankal444 | CC BY-SA 4.0 |