I've been using Python for over a year now. It's what I learned to program with. About half a year ago, a fellow coder (friend of a friend) posed the following riddle upon learning that it was my language of choice:
"How would you write a function in Python that knows how many times it's been invoked?"
Let's consider this for a moment. A function that knows how many times it has been invoked is one that would need some access to a scope outside of it's own. Functions are generally pretty transient — they do their thing and then wait until they are told to do it again. There isn't a middling dormant state where they consider how many times they've been told to execute their (probably) menial task.
As a first stab, we might consider a global counter, as in the following setup:
count = 0
def self_aware_function():
count += 1
if count == 1:
print 'This is my first time doing this'
else:
print 'I have done this {} times now.'.format(count)
for i in range(10):
self_aware_function()
Those familiar with Python are up in arms right now, and rightfully so. Here's what you get when invoking self_aware_function:
UnboundLocalError: local variable 'count' referenced before assignment
In Python, when you are in a function and assign a value to an immutable type variable (such as our int count), you end up shadowing the global variable with one local to the function's scope. So when count += 1 is evaluated (remember this is expanded to count = count + 1), Python cannot find the value for count in the expression to the right of the =.
Okay, local variables won't work, how about we use the global keyword or mutable variables?
# global keyword
def self_aware_function():
global count # Now we force the use of the global count
count += 1
# ...
# using a list
count = [0]
def self_aware_function():
count[0] += 1
# ...
These both work and globals were my first idea for a solution. However, when I asked if this was acceptable, I was met with opposition.
"You are only allowed to write code within the function, not outside of it."
That's rough. How do you become self aware of an outside world/scope that you can't even interact with?
Turns out, the answer lies within a popular Python gotcha.
Self-awareness
Here's how you define a default parameter in Python:
def foo(default='bar'):
return default
In Python, default parameters are evaluated ONLY once — when the function is defined. That means the default parameter is "the same" for all invocations of the function. I say "the same" because normally the default parameter will have the same value across multiple function invocations, but if your default parameter is mutable then you change it! And then you can do some really special things.
Case in point, self-awareness:
def self_aware_function(count=[0]):
count[0] += 1
if count[0] == 1:
print 'This is my first time doing this'
elif count[0] >= 10:
print "Who are you to tell me what to do???"
else:
print 'I have done this {} times now.'.format(count[0])
for i in range(10):
self_aware_function()
count is evaluated at function definition to be a mutable list with one integer element.- Each invocation of our
self_aware_function adds another tick to our mutable count parameter.
And we have our cheeky, self aware function!
$ python aware.py
This is my first time doing this
I have done this 2 times now.
I have done this 3 times now.
I have done this 4 times now.
I have done this 5 times now.
I have done this 6 times now.
I have done this 7 times now.
I have done this 8 times now.
I have done this 9 times now.
Who are you to tell me what to do???
If you're wondering, mutable default arguments was the answer I gave after a good amount of thought. I believe there are other solutions and I invite you to share them in the comments :)
[python]
I set some time out to open the box on some Python fundamentals this weekend. I have a few topics to write about but, for today, let's talk a little about objects.
Objects
Objects are a big deal in Python. And rightfully so, as most developers use Python in an object oriented manner, though you can certainly write imperatively or pseudo-functionally too. In fact, some people subscribe to the thought that everything in Python is an object. I'm not going to argue about whether that's true or not so we'll just tip-toe around it and state that there are an awful lot of objects.
So what is an object? Let's use Wikipedia's definition. Objects are characterized by these properties:
Identity (Objects are unique from each other)
class Trivial(object):
pass
obj, diff_obj = Trivial(), Trivial()
id(obj) # 25851216
id(diff_obj) # 26133840
State (Can store data in object)
import os # modules are objects
os.my_data = 'arbitrary'
print os.my_data # arbitrary
Behavior (Can manipulate the object)
print ' '.join(['strings', 'are', 'objects', 'with', 'methods'])
# strings are objects with methods
Attributes and Methods
You're probably familiar with setting object attributes to static data or writing simple methods if you've worked with objects in the past.
class Lannister(object):
def __init__(self, name):
self.name = name
def say_family_motto(self):
print '{} says: "Hear Me Roar!"'.format(self.name)
tyrion = Lannister()
print tyrion.name
# Tyrion Lannister
tyrion.say_family_motto()
# Tyrion Lannister says: "Hear Me Roar!"
But you're actually not limited to such trivial behavior. For instance, since functions are first class objects in Python, you could easily do the following too.
def say_common_motto():
print 'A Lannister Always Pays His Debts.'
tyrion.say_common_motto = say_common_motto
tyrion.say_common_motto()
# A Lannister Always Pays His Debts.
As you can see, we've set the .say_common_motto attribute to the function object say_common_motto, then invoked the attribute.
Before we continue, we should make a distinction between .say_common_motto and .say_family_motto.
type(tyrion.say_common_motto)
# <type 'function'>
type(tyrion.say_family_motto)
# <type 'instancemethod'>
Python resolves the type of .say_common_motto to a function object and .say_family_motto to an instance method object. What's the difference?
You can think of a method as a function with a unique difference. A method always takes the object it's associated with as it's first argument. You don't have a choice on the matter.
Under the hood, when Python sees tyrion.say_family_motto(), it first looks for a .say_family_motto attribute in tyrion (this means you can override an object method by writing to an object attribute with the same name). When it doesn't find that, the interpreter will jump up to the class level and look for say_family_motto function defined at the class level. Once found, it will invoke the function as a method - namely, by attaching the tyrion object to the head of the argument list. That's also why a method definition always includes a positional argument placeholder first (traditionally called self in Python).
Methods are really just a shortcut though. You can actually just define your own function with an argument placeholder for an object and attach the function to the object attribute. An example makes this clearer. Suppose we rewrote the say_common_motto function to make it equivalent to a method.
def say_common_motto(self):
print '{} says: "A Lannister Always Pays His Debts."'.format(self.name)
tyrion.say_common_motto = say_common_motto
tyrion.say_common_motto(tyrion)
# Tyrion Lannister says: "A Lannister Always Pays His Debts."
tyrion.say_family_motto()
# Tyrion Lannister says: "Hear Me Roar!"
As you can see, defining a method in the class is a lot cleaner than attaching a function to the instance object. But both styles get you to the same resolution eventually.
Anyways, hopefully you know a little more about Python objects now.
[objects]
[python]
[functions]
In the next couple months, I'm planning on writing more about Javascript as I pick it up in work and from my own reading. Towards the end of Hacker School, I decided I wanted to explore it as my second programming language. Reasoning: I can return to my functional programming roots and I can round out my understanding of web development by getting intimate with how the browser works.
However, this doesn't mean I will stop developing in Python. Aside from Django exposure at work, I'm planning to continue building web applications for myself - and hopefully with more robust front-end UI.
But, that's not quite good enough. If there was one thing I took away from Hacker School, it was the idea that I should always be pushing myself to become a better programmer. Web development is fun and lets me exercise my creative side, but I want to step outside my comfort zone and pursue other avenues of technology too. I'm not entirely sure what direction I'll look but I think my best bet is to attach myself to an open source project and develop a deep understanding of that problem space.
Anyways, I'll think on that and come back with my decision within the next month. Hold me to it!
[future]
[javascript]
[python]
[django]
[open source]
[hacker school]
I'm spending this weekend filling in some of the holes in my programming background, data structures in particular. As part of the learning process, I want to share my new understanding of heaps.
What is it?
A heap is a type of priority queue, which is just a queue where dequeued elements are primarily selected based on their "priority" and secondarily selected based on the "first in first out" principle. A heap prioritizes by key values of objects it stores, which leads to the two flavors of heaps: the max heap and min heap. The max heap will dequeue the objects with the highest keys first. If there are multiple maxes, the heap will dequeue by order of insertion. As you'd expect, the min heap is the same except it dequeues objects with the lowest keys first.
Introducing the max heap
Although a heap is technically a priority queue, and although we are going to implement it as an array, heaps are commonly represented as a binary tree. Here is the max heap we're going to work with:
There are two conditions that must be met for a binary tree to be a max heap.
- Every parent node must be at least as large as either child nodes. This means the max key will always be at the top of the tree.
- The tree must be complete at all levels except the deepest. The deepest level must be populated from the left. This means if the above tree had another node, it would be the left child of the node 8.
We're going to implement this heap as an array. This boils down to extracting nodes left to right, top to bottom. Here's what it will look like:
Normally heaps hold objects with the keys we are showing in the tree and array representation. For simplicity, we'll just assume the objects and keys are one and the same.
We also need to keep track of the parent and children of any given node. That's pretty natural for binary trees but how is that implemented in arrays? Turns out it's pretty simple with one-indexing, due to the way we are pulling elements off the tree.
1 2 3 4 5 <-- One-indexing
[11, 5, 8, 3, 4]
EXAMPLE:
parent(i) = floor(i/2) parent(2) = 1
left_child(i) = i*2 left_child(2) = 4
right_child(i) = i*2 + 1 right_child(2) = 5
Let's code up what we have. I prefer to have zero-indexing so the math on the parent/children calculation will have to compensate.
class MaxHeap(object):
def __init__(self):
self.arr = []
def parent(self, i):
if i == 0:
return 0
return (i + 1)//2 - 1
def children(self, i):
left = (i + 1) * 2 - 1
right = left + 1
return left, right
Now, a heap has two basic operations: insert and extract_max (extract_min). These are guaranteed to run in O(logN) time, or in other words, the height of the binary tree.
Insert
What does an insert look like in our binary tree model? Following the conditions of a binary heap, we have to insert the new object at the deepest level, moving in from the left. That corresponds to the node marked X below:
It should be pretty obvious that the object we insert could break the heap property of this tree. Whatever key we end up with, we first need to compare it with its parent node. The parent node's key is 8, so if we insert an object with key <= 8 then we wouldn't have to do anything further. But what if the key is something higher like 15? Then our insertion would break heap condition #2.
In this situation, the next step is to swap our inserted node with it's parent node.
Cool. But now when we check 15 against its new parent, the root, we notice we're still in trouble. So we swap again. These swap acts are also known as "bubbling up" or "heapifying up", as the inserted object is promoted levels due to its priority.
Now that 15 has made it's way up to the root node, we can stop. As you can see, the new tree follows all conditions to be classified as a max heap. Here's the code for the insert operation.
def insert(self, key):
self.arr.append(key)
i = len(self.arr) - 1
parent = self.parent(i)
while self.arr[i] > self.arr[parent]:
self.arr[i], self.arr[parent] = self.arr[parent], self.arr[i]
if parent:
i = parent
parent = self.parent(i)
else: # parent is root
break
As you can see, we first insert to the end of the array, then while the inserted key is larger than its parent, we swap it upward until it finds its place.
Extract Max
I believe this is also known as Delete Max, but in either case, this operation removes the max from the heap. And because we're working with a heap, we know the max is the root of the tree (or first element of the array), so we certainly don't need to traverse through the entire structure to determine it.
Now, as mentioned before, the first step is to remove the root node. That leaves us with a tricky situation. What node will replace the root?
Let's go through our options.
- Pull up the 5. Well, now we fail both conditions. The root is now less than the right child, and more importantly we have an incomplete binary tree.
- Pull up the 8. Cool, our root is the max, but now we have an entire empty branch on the right. That seems like a big problem and we can't just fix it by pulling from an entirely separate branch.
- Pull up the 3. Breaks the complete tree again.
- Pull up the 4. We still have a complete tree (in terms of a heap at least). We have a bad root but maybe we can shift that node back down.
So the general solution seems to be, promote the last element of the tree/array.
So now the new root is no longer the max. We need to swap it with one of its children. If we swap with 5, we'll still have the same problem. We'll need to swap with 8. This should lead us to the realization that we'll always want to swap with the higher of the two children, otherwise we'll just be making more of a mess of things.
Now we have our max extracted heap!
Here's the code:
def extract_max(self):
self.arr[0] = self.arr[-1]
del self.arr[-1]
i = 0
left, right = self.children(i)
while right < len(self.arr): # if right exists, so does left
if self.arr[i] < self.arr[left] or self.arr[i] < self.arr[right]:
if self.arr[left] > self.arr[right]:
self.arr[left], self.arr[i] = self.arr[i], self.arr[left]
i = left
else:
self.arr[right], self.arr[i] = self.arr[i], self.arr[right]
i = right
left, right = self.children(i)
else: # we have a heap again
return
if left < len(self.arr):
if self.arr[left] < self.arr[i]:
self.arr[left], self.arr[i] = self.arr[i], self.arr[left]
I'm not actually returning the max here, but you can build that in pretty easily.
extract_max is a bit more complicated than insert. Swapping the new root down takes a few more comparision steps as we have to decide which child to swap with. We're still within O(logN) time though, since we will never need to swap more than the height of the binary tree.
So what are heaps good for?
In general, when you constantly need to access the min or max of some data, heaps are a logical choice, as you just need to pluck it from the top of the tree/front of the array and do a little rearranging. This means they are useful for tasks like managing bandwith on a router (always send the prioritized traffic first) or handling asynchronous event processing (firing off shortest tasks first).
Heaps are also useful in speeding up certain algorithms that require multiple min or max computations. One example is Dijkstra's shortest path algorithm, where you are constantly computing the minimum path for each node.
So, hopefully you've now got a solid understanding of heaps. Next time you're working on something and you find yourself repeatedly taking minimums or maximums, you should give them a try. They will make your life easier.
[heaps]
[data structures]
[python]
So while I was working on interview prep, I got a bit curious about what cool ways bit manipulation might alter the way we might write code. Here's a few examples of short functions you can write using only bit operations.
Simple stuff first
The following trick may be standard fare but seeing as I am not a "classically" trained programmer (no degree in computer science), this guy did tickle my fancy.
When you write out a integer in a binary representation, 5 as 0101 for example, the least significant bit (leftmost bit) represents if the integer is odd or even. Of course, bits further left represent powers of two, hence the term "base two".
0101 is 0*(2^3) + 1*(2^2) + 0*(2^1) + 1*(2^0)
or 0*8 + 1*4 + 0*2 + 1*1
or 5
Anyone can write a simple function that tests if a given integer x is even. Usually it will involve checking to see if x mod 2 is 0.
def is_even(x):
return (x % 2) == 0
But, given that least significant bit of a binary value represents odd or even, we can write that same is_even function using the AND bit operation.
def is_even(x):
return (x & 1) == 0
For example 6 & 1 is 0.
0110 <-- 6
& 0001 <-- 1
======
0000
This ends up being the same amount of typing but it's interesting that we have this second option of writing the is_even function.
Powerful twos
If you work on Project Euler problems frequently, the following shortcut might be beneficial to keep in mind. Here's a function that checks if x is a power of two.
def is_power_of_two(x):
power_of_two = 2
while power_of_two < x:
power_of_two *= 2
return power_of_two == x
That's pretty compact but it turns out binary is well suited to figure out if a number is a power of two.
def is_power_of_two(x):
return (x & (x-1)) == 0
Let's see this in action with x as some random binary number:
010110000 <-- x
- 000000001
===========
010101111 <-- x-1
& 010110000
===========
010100000 <-- x & (x-1)
So, (x & (x-1)) just removed the left-most bit that was equal to 1. But then, when might (x & (x-1)) be 0? That would only happen when x has only one 1 bit, which means that x must be a power of 2.
Swapping in place
Python is nice in that you never have to use a temporary variable when you want to do variable swaps. This is, of course, not the same in other languages.
Behind the scenes, Python accesses the values of y and x, then rotates them as it unpacks and assigns to x and y. Here's what that looks like when run through the Python disassembler:
import dis
def func():
a = 1
b = 2
a, b = a, b
a, b = b, a
dis.dis(func)
>
> 3 0 LOAD_CONST 1 (1)
> 3 STORE_FAST 0 (a)
>
> 4 6 LOAD_CONST 2 (2)
> 9 STORE_FAST 1 (b)
>
> 5 12 LOAD_FAST 0 (a)
> 15 LOAD_FAST 1 (b)
> 18 ROT_TWO
> 19 STORE_FAST 0 (a)
> 22 STORE_FAST 1 (b)
>
> 6 25 LOAD_FAST 1 (b)
> 28 LOAD_FAST 0 (a)
> 31 ROT_TWO
> 32 STORE_FAST 0 (a)
> 35 STORE_FAST 1 (b)
> 38 LOAD_CONST 0 (None)
> 41 RETURN_VALUE
But, did you know we can actually swap without a temporary variable using XOR too.
To understand what's happening, you should recall that XOR is commutative, x^x is 0, and x^0 is x. Let's break down the XOR Swap Algorithm again.
start -> breaking down -> commuting -> cancelling -> removing 0's
=============================================================================
x ^= y -> x = x^y
y ^= x -> y = y^x^y -> y = x^y^y -> y = x^0 -> y = x
x ^= y -> x = x^y^y^x^y -> x = x^x^y^y^y -> x = 0^y^0 -> x = y
That's pretty cool but I'll stick to Python's easy swap. It is nice, however, to see how binary manipulation can be used to our advantage in languages that don't have an in-place swap.
Now for the disclaimer. While the XOR swap is pretty nifty, it doesn't have much practical use. If you actually plan on using it in the real world, hopefully your application fits in one of these buckets. Turns out, optimizing compilers tend to make temporary variable swaps pretty efficient, often faster than this XOR swap.
Have any more bit manipulation tricks you'd like to share? Leave me a comment, I'd love to see more in action.
[bit manipulation]
[binary]
[tricks]
[python]
[algorithms]
Page 1 / 2
>>
