An end to the experiments (for now)

Well, it's been 3 months, and I've gotten a decent number of things written. It took much longer than I was expecting, but I learned a lot of things, and made some good contacts. But most excitingly, I got a job! Last week I accepted a position working for Arc90, most prominently of Readability fame, but they've got plenty of other things going on.

I first heard about them when Kenneth Reitz started working there, and blogged about it. As it turns out, they were looking for someone with test automation experience just about the time I started getting serious about sending my resume around.

I'll be working with the Insight project team, building test automation and reporting tools to ensure confidence in the quality of every release. It's a very different scale from my work at RIM, and I think a very good opportunity for me to succeed or fail entirely on my own merits (I'm going to succeed, btw).

Which brings us to this blog. For the next few months, I don't expect to have much time to commit to writing here. Kenneth has certainly done an admirable job of keeping up blogging (and working on Requests!), so perhaps I will be able to as well. I've done a bit of research on some of the other topics I wanted to write about, and there's a post I think I owe someone for the help they have given me, but Arc90 is going to be my focus.

So this is an end, to this blog as it was. But one of the reasons I chose Arc90 as an employer is their support for blogging and open source work, so I do expect to be back writing before too long. Thanks to everyone who has read and commented on any of this!

Sorting out

As someone who almost exclusively uses high-level languages, the idea of writing my own sorting algorithm seems a bit silly. However, I can certainly appreciate the algorithms used for sorting, and it's a neat opportunity to try to document and implement these algorithms using methods I am familiar with.

Preface

These implementations are likely to be extremely naive. If you went CS school, you probably learned better implementations in your first year. There is absolutely no reason to use these in production code anywhere. The built-in python sorting is 10-50 times faster than anything I've produced (I'm actually surprised it's not more). If you've got tips about how to speed these up just by changing the code around, feel free to comment, or you can try forking my repository and sending a pull? request. I can't promise to spend much time on it, because this is pretty well-trod territory, but it would be a bit entertaining to see how close we can get.

Quick Sort

My understanding of quicksort is still developing, but based on what I've read on Wikipedia, it can work something like this:

1. Grab an item in the list, called the "pivot".
2. Create two lists, representing everything greater than the pivot, and everything less then the pivot.
3. Repeat steps 1 and 2 on the two sub-lists, returning the a list comprised of the smaller list items, then the pivot, then the larger list items.

In this way, the entire list should get sorted. It's my understanding there are various optimizations that can be done, such as swapping elements instead of creating new lists. It seems to be one of the "best" all around algorithms, though for certain cases, it's performance can be beaten by others.

Gist-it for quick_sort.py

This was the second fastest list implementation I created, at about 1/12th the performance of the built-in sorting.

Merge Sort
Merge sort relies on splitting the list recursively until you have an ordered hierarchy of l item item lists. Then you compare each list with it's neighbour, and return a combined list of the two merged together. Now you have 2-item sorted lists, which you work through, comparing the left-most element to its neighbour's left-most element, and moving the lowest one to a new list, eventually creating a 4-item list.

Gist-it for merge_sort.py

Heap Sort

Heap sort relies on understanding what a "heap" is, in this context. So let's do that.

A heap is a data structure that is tree based, and follows the rule that all children of a node will have a value that is lower than or equal to the value of that node (for a max-heap, for a min-heap the rule is reversed). In practice, heaps are usually implemented within arrays, with the first or last item of the array being the root of the tree.

Now, why do we do have a heap? What's the advantage? Apparently sorting things. :)

In a heap sort, we first build the heap from the list we've been given. Once we have our heap, we know the item with the highest value is at the root of the heap, which is position 0 in the list representing the heap. So now we swap the first and last elements in that list, and either move the last element from the list, or simply treat that part of the heap as already sorted (which means our heap needs to know to ignore it somehow). Then we take the first item, and trickle it down through the heap until the heap is proper again. This consists of comparing it's value with it's children, and swapping it with the higher one of these, until one of these is not higher.

Gist-it for heap_sort.py

Python apparently does have a built-in heap library, which might be worth benchmarking, as heap was my slowest sort implementation.

Bubble Sort

Bubble sort is fairly trivial.

Iterate through the items, except the last one, if an item is greater than the next one, swap their positions. When you reach the end of the list, do it again, unless there were zero swaps.

Gist-it for bubble_sort.py

Insertion Sort

Insertion sort is another trivial sort. I'm really only including it because I think my (unwitting) choice of an insertion sort in an interview may have cost me a job.

Gist-it for insertion_sort.py

Interestingly enough, for my stupid example of sorting a small list of characters, insertion sort is the fastest implementation I created.

Acknowledgements and Conclusion


Not really much to conclude, except that I now have a better understanding how to write a sorting algorithm, and some of the pros and cons of different algorithms. I certainly can't look at a data set and give you the big O case for a given algorithm.

But one thing I do want to draw special attention to is Wikipedia's pages on this subject. They vary a bit in information density, but they were incredibly informative, and make use of numerous methods to help communicate how each sort works. If you really want to understand this stuff, I would definitely start with these pages:

• Quicksort
• Merge sort
• Heap sort
• Bubble sort
• Insertion sort

Also, my thought to do this post was sparked by another post on Planet Python that mentioned Insertion Sort, where I recognized the algorithm. I'm not entirely sure, but this may be that post.

Design patterns

Design patterns are a very broad subject, but as far as I can tell, they are primarily common conventions for structuring software. I've never been taught them, and as far as I can tell, I've used nearly all of them, repeatedly. So for an experienced software developer, I don't believe studying design patterns is likely to improve your coding skills much, if at all. However, it could certainly improve your collaboration skills.

Words Matter
If there's one downside to being self-taught in the field of computer programming (there are several), it would be the difficulty of communicating your ideas with those who have a "standard" education. However good my code may be doesn't matter if I spend all my time trying to explain how I'm going to implement something. Formal computer science comes with a whole boatload of terminology, design patterns among them. Being able to say "use the template method pattern to defer processing to subclasses" is much more concise than "in the superclass method, call methods that are overridden in the subclass, but have only stub implementations in the superclass". Even that verbose description is concise compared to what usually comes up with discussing actual project code.

Template Method
The template method pattern is something that eventually comes in handy to anyone who does a fair amount of object oriented design. It's a response to the problem of how to mix specialized behaviour of subclasses with general behaviour of superclasses. The basic idea is that the superclass implementation of a method will contain mostly calls to other methods of the object, which will be mostly abstract in the superclass, and implemented in the subclasses, which won't implement the method being called.
I recently used this on an email reporting system, which used either HTML or text email depending on the job being reported on. There was a fair amount of commonality between both types, in that they dealt with collecting data from the environment and stuffing it into some kind of template (the use of the word template here is unrelated), then formatting that template into an email and sending it along.
The actual email sending was almost the same for both HTML and text, so with just a condition or two we could handle that entirely in the superclass. However, the data that was sent out varied a bit between the two types, as did the emails themselves.

Gist: "Template Method example"

Note that the implementation above is not ideal, because the subclasses do need a certain awareness of the superclass implementation in order to behave properly.

Mediator

The mediator pattern, in my understanding, mostly deals with managing the flow of communication between objects. It puts a layer between your object and it's intended communication target. I use this pattern frequently for building UIs, most of which I build in JQuery, so that's where I use it.

The way I build UIs in JQuery has been a constantly evolving pattern, so this may change, but right now it gives me the flexibility I need. What I usually do is create an object representing the page itself, as well as objects to represent each of the distinct interface areas, which I am going to call widgets (thought that might be too specific of a term in this context). Each of the widgets takes zero or more callback functions, depending on what they do, and the page object is responsible for seeing that these point to the same things. In some cases, they are methods of other widgets (though in typical javascript fashion, they are anonymous functions that call those methods), but more often they are methods of the page object, which accept the communication and see it dispatched to any other widget(s) that are interested. The page object is almost never more than wiring between the widgets.

The following is probably not syntactically correct. It frequently takes a bit of trial and error before I get into the swing of JavaScript OOP.

Gist: "Mediator Pattern example"

Strategy

The strategy pattern deals with abstracting away algorithms. In situations where a different context might require a different algorithm to achieve the desired results, you apply the strategy pattern. This might sounds complex, but in practice, it is as simple as using different validation functions on different data types, as long as you have a common interface to those functions.

Gist: "Strategy Pattern example"

Adapter

The adapter pattern is one that, thanks to Zope 3, I've been familiar with for a long time. An adapter is an object that "wraps" another object to provide a desired interface. Designing a system based on the adapter pattern requires using capital-I Interfaces for establishing object communication. Then, as necessary, adapters are created to allow the available objects to satisfy those interfaces.
To a certain degree, the adapter pattern takes the concept of polymorphism, traditionally understood as being able to use a superclass' interface to interact with instances of subclasses, and expands it. So you can use the specification of an Interface to interact with any objects that are adaptable to that Interface. To use the traditional Bicycle example, Bicycle might extend Vehicle, and have traditional vehicular methods. However, maybe we want to check what color the bike is, or paint it. Vehicle may not have methods for this, but IPaintable might. Then, with a BicyclePainter adapter, we can adapter our Bicycle instance to this interface. (For the record, I've never found the Bicycle example very useful, and I'm not sure if I'm doing you any favours by using it here).

Gist: "Adapter Pattern example"

Conclusion

So there's some design patterns, and their usage. It's by no means comprehensive, and I'm sure many of you will have encountered these in other contexts where my definitions aren't entirely accurate. That's just fine, because the value of these is not in having rigid development patterns, it's having useful ways to elevate the discussion of your development. I've almost never encountered clearly recognizable design patterns in code I inherited, because patterns are theory, and when applied, the real world makes things start to get messy.

References

• Wikipedia: I relied on this for design patterns and their basic descriptions.
• "Adapters" chapter from Grok tutorial

Introductions

Hi there, I'm Alec Munro. For various reasons, I've been unable to engage online for the last several years. That is no longer true, and I find myself with time, so here I am, engaging (well, I hope so).

So what am I trying to engage with? Well, I'm a software developer, interested in refining the process of software development to produce higher quality software. In practice, my skills and experience tend towards Python and Web Development, with the last 5 years being spent in the realm of test automation. Let's break that down...

When I say I want to produce higher quality software, I'm defining quality as "that which meets or exceeds my customer's expectations". This is a definition I'm stealing from someone, but which feels correct to me. There are two implicit conditions in that definition that go beyond simply writing good code: that you know who your customers are, and that you understand their expectations. So for me, developing quality software is a very holistic process, that encompasses the entire lifecycle of a desired piece of functionality.

I've been developing web sites for 14 years, starting with static HTML and JavaScript, moving through Flash and PHP, and finally "settling" on Python about 8 years ago. Since then, web development has almost never been my primary occupation, but it has almost always been a tool I could use to improve the projects I was working on. In the Python world, I started with Zope 2, moved to Zope 3, then Grok, and most recently Pylons and Pyramid. I'm biased towards building everything as a REST-ish web service, with a UI built in JQuery.

I came to test automation because I saw a need. I saw (seemingly) automatable tasks being performed by manual testers, and I took action to address this. I learned, with great difficulty, that many things I had assumed could be easily automated were actually terrible candidates for automation, often due to the development process that produced them. I learned about "testability" (thanks Misko!), and the role that test automation must play in driving development process improvements. I also gained an appreciation for what I call "proactive transparency", which is the philosophy that much of the information people need is too difficult to find, because those producing it don't know how to publicize it (or don't appreciate the need to do so). In test automation, this applies to results of testing, but I've found it applicable to many other areas.

So that's a rough overview of who I am, and what I can do. But where's the engagement? Well, I find myself without a job, but with a bit of a margin before I need a job. So I thought I would take this time to write on subjects I know about, as well as to study and report on those that I don't. This will hopefully give me the opportunity to broaden my skills (specifically for interviewing purposes, I will admit), while also re-engaging with the development community that I have been absent from for several years. For you, the reader, hopefully some of these topics will interest you, and you will participate in my discussions, to correct me where I err, or weasel further answers out of me when I am unclear.

What kind of topics? Well, I have no formal computer science training, so there's a couple of areas that tend to come up in interviews that I don't think I give satisfactory answers on. These include:

• Design patterns. I know many of their names, and I know I use them often in my work, albeit uncredited. I will research the most common ones, and invent problems where they are applicable, and explain why one over the other.
• Sorting. Quick sort, merge sort, etc. Using Python for web development, I've never been held back by the performance of a sorting operation, but I understand that these algorithms are considered quite foundational, and I know I've suffered in interviews due to the lack of them.

I will also go into some topics that are interesting to me, and play to the strengths I have developed during my career.

• Mock library comparison. I consider the use of mock objects to be an essential (and often neglected) part of almost any software development project. I also think there are too many Python mock object libraries. :) I will discuss this in more detail, and show examples of the use of each library, and try to illustrate the strengths and weaknesses of each.
• Web application development. Because of my recent work history, I have virtually no public code to share with potential interviewers. So, purely as a vanity project, I will create what I consider to be a properly tested and documented web application, and write about the process. I'll try to make a useful application, but I can't promise that.
• RabbitMQ, ZeroMQ, Gevent. I keep running across these things, but I've never had an occasion to do much beyond skim their docs. They seem interesting and well regarded by those who are well regarded by me, so I'll look into them.
• Go (the language, I'll leave the game to my father, at least for now). I've heard being laid off is a great time to learn a new language, and two of the jobs I've seen that would be most interesting mention Go, so I think that will probably be it for me.

To further my ideal of engagement, I will post any code I write for any of these in github (also new to me), and encourage contributions from the community. Hopefully, the community will find enough useful in what I create to do so.