Efficiency Crash Course

A place where you can post Python-related tutorials you made yourself, or links to tutorials made by others.

Efficiency Crash Course

Postby micseydel » Tue Jan 20, 2015 4:57 am

User avatar
micseydel
 
Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Efficiency Crash Course

Postby Mekire » Tue Jan 20, 2015 2:00 pm

Very nice. I wouldn't mind a follow up tutorial that went into more depth on the common time complexities encountered. I still, for instance, find correctly identifying O(nlogn) to be tricky.

On the point of your example, using string concatenation does, as you alluded to, sometimes make it hard to see these results in the wild. You could go into more detail with it here, but I think perhaps this past thread might suffice:
Time complexity different between operating systems. Why?

I tend to use examples with the list.count() builtin vs dictionary counting (or using collections.Counter) to illustrate the quadratic vs linear time of counting items in a large sequence.

I for instance have often seen people do things like this (and think themselves very clever):
Code: Select all
count_items = {item:items.count(item) for item in items}
Not realizing that this is O(n^2).

Whereas the less intuitive:
Code: Select all
count_items = {}
for item in items:
    count_items[item] = count_items.get(item, 0)+1
performs in O(n).

-Mek
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

Re: Efficiency Crash Course

Postby micseydel » Tue Feb 17, 2015 1:25 am

Thank you for the comments Mek. Apologies on taking so long to reply, I hadn't read your comments yet and was going to reply and also duplicate the efforts you mention below (which I now won't).

Mekire wrote:I still, for instance, find correctly identifying O(nlogn) to be tricky.

Since things are usually related to loops, you can look at it in terms of multiplying the number of iterations by the time each iteration takes. An O(n log n) sorting algorithm for example is either going to iterate n times, doing log n work each time, or else will iterate log n times and each iteration do n work. I tried to make this as brief as possible yet still get a basis, I realize it's not exhaustive. I want to make sure it's short enough that people will actually read it haha. We could start a series on it though.

Mekire wrote:On the point of your example, using string concatenation does, as you alluded to, sometimes make it hard to see these results in the wild. You could go into more detail with it here, but I think perhaps this past thread might suffice:
Time complexity different between operating systems. Why?

Thanks for the link to that thread, it's probably adequate. I was going to waste time elaborating but now I don't have to :)
I would mention though that you can verify it empirically by creating a dummy variable on the string which would have been modified in-place, since Python won't modify the string if there is more than one reference to it. Perhaps a small code sample is worth it, or it could be left as an exercise to the reader as so many of students' favorite textbooks tend to do ;)

Mekire wrote:I tend to use examples with the list.count() builtin vs dictionary counting (or using collections.Counter) to illustrate the quadratic vs linear time of counting items in a large sequence.

I for instance have often seen people do things like this (and think themselves very clever):
Code: Select all
count_items = {item:items.count(item) for item in items}
Not realizing that this is O(n^2).

Whereas the less intuitive:
Code: Select all
count_items = {}
for item in items:
    count_items[item] = count_items.get(item, 0)+1
performs in O(n).

-Mek

I think this is a wonderful example. Do you think this should be incorporated? Left as a comment here? Part of another thread?

I'd like to approval from one or two people before considering this live and moving it into the main section.
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 Tutorials

Who is online

Users browsing this forum: No registered users and 3 guests