4 ms·
The author states: "There's a general technique to avoid quadratic behavior in algorithms like this. I coded it as follows for strings of exactly 256 items:"
by bogomipz 10y ago
The author states:
"There's a general technique to avoid quadratic behavior in algorithms like this. I coded it as follows for strings of exactly 256
items:"
def f5(list):
string = ""
for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
s = ""
for character in map(chr, list[i:i+16]):
s = s + character
string = string + s
return string
I am not understanding what the technique is or why using a step size of 16 in the range function is significant. Can anyone enlighten me about this and what the technique is? Does this technique have a name?
- fabianhjr 10y agoA wild guess on what he is trying to do: - Use Vector Processor instead of Scalar Processor, SIMD(SSE/AVX/etc) has 16 128-bit registers. In the wikipedia entry of SSE it says that SSE2 has support for 16 chars. Things that don't add up: - This should be a compiler optimization - This makes something readable unnecessarily complex - s is mutating - You could eliminate the inner loop and s
- anuraaga 10y agoFound a long but thorough answer here - doesn't become linear but does go down to n log n. The step size of 16 is chosen as it is √256 http://cs.stackexchange.com/questions/52360/from-guidos-essays-how-does-this-function-avoid-quadratic-behavior-in-a-string http://cs.stackexchange.com/questions/52360/from-guidos-essa...
- tfm 10y agoThe idea is to reduce the amount of redundant copying of characters: you end up doing a few more concatenations in the outer loop, but the concatenations in the inner loop are of short strings. Importantly, if you remove the restriction of the input list being "exactly 256 items", then the method is still quadratic. A linear-time algorithm for this would copy each input character exactly once, which is effectively what the method based on array.tostring() does. The chunk size of 16 is not as significant as the technique of constructing+concatenating chunks, although it is optimal for input length 256. In general I think you'd want a chunk size about the square-root of the expected input length, to minimise the number of copied characters. EDIT: maths Concatenating strings of length M and N is linear in O(M+N), because that's how many characters you're copying. Number of characters copied if you construct a string of length N by concatenating one character at a time = (0+1) + (1+1) + (2+1) + (3+1) + ... + ((N-1)+1) + (N+1) = (N +1)*N / 2 Number of characters copied if you construct a string of length N by concatenating a chunk of length 16 each time = (0+16) + (16+16) + (32+16) + ... + ((N-16)+16) = 16*(0+1) + 16*(1+1) + 16*(2+1) + ... = 16 * (N/16 +1)*(N/16) / 2 ^^^^^^^^^^^^^^^ This is where the "technique" comes in: although the algorithm is still quadratic you're effectively moving a constant factor out the front. Note that you also have the cost of constructing the chunks each time, which becomes the dominant cost if you have too many chunks. In general, if you have a length kM string which you construct from k chunks of length M, the number of characters copied = M * (k+1)*k / 2 + k * (M+1)*M / 2 ... which (rounding and integer constraints aside) is minimised for M = k, i.e. when the chunk size is the square root of the input length. Hence, for input length 256 we take chunk size 16.
- bogomipz 10y agoI see, that makes sense about reducing the constant. Interesting. Thanks for the great explanation.