From: Tero Tilus <tero@tilus.net>
To: Sup developers <sup-devel@rubyforge.org>
Subject: Re: [sup-devel] Message#text_to_chunks performance
Date: Tue, 21 Dec 2010 23:45:14 +0200 [thread overview]
Message-ID: <1292967783-sup-4582@tilus.net> (raw)
In-Reply-To: <1288264300-sup-7747@tilus.net>
[-- Attachment #1: Type: text/plain, Size: 89 bytes --]
And here's (finally) the patch.
--
Tero Tilus ## 050 3635 235 ## http://tero.tilus.net/
[-- Attachment #2: 0001-Message-text_to_chunks-avoid-O-n-2-behavior-on-seq.patch --]
[-- Type: application/octet-stream, Size: 1266 bytes --]
From c496e68930f9c0e134f37c060508d52cafd06bcc Mon Sep 17 00:00:00 2001
From: Tero Tilus <tero@tilus.net>
Date: Thu, 28 Oct 2010 14:01:12 +0300
Subject: [PATCH] Message#text_to_chunks: avoid O(n^2) behavior on sequences of blank lines
Signed-off-by: Tero Tilus <tero@tilus.net>
---
lib/sup/message.rb | 13 ++++++++++++-
1 files changed, 12 insertions(+), 1 deletions(-)
diff --git a/lib/sup/message.rb b/lib/sup/message.rb
index cf0e505..41e6486 100644
--- a/lib/sup/message.rb
+++ b/lib/sup/message.rb
@@ -590,9 +590,20 @@ private
state = :text # one of :text, :quote, or :sig
chunks = []
chunk_lines = []
+ nextline_index = -1
lines.each_with_index do |line, i|
- nextline = lines[(i + 1) ... lines.length].find { |l| l !~ /^\s*$/ } # skip blank lines
+ if i >= nextline_index
+ # look for next nonblank line only when needed to avoid O(n²)
+ # behavior on sequences of blank lines
+ if nextline_index = lines[(i+1)..-1].index { |l| l !~ /^\s*$/ } # skip blank lines
+ nextline_index += i + 1
+ nextline = lines[nextline_index]
+ else
+ nextline_index = lines.length
+ nextline = nil
+ end
+ end
case state
when :text
--
1.5.6.5
[-- Attachment #3: Type: text/plain, Size: 143 bytes --]
_______________________________________________
Sup-devel mailing list
Sup-devel@rubyforge.org
http://rubyforge.org/mailman/listinfo/sup-devel
next prev parent reply other threads:[~2010-12-21 21:45 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-10-28 12:05 Tero Tilus
2010-11-04 16:05 ` Rich Lane
2010-12-21 21:45 ` Tero Tilus [this message]
2010-12-23 18:38 ` Rich Lane
2011-01-19 3:12 ` Rich Lane
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1292967783-sup-4582@tilus.net \
--to=tero@tilus.net \
--cc=sup-devel@rubyforge.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox