Damien Katz is the creator of the CouchDB project.
Today I watched a great, inspirational video by him - CouchDB and Me. I recommend it to anyone who really loves programming. There are quite a few points in the talk you’ll be able to connect with.
If you can recommend any other inspirational talks about programming, I’m all ears!
And while we’re talking about Damien Katz - here’s a very good and once popular blog post he’s written - Formula Engine Rewrite. His whole experience of working with a complex, buggy and undocumented system strikes a cord with me and brings up lots of memories from my (ugh) IBM job.
I’ve just solved my 100th problem on Project Euler and got this nice message:
Excellent work, eliben! By solving your 100th problem you have earned a place among the top 2.53% of members and have advanced to level 3.
So I’m level 3 now!
P.S.: Problem 125 is very easy
Secondary title: “The invention of the transistor and the birth of the information age”
The invention of the semiconductor-based transistor in 1947 is certainly one of the most important technological breakthroughs of the 20th century, giving birth to modern computers and the communication revolution, among other effects.
In this book the authors provide a semi-biographic history of the transistor, focusing on the technologies behind it as well as on the persons responsible for its discovery - Bardeen, Brattain and Shockley. It’s written well and easy to read - even though the text gets somewhat technical at times. After all, it’s pretty hard to explain how transistors work without getting into technical details. I personally felt a little bit dissatisfied with the level of detail the authors went into - some things weren’t explained well enough and I had to look up topics in Wikipedia from time to time. And this having finished Electrical Engineering, with courses in semiconductors and analog circuits.
I’m not sure how interesting this book can be for people with absolutely no understanding in electronics. Perhaps the authors could have made it easier by providing a brief introductory explanation of P-N junctions (at least in the Appendix). All in all it’s still a good, enjoyable reading.
Problems 18, 67, 81, 82 and 83 in Project Euler are quite similar, but increase in level of difficulty.
For all of these except 83 I’ve used a specialized dynamic-programming solution that worked quite well. Being recursive it was a tiny bit slower than the iterative approaches others have used, but I believe recursive solutions are more elegant.
Anyway, project 83 proved too hard for my approach, because it introduces real cycles into the paths. So, this time I had to arm myself with a real path-finding algorithm. Luckily, I’ve coded a pretty generic implementation of the A* algorithm quite recently for my Creeps PyGame demo.
A*, however, requires a heuristic to do its magic, and for problem 83 there’s no real heuristic. However, since a constant heuristic is acceptable and effectively “dumbs down” A* to the original Dijkstra algorithm (the heuristic of A* must be non-decreasing, which a constant satisfies), I was able to make use of the code from the Creeps game to find a solution in 0.3 seconds, with only 30 lines of code.
Problem 66 is one of those problems that make Project Euler lots of fun. It doesn’t have a brute-force solution, and to solve it one actually has to implement a non-trivial mathematical algorithm and get exposed to several interesting techniques.
I will not post the solution or the full code for the problem here, just a couple of hints.
After a very short bout of Googling, you’ll discover that the Diophantine equation:
Is quite famous and is called Pell’s equation. From here, further web searches and Wikipedia-reading will bring you to at least two methods for finding the fundamental solution, which is the pair of x and y with minimal x solving it.
One of the methods involves computing the continued-fraction representation of the square root of D. This page is a must read on this topic, and will help you with other Euler problems as well.
I want to post here a code snippet that implements the continued-fraction computation described in that link. Its steps follow the Algebraic algoritm given there:
def CF_of_sqrt(n):
""" Compute the continued fraction representation of the
square root of N.
The first element in the returned array is the whole
part of the fraction. The others are the denominators
up to (and not including) the point where it starts
repeating.
Uses the algorithm explained here:
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/cfINTRO.html
In the section named: "Methods of finding continued
fractions for square roots"
"""
if is_square(n):
return [int(math.sqrt(n))]
ans = []
step1_num = 0
step1_denom = 1
while True:
nextn = int((math.floor(math.sqrt(n)) + step1_num) / step1_denom)
ans.append(int(nextn))
step2_num = step1_denom
step2_denom = step1_num - step1_denom * nextn
step3_denom = (n - step2_denom ** 2) / step2_num
step3_num = -step2_denom
if step3_denom == 1:
ans.append(ans[0] * 2)
break
step1_num, step1_denom = step3_num, step3_denom
return ans
As I said, this still isn’t enough to solve the problem, but with this code in hand, the solution isn’t too far. Read some more about Pell’s equation and you’ll discover how to use this code to reach a solution.
It took my program ~30 milliseconds to find an answer to the problem, by the way. It took less than a second to solve a 10-times larger problem (for D <= 10000), so I believe it to be a pretty good implementation.
In this encyclopedic work, Richard Rhodes ambitiously sets to document one of the largest scientific and engineering efforts of modern times - the creation of the atomic bomb by American scientists and engineers during World War II. The book has won numerous awards since it’s publishing in 1986, including the Pulitzer prize for general non-fiction in 1988.
Far from your usual lightweight pop-science reading, this book is huge and packed with details. 800 large pages delve into the history of the bomb in every imaginable aspect - scientific, human, political and what not. For example, this book contains one of the most detailed and well-written histories of modern physics (mainly focusing on nuclear and particle physics, naturally) I’ve ever read. The lives, characters, and works of most preeminent physics who’ve shaped this field are described in great detail. Many of the important experiments and papers which laid the theoretical foundations for nuclear fission are described, with the level of detail becoming lower only after the beginning of the Manhattan project, when most of the research was classified.
Sometimes the details are taken too far, however. For example, World War I is described in dozens of pages, although in the great total of the history of the bomb it probably doesn’t play that big a part. Also, since a large percentage of the scientists involved with the development of the bomb and the research that made it possible were Jews, Rhodes didn’t spare half a chapter on retelling the history of the Jewish people in Europe in the past few centuries. While personally I found this part very interesting, I’m not sure it added a lot of value to the average reader.
Another thing I liked is the interesting description of the huge industrial undertaking the project required. I’m a fan of “economies of scale” reading about how big engineering projects are done, so reading this was very illuminating.
To conclude, this is a very good book, but only if you’re sufficiently interested in the topic and have enough patience to read it. Its size is nothing short of monumental, and you can finish 4-5 average pop-science book in the time it will require to finish this one.
This post applies to Python 2.5 and 2.6 - if you see any difference for Python 3, please let me know.
Destructors are a very important concept in C++, where they’re an essential ingredient of RAII - virtually the only real safe way to write code that involves allocation and deallocation of resources in an exception-throwing program.
In Python, destructors are needed much less, because Python has a garbage collector that handles memory management. However, while memory is the most common resource allocated, it is not the only one. There are also sockets and database connections to be closed, files, buffers and caches flushed and a few more resources that need to be released when an object is done with them.
So Python has the destructor concept - the __del__ method. For some reason, many in the Python community believe that __del__ is evil and shouldn’t be used. However, a simple grep of the standard library shows dozens of uses of __del__ in classes we all use and love, so where’s the catch? In this article I’ll try to make it clear (first and foremost for myself), when __del__ should be used, and how.
First a basic example:
class FooType(object):
def __init__(self, id):
self.id = id
print self.id, 'born'
def __del__(self):
print self.id, 'died'
ft = FooType(1)
This prints:
1 born
1 died
Now, recall that due to the usage of a reference-counting garbage collector, Python won’t clean up an object when it does out of scope. It will clean it up when the last reference to it has gone out of scope. Here’s a demonstration:
class FooType(object):
def __init__(self, id):
self.id = id
print self.id, 'born'
def __del__(self):
print self.id, 'died'
def make_foo():
print 'Making...'
ft = FooType(1)
print 'Returning...'
return ft
print 'Calling...'
ft = make_foo()
print 'End...'
This prints:
Calling...
Making...
1 born
Returning...
End...
1 died
The destructor was called after the program ended, not when ft went out of scope inside make_foo.
Before I proceed, a proper disclosure: Python provides a better method for managing resources than destructors - contexts. I won’t turn this into a tutorial of contexts, but you should really get yourself familiar with the with statement and objects that can be used inside. For example, the best way to handle writing to a file is:
with open('out.txt', 'w') as of:
of.write('222')
This makes sure the file is properly closed when the block inside with exits, even if exceptions are thrown. Note that this demonstrates a standard context manager. Another is threading.lock, which returns a context manager very suitable to be used in a with statement. You should read PEP 343 for more details.
While recommended, with isn’t always applicable. For example, assume you have an object that encapsulates some sort of a database that has to be committed and closed when the object ends its existence. Now suppose the object should be a member variable of some large and complex class (say, a GUI dialog, or a MVC model class). The parent interacts with the DB object from time to time in different methods, so using with isn’t practical. What’s needed is a functioning destructor.
To solve the use case I presented in the last paragraph, you can employ the __del__ destructor. However, it’s important to know that this doesn’t always work well. The nemesis of a reference-counting garbage collector is circular references. Here’s an example:
class FooType(object):
def __init__(self, id, parent):
self.id = id
self.parent = parent
print 'Foo', self.id, 'born'
def __del__(self):
print 'Foo', self.id, 'died'
class BarType(object):
def __init__(self, id):
self.id = id
self.foo = FooType(id, self)
print 'Bar', self.id, 'born'
def __del__(self):
print 'Bar', self.id, 'died'
b = BarType(12)
Output:
Foo 12 born
Bar 12 born
Ouch… what has happened? Where are the destructors? Here’s what the Python documentation has to say on the matter:
Circular references which are garbage are detected when the option cycle detector is enabled (it’s on by default), but can only be cleaned up if there are no Python-level __del__() methods involved.
Python doesn’t know the order in which it’s safe to destroy objects that hold circular references to each other, so as a design decision, it just doesn’t call the destructors for such methods!
Shouldn’t we use destructors because of this deficiency? I’m very surprised to see that many Pythonistas think so, and recommend to use explicit close methods. But I disagree - explicit close methods are less safe, since they are easy to forget to call. Moreover, when exceptions can happen (and in Python they happen all the time), managing explicit closing becomes very difficult and burdensome.
I actually think that destructors can and should be used safely in Python. With a couple of precautions, it’s definitely possible.
First and foremost, note that justified cyclic references are a rare occurrence. I say justified on purpose - a lot of uses in which cyclic references arise are an example of bad design and leaky abstractions.
As a general rule of thumb, resources should be held by the lowest-level objects possible. Don’t hold a DB resource directly in your GUI dialog. Use an object to encapsulate the DB connection and close it safely in the destructor. The DB object has no reason whatsoever to hold references to other objects in your code. If it does - it violates several good-design practices.
Sometimes Dependency Injection can help prevent cyclic references in complex code, but even in those rare few cases when you find yourself needing a true cyclic reference, there’s a solution. Python provides the weakref module for this purpose. The documentation quickly reveals that this is exactly what we need here:
A weak reference to an object is not enough to keep the object alive: when the only remaining references to a referent are weak references, garbage collection is free to destroy the referent and reuse its memory for something else. A primary use for weak references is to implement caches or mappings holding large objects, where it’s desired that a large object not be kept alive solely because it appears in a cache or mapping.
Here’s the previous example rewritten with weakref:
import weakref
class FooType(object):
def __init__(self, id, parent):
self.id = id
self.parent = weakref.ref(parent)
print 'Foo', self.id, 'born'
def __del__(self):
print 'Foo', self.id, 'died'
class BarType(object):
def __init__(self, id):
self.id = id
self.foo = FooType(id, self)
print 'Bar', self.id, 'born'
def __del__(self):
print 'Bar', self.id, 'died'
b = BarType(12)
Now we get the result we want:
Foo 12 born
Bar 12 born
Bar 12 died
Foo 12 died
The tiny change in this example is that I use weakref.ref to assign the parent reference in the constructor FooType. This is a weak reference, so it doesn’t really create a cycle. Since the GC sees no cycle, it destroys both objects.
Python has perfectly usable object destruction via the __del__ method. It works fine for the vast majority of use-cases, but chokes on cyclic references. Cyclic references, however, are often a sign of bad design, and few of them are justified. For the teeny tiny amount of uses cases where justified cyclic references have to be used, the cycles can be easily broken with weak references, which Python provides in the weakref module.
Some links that were useful in the preparation of this article:
Note: there are surely many collections of shorter works by Tolstoy out there. This particular one was issued by the Russian publishing house “Ripol Classic” in 2003. I’ll try to emphasize the stories and not the collection - and the names are my own translations from Russian.
There are 20+ works in this collection, ranging from just 4 to almost 100 pages in length. Not all the stories are interesting, but here are a few I enjoyed:
As I’ve said in the list above, it’s very worth reading “The Death of Ivan Illych”. The other stories can be skipped unless you’re a hard-core fan of Tolstoy of or Russian history.
When it comes to plotting and drawing graphs, Python has quite a few options. In this post I want to focus on the two I’ve had experience with, so far. After a short presentation of the libraries, I will compare them on various criteria which I found important.
matplotlib is arguably the most popular and best known Python plotting package out there. Armed with NumPy, SciPy and matplotlib, Python programmers aim at the domain currently occupied by the uncontested heavyweight of numeric computing - Matlab. And quite frankly, Python doesn’t fare too badly in this contest.
So matplotlib has been designed from the ground up to support a huge range of plots, and be particularly suitable for scientific plotting. It provides publication-quality plotting, generating high-resolution anti-aliased images that can (and have been) incorporated in real reports and scientific articles.
PyQwt is a different beast. It provides Python bindings to the C++ Qwt library, which is a set of classes extending the Qt framework with plotting and other widgets for scientific and engineering applications.
While not aimed at scientific publication, PyQwt is relatively light-weight, integrates very well with PyQt and provides additional widgets that can be useful for some applications that require plotting.
Without question, matplotlib produces prettier plots. It uses the Agg 2D rendering engine as its backend and produces the best looking plots I’ve seen from any tool or library.
PyQwt’s plots are homelier, but still look pretty good. There’s an option to render the plots in an anti-aliased manner as well (using the RenderAntialiased option), which makes the plots look much better (at the price of performance), though still not quite like matplotlib.
matplotlib has built-in support for much more plot types than PyQwt. Although when you have a good framework (and PyQwt is one) it’s not difficult to program any type of plot, matplotlib delivers most types you could (and couldn’t) think of out-of-the-box.
Also, if math is your thing, you’ll be happy to discover that matplotlib can render LaTeX-typed equations onto the plots.
Since plotting is an inherently visual activity, integration with a GUI is important for a plotting library.
matplotlib knows how to play with Tk, wxPython and PyQt quite well. But it’s a separate library, with its own types, conventions and needs.
PyQwt is seamlessly integrated into the PyQt model. The pens you use to plot in it are PyQt pens, the events and slots of the plot are the same events and slots of the GUI, and everything fits together just perfectly. This is very useful if integration with PyQt is what your application needs the most.
For some plots, interaction is important: you want to allow the user to navigate the plot - zoom in and out of areas, have a cursor with a known location, and so on. matplotlib provides built-in interaction with its toolbar that can be easily attached to a plot. Just a few lines of code, and you have a pretty good means of interaction.
PyQwt is different in this aspect. Though it doesn’t have a built-in toolbar widget, here its great integration with PyQt shows its strength. Since PyQwt is so tightly tied into the Qt GUI and event system, it’s possible to create very complex interactions with it. While matplotlib also has an event capability that can be tied to the host GUI’s, it’s much less natural and less convenient to work with.
So if you need just the basic integration, matplotlib has it built-in, and in PyQwt you will have to spend a bit more effort. But if you need a complex interaction, PyQwt is better.
matplotlib is much better documented than PyQwt. For PyQwt you just have the examples and the class reference of Qwt (the C++ library) to look at. For matplotlib you have a whole handbook almost 500 pages long, and several other helpful documents.
But this is mostly because matplotlib is much more complex. As I’ve mentioned before, PyQwt is so integrated with PyQt that you don’t need that much documentation to use it. It’s basically another PyQt widget you can use in your application - the learning curve is much gentler.
Here, in my experience, PyQwt wins big. matplotlib is a large and heavy library, and adding it to an application considerably increases its load time. PyQwt is much lighter and faster as well. If distributing applications is important, keep in mind that the executables produced (say, with py2exe or PyInstaller) with PyQwt will be much smaller, and will load more quickly.
If you build PyQwt on your own, you can also keep numpy support out, which will make the library even smaller. Unfortunately, the pre-built binaries for Windows come with numpy support obligatory.
matplotlib is a library for plotting, period. It contains a huge variety of different plot types that will satisfy ultimately all of your plotting needs.
PyQwt, on the other hand, aims at other goals as well. It contains other widgets useful for scientific and engineering apps, such as dials, knobs, wheels and sliders. These can be very useful for some applications, especially in the domain of test&measurement software (as a competition to LabView or Matlab).
I think that there’s place for both libraries in the toolkit of a Python programmer, especially if PyQt is his GUI of choice.
If you need to incorporate a plot into a complex GUI, and provide interesting interaction between the plot and the rest of the widgets (especially dynamic updating), PyQwt is very suitable for the task. It’s lightweight (which helps speed up large applications), very well integrated with PyQt and has a set of additional widgets you can find useful.
On the other hand, whenever you need to crunch some numbers with Python, matplotlib is indispensable. Armed with a good interactive terminal (such as Pydee or IPython) and matplotlib, mathematical explorations are as easy as with Matlab, and the produced plots can be saved to images and incorporated into reports and documents.
Also, if you don’t use PyQt but prefer wx or Tk instead, then matplotlib is perhaps your best option for GUI-integrated plots as well.
I must be looking in all the wrong places, but I haven’t found many usable examples online of storing BLOBs in a SQLite database using Python. At least, not something that works with current versions of Python (2.5), pysqlite (2.3.2) and SQLite (the version that comes installed with Python 2.5). Overall, there doesn’t seem to be much good examples of pysqlite anywhere.
So here’s an example I cooked up after consulting with several sources and experimenting a little:
import sqlite3 as sqlite
# Create a new in-memory DB and a cursor
#
con = sqlite.connect(':memory:')
cur = con.cursor()
# The table is named 'frames'
# The columns are: a running ID, and a data blob
#
cur.execute('''
create table frames (
id integer primary key,
data blob)''')
# Shove some data into the table. The data stored
# using the sqlite.Binary type, which means a BLOB.
#
cur.execute('''
insert into frames values (null, ?)''',
(sqlite.Binary('\0' * 10 + '\x12'),))
cur.execute('''
insert into frames values (null, ?)''',
(sqlite.Binary('\x01\x42\x55'),))
# Now read it back. When BLOBs are read, they're
# converted to Python buffers of type 'buffer'
#
for row in cur.execute("select * from frames"):
print row[0], str(row[1]).encode('hex')
cur.close()
con.close()