[Python-Dev] Socket timeout patch
Tim Peters
tim.one@comcast.net
Mon, 03 Jun 2002 13:32:27 -0400
[Guido]
>>> - Maybe changing the write buffer to a list makes sense too?
[mgilfix@eecs.tufts.edu]
>> I could do this. Then just do a join before the flush. Is the append
>> /that/ much faster?
[Guido]
> Depends on how small the chunks are you write. Roughly, repeated list
> append is O(N log N), while repeated string append is O(N**2).
Repeated list append is O(N) amortized (a single append may take O(N) time
all by itself, but if you do N of them in a row the time is still no worse
than O(N) overall; a possible conceptual difficulty may arise here because
the value of "N" changes over time, and while growing to a total of size N
may require O(log N) whole-list copies, each of the copies involves far
fewer elements than the final value of N -- if you add up all these smaller
values of N in the worst case, the sum is O(N) wrt the final value of N, and
so it's worst-case O(N) overall wrt the final value of N).