Tag Archives: Python

TimSort Source Code in Java

This was an pretty interesting read, TimSort.java
TimSort is a stable form of merge-sort algorithm invented by Tim Peters.  Tim orginal wrote the sorting algorithm for the python language and was ported into the Java language by Josh Bloch.

Uses of Else in Python

I found this blog post post by Amir Rachum posted on /r/programming. I didn’t know you could use “else” after for or while loop statements or even after a catch statement.

Python lambda sample usage

This will be a very brief post on the sample usage of python’s lambda function.  The following code is an identity function that will return the argument passed in. Nothing too special but it will help demonstrate the syntax. In this case I’m defining the symbol id to the lambda function.

id = lambda x: x

The following snippet contains some sample use cases of the id symbol.

print(id(2)) # prints integer 2
print(id("Hello World")) # prints string "Hello World"

Here is a code snippet that is a bit more useful. The following code is a bit hack that finds the least significant bit(LSB) in a number, meaning the lowest bit that is used to generate the given number.

lsb = lambda x: x & (-x)

As an example, passing in 8 (1000) will return 8 as the LSB. When a more complex number like 6 (0110) is passed in the LSB will be 2.

print( lsb(8) ) # prints 8
print( lsb(6) ) # prints 2

You can also nest lambda’s together in Python. The next code snippet finds the sum of two numbers.

sum = lambda x: lambda y: x+y

So, how do you define the value of y when lambda expressions only take in a single argument? Well when you define the values of x and y in the expression, you use two sets of parenthesis. Each parenthesis will pass in the argument into the targeted lambda function.

print(sum(2)(2)) # prints 4
print(sum(2)(4)) # prints 6
print(sum(2)("Hello World")) # raises type error

My last code snippet defines a symbol min as a lambda expression. Min is contains a nested lambda expression that uses a bit hack to compare two integer values.

min = lambda x: lambda y: y ^((x^y) & -(x<y))

Here is a sample use case min.

print(min(2)(4)) # prints 2
print(min(4)(2)) # prints 2

Additional Resources:
http://en.wikipedia.org/wiki/Lambda_calculus

Lecture 2A – Higher Order Procedures: Structure and Interpretation of Computer Programs
[youtube:http://www.youtube.com/watch?feature=player_embedded&v=erHp3r6PbJk%5D

Python and HDF5 – Fast Storage for Large Data (Pycon 2012)

Not sure how I missed this one but it’s a great talk by Mike Müller

[youtube:http://www.youtube.com/watch?feature=player_detailpage&v=hnhN2_TpY8g%5D

Python Module Spotlight: HDF5

I wanted to try coding a python program that used a Strassen algorithm to multiply two extremely large matrices.   I my first hunch was to use numpy and after a bit of googling I found my way to this SO question.

http://stackoverflow.com/questions/3218645/handling-large-dense-matrices-in-python

People who answer their own questions are nice, but anyway this HDF5 library looks promising. I’m going to spend some time today an maybe next weekend attempting to code this.

http://alfven.org/wp/hdf5-for-python/

Turning Machine Links

These were great articles written by Peteris Krumins.  I would have never thought that sed would be a turning complete language but it kinda makes sense now.  Also check out his post on the busy beaver problem.  His scripts are pretty fun to run.

A proof that Unix utility “sed” is Turing complete

http://www.catonmat.net/blog/proof-that-sed-is-turing-complete/

The Busy Beaver Problem

http://www.catonmat.net/blog/busy-beaver/

Testing Floating Point Numbers Accuracy

This should be a no brainier for anyone who has been coding for awhile but computer math can be funky at times.  To demonstrate how accuracte a floating point number is I opened up my python interperter and ran this mathimatical gem.

>>> float(1/998001)
1.002003004005006e-06

As you can see python gives up pretty quickly calculating this number. Dividing 1 by 998001 will create a decimal sequence of every three digit number in order.

Now lets take a look a python’s decimal data type.

from decimal import Decimal
>>> Decimal(1/998001)
Decimal('0.000001002003004005005955287066314596255978131011943332850933074951171875')

Ok, the decimal length is bigger but it sequence turns to garbage at around the same point where the floating point number gave up. There are a few ways to improve your programming math but the given answer will still be bound by the constants of being computed by a computer.