A Refresher on "Big O" Notation (Python)

It's well known that asymptotic notation is used to convey the speed and efficiency of code blocks in computer programs. I haven't used them very much while working with Python, so I needed to refresh my memory before trying to use this great tool.


Cardinal Rule: Focus primarily the largest value in the equation of time complexity. All other factors in the time complexity equation are essentially trumped.


O(n^4+n^2+n^3+nm+100) ~= O(n^4)
Update: assuming m is linear.


Trump Rules for Time Complexity:

• Notes
• Remember that we care most about the upper bound and are not so concerned with the lower (in general)
• The smaller the upper bound number the better (and consequently, faster)
• The Ladder
• Constants are less than logarithms
• Logarithms are less than polynomials
• Polynomials are less than exponentials
• Exponentials are less than factorials

Notation and Hierarchy (Smaller Is Better):

Constant Θ(1)

Logarithmic Θ(lg n) 

Linear Θ(n) 

Loglinear Θ(n lg n) 

QuadraticΘ(n^2) 

Cubic Θ(n^3) 

Polynomial O(n^k) 

Exponential O(k^n) 

Factorial Θ(n!)

Quick Examples:

[i for i in list] {linear}

Functions that generally operate on lists or generators (sum, map, filter, reduce, min, max, etc) tend to be linear in time complexity

[i+k for i in list for k in list] {quadratic}

[i+k for i in list1 for k in list2] O(list1*list2) {quadratic I think, since it's linear*linear}

Add 1 to the exponent value for each nested loop. For example. [j+i+k+n for j in list1 for i in list1 for k in list1 for n in list1] would have a time complexity of O(n^4)

Note: Some programmers reduce quadratic time complexity a bit when using nested loops with sorted lists by ensuring that calculations aren't performed more than once. Consequently, that code block runs faster and faster and less and less has to be evaluated through each iteration of the loop. For example:

list1 = [i for i in range(10)]

size = len(list1)

number=100

for n in range(size-1):

    for k in range(n+1, size):

        print number*(n+k)

How to Improve Coding Style (In Python)

I'm finally cracking open the Python Style Guide. I've been programming python for years now so I thought I'd join the club.


In addition to all of the nifty tools available to speed up and optimize python code, there are a few utilities out there to help with coding style. PyLint is a program which analyzes source code and reports lines which do not follow the PEP 8 coding convention. There is another program called CloneDigger which looks through source code and points out duplicate code.


Summary of Guidelines to Improve Python Coding Style:

• Variables
• Global variables should be ALL_CAPS_WITH_UNDERSCORES
• Non-public variables within classes should be prefixed with an underscore and lowercase (_private_list = [])
• Public variables should be lowercase
• Boolean variables should be have "is" or "has" (is_full = True)
• Avoid generic names
• Classes
• Should be named using the CamelCase convention
• If a class will be a base class, prefix the classname with "Base"
• Functions
• Names of functions and methods should be lowercase and underscore separated (do_something_with_this)
• Watch out for custom functions which share names with built-in functions
• If this does happen and one can't find a better name, then add a trailing underscore to the custom function
• Arguments names and contents should be decided through an iterative design process
• Also, do not use spaces around the "=" sign used to assign the default parameter for keyword arguments
• Be careful with *args and **kw. These can cause problems if abused.
• Don't implement "type" checking using the assert command
• Conditionals
• When check to see if an object is true, use "if object:" rather than "if object == True" or "if object is True"
• When checking to see if an object is of a certain "type" (integer, string, etc), do not use "if type(obj) == type(int):", use "if isinstance(obj, int):"
• What's "False" in Python?:
• None
• False
• Zero (of any numeric type)
• Any empty sequence or mapping ({},'', [], ())
• instances of user-defined classes, if the class defines a __nonzero__() or __len__() method, when that method returns the integer zero or bool value False
• Modules and Packages
• Usually has a lib suffix (mathlib)
• Be careful to ensure that any process requiring the use of several functions strung together are consolidated into an independent "pipeline" function
• General Coding
• Clarity over cleverness
• Try to keep code as short as possible--short enough to fit on the screen without having to scroll rampantly
• When a class start to have about 10 or more methods, it is time to re-evaluate the contents of the class and possibly split that larger class into a number of smaller classes
• Use lambda functions for functions that will only be run once or twice. Otherwise, create a defined function
• Use spaces around arithmetic operators
• Import statements should always be on separate lines
• Avoid extraneous whitespace immediately inside parentheses, brackets, or braces. Also before colons

Playing with Ruby on Rails

Here below are some notes I made while playing with Ruby and RoR. Interestingly, I found that RoR is a great way to learn about the foundations of web frameworks. I have a much stronger understanding about not just RoR, but of Django, Pyramid, and Web2Py. Every web framework really has the same few components (or some variation thereof): Models, Views, Controllers, and Routes.

I walked through the free tutorial by CodeSchool:

The Basics:

CRUD
Create,Read,Update,Destroy

Zombie.new
z = Zombie.new(initialize)
z.save
Zombie.create
Zombie.find(3)
Zombie.update_attributes

Models:

class Tweet < ActiveRecord::Base (just means that class Tweet inherits from ActiveRecord)
end

validate data before it is saved in DB

class Tweet < ActiveRecord::Base
    validates_presence_of :status
end

t.errors -> returns errors
t.errors[:status] --> just error pertaining to status

Rails 3 new syntax for validation:

validates attribute, validation
validates :status, :presence => true
validates :status, :length => {:minimum => 3}

app/models/tweet.rb

class Tweet < ActiveRecord::Base
    belongs_to :zombie
end

app/models/zombie.rb

class Zombie < ActiveRecord::Base

    has_many :tweets

end

View:

web request -> 4 layers -> models, view, controllers, routing

<%...%> evaluate ruby

<%=...%> evaluate and print results

layouts/application --> make html page format and use <%= yield %>

/app/views/tweets/shot.html.erb (code that will be yielded is in here)

Adding CSS

<%= stylesheet_link_tag :all %>

<%= javascript_include_tag :defaults %> # can replace prototype javascript library with jquery

<%= csrf_meta_tag %> #protects website from hackers

with URLs, it checks public folder first, then tries to execute inside rails

Adding a Link

<%= link_to "link text",  "link path (URL)"%>

<%= link_to tweet.zombie.name, zombie_path(zombie.tweet) %>

<%= link_to "Edit", edit_tweet_path(tweet) %>

<%= link_to "Delete", :method => :delete %>

Listing Zombies

Listing Tweets

<% Tweet.all.each do |tweet| %>

<% end %>

Status	Zombie
<% tweet.status %>	<% tweet.zombie.name %>

Controllers:

class TweetsController < ApplicationController

   def show

      @tweet = Tweet.find(params[:id]) #using an instance variable

       render :action => 'status' #for status.html.erb

       respond_to do |format|

          format.html #show html.erb

          format.xml  { render :xml => @tweet }

          format.json { render :json => @tweet }

   end

end

model calls goes into the controller files. All request data stored in a hash called params.

def index -> list all tweets

def show -> show a single tweet

def new -> show a new tweet form

def edit -> show an edit tweet form

def create -> create a new tweet

def update -> update a tweet

def delete -> delete a tweet

Authorization:

def edit

  @tweet = Tweet.find(params[:id])

   if session[:zombie_id] != @tweet.zombie_id

      flash[:notice] = "sorry, you can't edit this tweet"

      redirect_to(tweets_path)

    end

  end

 end

class TweetsController < ApplicationController

  before_filter :get_tweet, :only => [:edit, :update, :destroy]

  before_filter :check_auth, :only => [:edit, :update, :destroy]

  def get_tweet

    @tweet = Tweet.find(params[:id])

  end

def check_auth

  if session[:zombie_id] != @tweet.zombie_id

      flash[:notice] = "sorry, you can't edit this tweet"

      redirect_to(tweets_path)

  end

 end

Routing:

config/routes.rb

ZombieTwitter::Application.routes.draw do |map|

  resources :tweets #creates a "REST"ful resource

  match 'new_tweet' => "Tweets#new" # path => controller#action

  match 'all' => "Tweets#index", :as => "all_tweets" # now all tweets can be used as an object "link_to"

  match 'a' => redirect('/tweets')

  match 'google' => redirect('http://www.google.com')

  root :to => "Tweets#index"

  match 'local_tweets/:zipcode' => "Tweets#index"

  match 'local_tweets/:zipcode' => 'Tweets#index', :as => 'local_tweets'

end

<%= link_to "All Tweets", all_tweets_path %>

<%= link_to "Tweets in 32828", local_tweets_path(32828) %>