Time complexity different between operating systems. Why?

A forum for general discussion of the Python programming language.

Time complexity different between operating systems. Why?

Postby Mekire » Sat May 18, 2013 5:02 am

migrated
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

Re: Time complexity different between operating systems. Why

Postby metulburr » Sat May 18, 2013 12:37 pm

migrated
User avatar
metulburr
 
Posts: 2244
Joined: Thu Feb 07, 2013 4:47 pm
Location: Elmira, NY

Re: Time complexity different between operating systems. Why

Postby hrs » Sat May 18, 2013 1:33 pm

I got this from cProfile
Code: Select all
         12000036 function calls in 6.926 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    6.926    6.926 <string>:1(<module>)
        3    0.000    0.000    3.288    1.096 con.py:10(make_string_join)
  6000003    2.052    0.000    2.052    0.000 con.py:11(<genexpr>)
        1    0.001    0.001    6.926    6.926 con.py:14(main)
        3    1.843    0.614    3.636    1.212 con.py:4(make_string_concat)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  6000009    1.794    0.000    1.794    0.000 {method 'format' of 'str' objects}
        3    1.237    0.412    3.288    1.096 {method 'join' of 'str' objects}
       12    0.000    0.000    0.000    0.000 {time.time}

So it looks like benchmarking a generator expression against string concat.

edit: This is on linux btw.
hrs
 
Posts: 86
Joined: Thu Feb 07, 2013 9:26 pm

Re: Time complexity different between operating systems. Why

Postby casevh » Sat May 18, 2013 3:45 pm

migrated
casevh
 
Posts: 114
Joined: Sat Feb 09, 2013 7:35 am

Re: Time complexity different between operating systems. Why

Postby micseydel » Sun May 19, 2013 2:40 am

Thanks as always for the information casevh! I was really curious about this, I had a lot of the information you provided here but was missing some important stuff!
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.
User avatar
micseydel
 
Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Time complexity different between operating systems. Why

Postby snippsat » Sun May 19, 2013 3:21 am

Tnx for good explanation casevh.
It would appear that the str.join stays linear while the concatenation blows up quadratically.

It`s more that memory use blow up bye the use of +=.

Some more info about implementation in Python source string concatenation VS list join
+= is fastest if string length < 40.
http://stackoverflow.com/questions/3055 ... s-str-join
Code: Select all
Iterations: 1,000,000       
String Length:  Time +=     Time ''.join()
1                0.953990        1.3280
4                1.233990        1.8140
6                1.516000        2.2810
12               2.250000        3.2500
80              15.530900       12.3750
222            101.797000       30.5160
443            238.063990       57.2030
We will be moving to python-forum.io on October 1 2016
User avatar
snippsat
 
Posts: 1251
Joined: Thu Feb 21, 2013 12:04 am

Re: Time complexity different between operating systems. Why

Postby micseydel » Sun May 19, 2013 4:41 am

Yeah, but when it's that fast the speed different between the two likely doesn't matter. I'd say stylistically it's preferable to use the more robust version.
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.
User avatar
micseydel
 
Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA


Return to General Discussions

Who is online

Users browsing this forum: No registered users and 1 guest