optimization question

[Andrew Koenig]

Tim> [Andrew Koenig]
>> If s and t are strings, and I evaluate an expression of the form
>> 
>> s[i:j] == t
>> 
>> can I count on the implementation not to form s[i:j] as a new
>> substring?

Tim> Yes, but not for the reason you're picturing <wink>: strings are
Tim> immutable and don't support slice assignment, i.e. this code
Tim> raises TypeError.

Beg pardon?  I see no assignment here.

>> Suppose, for instance, that s is many megabytes long, i and j are
>> far apart, and t is very short.  Can I assume that the execution
>> time for this comparison will be no worse than O(len(t)), or must I
>> assume O(j-1)?

Tim> It's O(1) but in a useless sense.  If you do the equivalent with
Tim> array.array('c') objects, or even lists of characters, it's then
Tim> true that no sub-array i:j is formed, and it does take O(len(t))
Tim> time to copy in the new slice.  It *also* takes O(len(s)-j) time
Tim> to "shift over" the tail end of s, unless len(t) == j-i (in which
Tim> case no tail shift is needed).  All assuming 0 <= i <= j <=
Tim> len(s).

Beg pardon?  Where am I shifting characters?

Did you think I was writing

        s[i:j] = t

?  I really did mean ==, not =, and that's what I think I wrote.


-- 
Andrew Koenig, ark at research.att.com, http://www.research.att.com/info/ark