RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from http://mail.python.org/pipermail/python-dev/attachments/20140807/83fcb573/attachment.html below:

<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Aug 4, 2014 at 11:10 AM, Steven D'Aprano <span dir="ltr"><<a href="mailto:steve@pearwood.info" target="_blank">steve@pearwood.info</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div>On Mon, Aug 04, 2014 at 09:25:12AM -0700, Chris Barker wrote:<br>

<br>

> Good point -- I was trying to make the point about .join() vs + for strings<br>
> in an intro python class last year, and made the mistake of having the<br>
> students test the performance.<br>
><br>
> You need to concatenate a LOT of strings to see any difference at all</div></blockquote><div>Â </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">

If only that were the case, but it isn't. Here's a cautionary tale for<br>

how using string concatenation can blow up in your face:<br>
<br>
Chris Withers asks for help debugging HTTP slowness:<br>
<a href="https://mail.python.org/pipermail/python-dev/2009-August/091125.html" target="_blank">https://mail.python.org/pipermail/python-dev/2009-August/091125.html</a></blockquote><div><br></div><div><br></div><div>Thanks for that -- interesting story. note that that was not suing sum() in that case though, which is really the issue at hand.Â </div>

<div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">It shouldn't be hard to demonstrate the difference between repeated<br>

string concatenation and join, all you need do is defeat sum()'s<br>

prohibition against strings. Run this bit of code, and you'll see a<br>
significant difference in performance, even with CPython's optimized<br>
concatenation:<br></blockquote><div><br></div><div>well, that does look compelling, but what it shows is that sum(a_list_of_strings) is slow compared to ''.join(a_list_of_stings). That doesn't surprise me a bit -- this is really similar to why:</div>

<div><br></div><div>a_numpy_array.sum()</div><div><br></div><div>is going to be a lot faster than:</div><div><br></div><div>sum(a_numpy_array)</div><div><br></div><div>and why I'll tell everyone that is working with lots of numbers to use numpy. ndarray.sum know what data type it's deaing with,a nd can do the loop in C. similarly with ''.join() (though not as optimized.Â </div>

<div><br></div><div>But I'm not sure we're seeing the big O difference here at all -- but rather the extra calls though each element in the list's __add__ method.</div><div><br></div><div>In the case where you already HAVE a big list of strings, then yes, ''.join is the clear winner.Â </div>

<div><br></div><div>But I think the case we're often talking about, and I've tested with students, is when you are building up a long string on the fly out of little strings. In that case, you need to profile the full "append to list, then call join()", not just the join() call:</div>

<div><br></div><div># continued adding of strings ( O(n^2)? )</div><div><div>In [6]: def add_strings(l):</div><div>Â Â ...: Â Â s = ''</div><div>Â Â ...: Â Â for i in l:</div><div>Â Â ...: Â Â Â Â s+=i</div><div>Â Â ...: Â Â return s</div>

</div><div><br></div><div>Using append and then join ( O(n)? )</div><div><div>In [14]: def join_strings(list_of_strings):</div><div>Â Â ....: Â Â l = []</div><div>Â Â ....: Â Â for i in list_of_strings:</div><div>Â Â ....: Â Â Â Â l.append(i)</div>

<div>Â Â ....: Â Â return ''.join(l)</div></div><div><br></div><div><div>In [23]: timeit add_strings(strings)</div><div>1000000 loops, best of 3: 831 ns per loop</div><div><br></div><div>In [24]: timeit join_strings(strings)</div>

<div>100000 loops, best of 3: 1.87 Âµs per loop</div></div><div><br></div><div>## hmm -- concatenating is faster for a small list of tiny strings....</div><div><br></div><div><div>In [31]: strings = list('Hello World')* 1000</div>

</div><div><br></div><div>strings *= 1000</div><div><div>In [26]: timeit add_strings(strings)</div>

<div>1000 loops, best of 3: 932 Âµs per loop</div><div><br></div><div>In [27]: timeit join_strings(strings)</div><div>1000 loops, best of 3: 967 Âµs per loop</div></div><div><br></div><div>## now about the same.</div><div>

<br>

</div><div>In [31]: strings = list('Hello World')* 10000</div><div><br></div><div>In [29]: timeit add_strings(strings)<br></div><div><div>100 loops, best of 3: 9.44 ms per loop</div><div><br></div><div>In [30]: timeit join_strings(strings)</div>

<div>100 loops, best of 3: 10.1 ms per loop</div><div>

<br></div></div><div>still about he same?</div><div><br></div><div><div>In [31]: strings = list('Hello World')* 1000000</div><div><br></div><div>In [32]: timeit add_strings(strings)</div><div>1 loops, best of 3: 1.27 s per loop</div>

<div><br></div><div>In [33]: timeit join_strings(strings)</div><div>1 loops, best of 3: 1.05 s per loop</div></div><div><br></div><div>there we go -- slight advantage to joining.....</div><div><br></div><div>So this is why we've said that the common wisdom about string concatenating isn't really a practical issue.</div>

<div><br></div><div>But if you already have the strings all in a list, then yes, join() is a major win over sum()</div><div><br></div><div>In fact, I tried the above with sum() -- and it was really, really slow. So slow I didn't have the patience to wait for it.</div>

<div><br></div><div>Here is a smaller example:</div><div><br></div><div><div>In [22]: strings = list('Hello World')* 10000</div><div><br></div><div>In [23]: timeit add_strings(strings)</div><div>100 loops, best of 3: 9.61 ms per loop</div>

<div><br></div><div>In [24]: timeit sum( strings, Faker() )</div><div>1 loops, best of 3: 246 ms per loop</div></div><div><br></div><div>So why is sum() so darn slow with strings compared to a simple loop with += ?</div>

<div>
<br></div><div>(and if I try it with a list 10 times as long it takes "forever")</div><div><br></div><div>Perhaps the http issue cited was before some nifty optimizations in current CPython?</div><div><br></div>

<div>-Chris</div><div><br></div><div><br></div><div><br></div></div><br clear="all"><div><br></div>-- <br><br>Christopher Barker, Ph.D.<br>Oceanographer<br><br>Emergency Response Division<br>NOAA/NOS/OR&R Â Â Â Â Â Â <a href="tel:%28206%29%20526-6959" value="+12065266959" target="_blank">(206) 526-6959</a>Â Â voice<br>

7600 Sand Point Way NE Â Â <a href="tel:%28206%29%20526-6329" value="+12065266329" target="_blank">(206) 526-6329</a>Â Â fax<br>

Seattle, WA Â 98115 Â Â Â Â <a href="tel:%28206%29%20526-6317" value="+12065266317" target="_blank">(206) 526-6317</a>Â Â main reception<br><br><a href="mailto:Chris.Barker@noaa.gov" target="_blank">Chris.Barker@noaa.gov</a>
</div></div>

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4