2 ms·
Added in edit: Why do you think the last version must be faster? In short, if you implement these things on multi-core machines, then no, it isn't obvious that
by ColinWright 12y ago
Added in edit: Why do you think the last version must be faster?
In short, if you implement these things on multi-core machines, then no, it isn't obvious that the last algorithm will be the fastest. With modern experimental parallelizing compilers on suitable hardware, the exact algorithm matters, and these show significantly different results.
I spend most of my time working on "odd" hardware configurations, and as a result, sometimes these more "interesting" algorithms are the ones I immediately turn to rather than doing what others think of as instantly obvious.
- kabdib 12y agoI would expect that for a vector of things in Python, iteration would be fastest. The array is in memory, right there. Spooling up a series of parallel threads (and in Python, establishing the right locking, whatever that is...) just to distribute a bunch of ADD operations seems like a waste of time. If the problem domain is indeed massive and needs to be parallel, okay. But the introduction was about doing some simple image processing, so the direction that this guy took with parallelism surprised me. I wouldn't call this a waste of time (I learned some more Python, which is nice). But I think I would have had this done in a minute or two and moved on.
- srean 12y agoThat sure surprised me, I would have rooted for reduce. May be lambda overhead is screwing it up. Could you try the reduction with from operator import add I cannot try it out on Colin's version of Python, however on Python 2.7.6 | 32-bit | [GCC 4.1.2 20080704] from operator import add def sum1(l): return reduce(lambda a,b:a+b,l) def sum2(l): return reduce(add,l) The times to compute sum1(l) and sum2(l) on xrange(3333333) are 11.69s and 6.38s respectively. So sum2 is about twice faster, which is expected. The timings are the minimum of 5 runs. Given Colin's reduce was about twice slower than his for loop, there is a fair chance that the updated reduce will beat the for loop occasionally. I was surprised that trying the same on an array turned out to be marginally slower than using an xrange. I would have expected the array to be faster. xrange is possibly faster because it can be held in cache whereas the array would definitely spill outside, although I expected locality to be a win.