Jan-18-2017, 09:26 PM
Mekire: Migrating a thread from the old forum which I think provided good discussion so as to avoid linking to the dead forum.
Ok, so first off I have a dual boot setup with Windows 7 and Linux Mint 13. I generally work in Windows because I'm honestly not so comfortable in Linux but I like to be able to test compatibility and such when necessary.
Brought on by a recent thread, I realized that certain operations were not performing the same on the two OS.
Specifically string concatenation and the str.join method. My original assertion was that the string concatenation method should be completely avoided because it goes quadratic.
Take the following code (still using time instead of timeit; still lazy):
Then Metulburr showed me his results for the same code, which completely contradicted mine. I rebooted to Linux and tested the same code.
Result with Linux on the same computer:
Aside from the standard, "Lol Windows," line of reasoning; what would be causing the time complexity of concatenation to be O(n^2) with one operating system, and o(n) with the other?
-Mek
Ok, so first off I have a dual boot setup with Windows 7 and Linux Mint 13. I generally work in Windows because I'm honestly not so comfortable in Linux but I like to be able to test compatibility and such when necessary.
Brought on by a recent thread, I realized that certain operations were not performing the same on the two OS.
Specifically string concatenation and the str.join method. My original assertion was that the string concatenation method should be completely avoided because it goes quadratic.
Take the following code (still using time instead of timeit; still lazy):
import time def make_string_concat(num): l = '' for i in xrange(num): l += '{}\n'.format(i) return l def make_string_join(num): return "\n".join(str(i) for i in xrange(num))+"\n" ### if __name__ == "__main__": NUMBERS = [1000000,2000000,3000000] for number in NUMBERS: print("n = {}".format(number)) start = time.time() DATA1 = make_string_join(number) print("Time to generate data (str.join): {}".format(time.time()-start)) start = time.time() DATA2 = make_string_concat(number) print("Time to generate data (concatenation): {}\n".format(time.time()-start))So on windows the result I get is:
>>> n = 1000000 Time to generate data (str.join): 0.389999866486 Time to generate data (concatenation): 2.88599991798 n = 2000000 Time to generate data (str.join): 0.655000209808 Time to generate data (concatenation): 12.2779998779 n = 3000000 Time to generate data (str.join): 0.99799990654 Time to generate data (concatenation): 28.2520000935 >>>It would appear that the str.join stays linear while the concatenation blows up quadratically.
Then Metulburr showed me his results for the same code, which completely contradicted mine. I rebooted to Linux and tested the same code.
Result with Linux on the same computer:
>>> n = 1000000 Time to generate data (str.join): 0.224174022675 Time to generate data (concatenation): 0.316344022751 n = 2000000 Time to generate data (str.join): 0.449282884598 Time to generate data (concatenation): 0.658910989761 n = 3000000 Time to generate data (str.join): 0.677663803101 Time to generate data (concatenation): 0.943947792053 >>>Here, while the join method is still superior, they both appear to have linear time complexity.
Aside from the standard, "Lol Windows," line of reasoning; what would be causing the time complexity of concatenation to be O(n^2) with one operating system, and o(n) with the other?
-Mek