[Patches] [ python-Patches-1209527 ] Optimization for textwrap

[SourceForge.net]

Patches item #1209527, was opened at 2005-05-26 18:09
Message generated for change (Settings changed) made by rhettinger
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1209527&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Library (Lib)
Group: Python 2.5
Status: Open
Resolution: None
Priority: 5
Submitted By: Connelly (connelly)
>Assigned to: Raymond Hettinger (rhettinger)
Summary: Optimization for textwrap

Initial Comment:

This patch speeds up the textwrap module, so that it
takes O(n) time to process n chunks rather than the
O(n^2) time that textwrap previously took.

This makes textwrap much faster for large texts (for
example, the patched version runs textwrap.fill('foo' *
100000) 80 times faster than the unpatched version).

----------------------------------------------------------------------

Comment By: Reinhold Birkenfeld (birkenfeld)
Date: 2005-07-09 06:15

Message:
Logged In: YES 
user_id=1188172

I've applied the original patch, ensured the test suite ran
and measured the same speedup as Connelly.

Looks like a sound addition.
Another option is, as he said, using collections.deque or an
substitute class for compatibility.

----------------------------------------------------------------------

Comment By: Connelly (connelly)
Date: 2005-07-08 18:49

Message:
Logged In: YES 
user_id=1039782

Personally, I need linear running time for this module, so I 
contributed the patch in the hope that others would find it 
useful.  The practical result is that parsing a 5 MB unwrapped 
text file takes an order of seconds with the patch, and > 10 
minutes without the patch (3 GHz Pentium).

If the code is written with a deque or queue, there would be a 
similar speed incease, since deque operations are O(1).  Is 
the patch not 'clean enough' code-wide?  (I could recode it to 
use collections.deque or else a simple dummy queue if 
collections is not available).


----------------------------------------------------------------------

Comment By: Jeff Epler (jepler)
Date: 2005-06-03 08:49

Message:
Logged In: YES 
user_id=2772

I didn't benchmark the speed increase, but I verified that
on my system 'test_textwrap.py' still completes
successfully.  I also looked at the patch and found the
change to be straightforward.  However, I wonder if the
speed increase would be nearly as great if 
collections.deque was used instead of the reversed list. 
Unfortunately, the textwrap module seems to intend
portability with older versions of Python, which would not
work if the collections module is used.

----------------------------------------------------------------------

Comment By: Connelly (connelly)
Date: 2005-05-27 11:37

Message:
Logged In: YES 
user_id=1039782

I assign the Copyright for this patch to the Python Software
Foundation.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1209527&group_id=5470