Category Archives: python

Special method attributes in Python

Special method attributes in python provides much of the same functionality when using ‘operator overloading’ to apply built-in operators to user defined classes.

This can be understood by the following example using classes and objects in python.

>>>class test:

. . .      def __init__(self, n):

. . .          self.n = n

. . .      def test1(self, n):

. . .          self.n = n

. . .

>>> a = test(1)

>>> print a.n

1

>>> test.test1(a,2)

>>> print a.n

2

>>>

The method ‘__init__’ is a ‘special method’ which is automatically called when an object is being created. Now, when we call test.test1(a,2), we are actually calling a method belonging to class foo with the object ‘a’ as the first parameter. This parameter is usually called ‘self’.

The following are some of the python special methods (attribute access):

object.__getattr__(self,name):- Called when an attribute lookup has not found the attribute in the usual places (i.e. it is not an instance attribute nor is it found in the class tree for self). object.__setattr__(self,name,value):- Called when an attribute assignment is attempted. This is called instead of the normal mechanism (i.e. store the value in the instance dictionary).

If __setattr__() wants to assign to an instance attribute, it should not simply execute self.name = value — this would cause a recursive call to itself. Instead, for new style classes, it should call the base class method with the same name, for example, object.__setattr__(self, name, value). For classic classes, it should insert the value in the dictionary of instance attributes, e.g., self.__dict__[name] = value.
object.__delattr__(self,name):- Like __setattr__() but for attribute deletion instead of assignment. This should only be implemented if del obj.name is meaningful for the object. object.__getattribute__(self,name):- This method is for new style classes only. Called unconditionally to implement attribute accesses for instances of the class.

In order to avoid infinite recursion in this method, its implementation should always call the base class method with the same name to access any attributes it needs, for example, object.__getattribute__(self, name).

Functional programming in Python

Python supports functional programming paradigm which treats computation as mathematical evaluation of functions. Functions are first-class objects in Python. That is they have attributes and can be referenced and assigned to variables. Python also supports higher-order functions, that can accept other functions as arguments and return functions to the caller.

The functional programming paradigm encourages us to structure our programs as collections of pure functions. The basic element of Functional programming in python are the functions map(),reduce(),and filter() , and the operator lambda.

Lambda

Python supports the creation of anonymous functions (i.e. functions that are not bound to a name) at runtime, using a construct called “lambda”.The lambda definition does not include a “return” statement — it always contains an expression which is returned. Also we can put a lambda definition anywhere a function is expected, and we don’t have to assign it to a variable at all.

Syntax:  lambda argument_list:expression

The following shows an example of lambda function:

>>> def increment(n):
. . .       return lambda x: x + n
. . .
>>> a = increment(2)
>>> b = increment(5)
>>>
>>> print a(10), b(4)
12  9
>>>
>>> print increment(11)(12)
23
>>>

filter()

Syntax: filter(function, sequence)
filter() return those items of sequence for which function(item) is true. If function is None, return the items that are true. If sequence is a tuple
or string, return the same type, else return a list.

The following shows an example of filter():

>>> def even(num):
. . .       return num % 2 == 0
. . .
>>> n = [1,2,4,7,3,9,8,6]
>>> filter(even, n)
[2, 4, 8, 6]
>>>

map()
map() return a list of the results of applying the function to the items of the argument sequences. If more than one sequence is given, the function is called with an argument list consisting of the corresponding item of each sequence, substituting None for missing values when not all sequences have the same length. If the function is None, return a list of the items of the sequence (or a list of tuples if more than one sequence).

>>> def test(x):
. . .       return (x*x)+x+10
. . .
>>> map(test, [1,2,3,4,5])
[12, 16, 22, 30, 40]
>>>

reduce()

reduce() function reduces a list to a single value by combining elements via a supplied function. It returns only a single value. The following function describes working of reduce() function.First it take the first two elements in the list and applied it to the function, in the next step the result of the previous step and the next element is applied to the function, this process will continue at the end of the list, finally a single value returned.

>>> l = [1,2,3,4,5]
>>> def mul(a,b):
. . .       return a*b
. . .
>>> reduce(mul, l)
120
>>>

Python Generators

Generators are one of important features of python. A generator is a function that when called executes up to a ‘yield’ command. When we call a generator function, it returns a generator object. This object stores information about the original function and the values of the variables in the function and the location of the code to run next. So next time the function is called, it resume from the point it had stopped and continue execution.

Here is an example:

>>> def test():

print ‘Hai’

yield 1

print ‘Hello’

yield 2

To execute the function, we have to use the ‘next()’ method.

>>> call = test()

>>> call.next()

Hai

1

>>> call.next()

Hello

2

>>> call.next()

Traceback (most recent call last):

File “<stdin>” line 1, in ?

StopIteration

We can use for loop in the generator, which works by calling a.next() and assigning the obtained value to i.

>>> call = test()

>>> for i in place:

print i

Hai

1

Hello

2

Here is a program for printing factorials as an example for generators:

 # A simple factorial program using python generators with iterations

>>>  def factorial(n):

 count = 1

 fact = 1

 while count <= n:

 yield fact

 count = count + 1

 fact = fact * count

 >>> print “Factorial program using generators.”

 >>> for i in factorial(5):

 print i


Output:

Factorial program using generators.

1

2

6

24

120

List comprehensions

List comprehensions provide a concise way to create lists from existing lists. Each list comprehension consists of an expression followed by a for clause, then zero or more for or if clauses. The result will be a list resulting from evaluating the expression in the context of the for and if clauses which follow it.

The following are common ways to describe lists (or sets, or tuples, or vectors) in mathematics.

Lists can contain any type of elements, including strings, nested lists and functions. We can even mix different types within a list.
The following works on a list of strings and produces a list of lists.

The following is also an example of nested list comprehension:

Unit testing in Python

According to wikipedia: In computer programming, unit testing is a method by which individual units of source code are tested to determine if they are fit for use. A unit is the smallest testable part of an application. In procedural programming a unit could be an entire module but is more commonly an individual function or procedure. In object-oriented programming a unit is often an entire interface, such as a class, but could be an individual method.

This post is about testing in Python, mainly using the Python standard library testing framework unittest. For an example to test, first import the Unit Test module by:

import unittest

unittestis an object oriented framework based around test fixtures. In unittest the test fixture is the TestCase class. To write a testcase class, we have to write a class that derives from the TestCase class of the unittest module. On the class statement, the base class (or classes) goes in parentheses after the name of the class. The usual four-phase unit test includes Setup, Exercise, Verify and Teardown.

The snapshot of my sample unit testing program is shown below:

In the above program add is a simple adding function to demo unittest. MyTest is the class in which all functions will be ran by unittest. The function setUp will always be ran in order to setup the test environment before all the tests have run. The function tearDown will always be ran in order to cleanup the test environment after all the tests have run. After that, the function beginning with ‘add’ will be ran as a unit test. AssertEqual checks the values given in the parentheses are equal. The TestCase class provides a number of methods to check for and report failures, such as:

assertEqual (a,b) → a == b

assertNotEqual (a,b) → a != b

assertTrue (x) → bool(x) is True

assertFalse(x) → bool(x) is False

assertIs (a,b) → a is b

assertIsNot(a,b) → a is not b

assertIn (a,b) → a in b

assertNotIn (a,b) → a not in b

When we run the above program, we get an output like this:

If there is error in the output or if it is not compiled properly, it will be printed in the terminal. Here , the code is correct. So, we get the output as ‘OK’.

Multi client chat server in Twisted Python

In a multi client chat server, N clients are connected to a server and send messages. In this program, one of the clients send messages to the server and it will send back the messages to all other clients. I implemented it in Twisted Python also.

Twisted is an event-driven networking engine written in Python and licensed under the open source. Twisted makes it easy to implement custom network applications, both servers and clients.It gives developers a complete set of tools for communicating across networks and the Internet. Twisted includes both high- and low-level tools.

This program also uses TCP.

Client:

The twisted event loop is started by starting the reactor. Starting the reactor is easy. Import the reactor object from the twisted.internet module. Then call reactor.run( ) to start the reactor’s event loop. Call the reactor.connectTCP( ) method to start a TCP connection, passing a StdioProxyFactory object as the third parameter. The StdioProxyFactory object waits for the connection to be established, and then creates a Protocol object that manages the flow of data back and forth along that connection. Use a subclass of Protocol to send and receive data. Override the dataReceived method to control what happens when data is received from the connection. Use self.transport.write to send data.

Keyboard input is given by importing stdio from twisted.internet.

This program includes a class called DataForwardingProtocol, which takes any data received and writes it to self.output. This usage makes it possible to create a simple application, similar to the classic utility netcat, that passes any data received on standard input to a server, while printing any data received from the server to standard output.

Server:

Twisted server accepts connections from clients and interacts with them by creating a Protocol object defining our server’s behavior. Create a MultiClientEchoFactory object using the Protocol, and pass it to reactor.listenTCP. The list self.clients defined in the factory stores clients connections. Whenever a data is received from one of the clients, the server send back this data to all clients in the clients list.

The complete code of this program is available in https://bitbucket.org/vidyakv/twisted-python/changeset/7db7480a1dc8

URL Shortener in Python with Google App Engine

According to wikipedia: URL shortening is a technique on the World Wide Web in which a Uniform Resource Locator (URL) may be made substantially shorter in length and still direct to the required page. This is achieved by using an HTTP Redirect on a domain name that is short, which links to the web page that has a long URL. This is especially convenient for messaging technologies such as Twitter and Identi.ca, which severely limit the number of characters that may be used in a message. Normally, a URL shortening service will use the top-level domain of a country that allows foreign sites to use its extension, such as .ly or .to (Libya and Tonga), to redirect worldwide using a short alphanumeric sequence after the provider’s site address in order to point to the long URL. Another use of URL shortening is to disguise the underlying address.

I implemented it in python with Google App Engine. Google App Engine (often referred to as GAE or simply App Engine, and also used by the acronym GAE/J) is a platform as a service (PaaS) cloud computing platform for developing and hosting web applications in Google-managed data centers. It virtualizes applications across multiple servers.

For deploying this project with google appengine, I developed and uploaded Python applications for Google App Engine using the App Engine Python software development kit (SDK).

The Python SDK includes a web server application that simulates the App Engine environment, including a local version of the datastore, Google Accounts, and the ability to fetch URLs and send email directly from our computer using the App Engine APIs.

Python App Engine applications communicate with the web server using the CGI standard. When the server receives a request for our application, it runs the application with the request data in environment variables and on the standard input stream (for POST data). To respond, the application writes the response to the standard output stream, including HTTP headers and content.

App Engine includes a simple web application framework of its own, called webapp. The webapp framework is already installed in the App Engine environment and in the SDK, so you do not need to bundle it with your application code to use it.

A webapp application has three parts:

  • one or more RequestHandler classes that process requests and build responses
  • a WSGIApplication instance that routes incoming requests to handlers based on the URL
  • a main routine that runs the WSGIApplication using a CGI adaptor.

The default datastore for an application is now the High Replication datastore.In my program, this High replication datastore stores the short URL of the corresponding original URL and when we give the same original URL, it gives the same short URL which is same as before.

Unlike a traditional web hosting environment, Google App Engine does not serve files directly out of our application’s source directory unless configured to do so. For that, we use static files. In my url shortener , I used stylesheets, images etc.

For testing the application: If we are not using Google App Engine Launcher, start the web server with the following command, giving it the path to the root directory. Here ‘url’ is my root directory.:

google_appengine/dev_appserver.py url/

The web server is now running, listening for requests on port 8080. You can test the application by visiting the following URL in your web browser:

I registerd this application in Google App Engine using my gmail account.

We can create and manage App Engine web applications from the App Engine Administration Console, at the following URL:

https://appengine.google.com/ and uploaded it by running the following command:

google_appengine appcfg.py update url/

For my url shortener application, the URL for my website is https://urlshortener-vidya.appspot.com/

My urlshortener website snapshot is given below:

 

The complete code of this program is available in my bitbucket account. Here is the link: https://bitbucket.org/vidyakv/url-shortener 

Flood fill

According to wikipedia: Flood fill also called Seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the “bucket” fill tool of paint programs to determine which parts of a bitmap to fill with color, and in games such as Go and Minesweeper for determining which pieces are cleared. When applied on an image to fill a particular bounded area with color, it is also known as boundary fill.

I implemented it in python using pygame. The algorithm used is the depth-first algorithm(recursive). In my flood fill program, for every pixel filled, the functions analyze neighbor pixels: 4 neighbors (except diagonal neighbors); this kind of connectivity is called 4-connectivity. The code of this section is shown below:

 

 The complete code is available in  https://bitbucket.org/vidyakv/flood-fill-using-pygame/changeset/bf1a8df717ea . The following images are the snapshots taken during flood filling.
                                

Implementing Trie datastructure in C

In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key it is associated with. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

The term trie comes from retrieval.Trie data structure is a tree with each node consisting of one letter as data and pointer to the next node. It uses Finite Deterministic automation. That means, it uses state to state transition.

This is a trie for keys “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, and “inn”. When we need to do auto complete for the starting characters, “te”, we need to get output tea, ted and ten. Instead of checking regular expression match for all the words in the database, it will make use of transitions. First character is t. Then in the root element, it will make transition for ‘t’ so that it will reach the node with data ‘t’, then at node ‘t’, it will make transition for next node ‘e’. At that point, we need to follow all paths from node ‘e’ to leaf nodes so that we can get the paths t->e->a, t->e->d and t->e->n. This is the basic algorithm behind implementing an efficient auto complete.

I implemented it using dfs(Depth First Search). DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn’t finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.

The complete code of this program is available in https://bitbucket.org/vidyakv/trie-datastructure/changeset/8c9e1cc33592

Graph colouring using PyGame

In graphtheory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring.  

In my program, I implemented the graph coloring in Python. The colouring code is given below:

The PyGame library is used here to visualize the graph colouring in Python. Pygame is a cross-platform set of Python modules designed for writing video games. It includes computer graphics and sound libraries designed to be used with the Python programming language.

The complete code of this program is available in my bitbucket account. Here is the link: https://bitbucket.org/vidyakv/graph-colouring-using-pygame/changeset/0698b8122965#chg-graph3.py

The WordPress.com Blog

The latest news on WordPress.com and the WordPress community.