ark at research.att.com
Sun Aug 11 20:47:12 CEST 2002
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
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 <=
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
More information about the Python-list