Hash Table (Map) Built In Python

Lately, I've been studying up on my data structures and algorithms. I decided it would be fun to implement a HashMap (the map abstract data type). I decided to rely on Python's idiomatic __hash__ function, and use linear probing as the collision resolution mechanism. In the process of building this, I learned a few things and I would like to share them.

Deletion is the Hardest Part

Overall the data structure was not very difficult to build. Well, except for deletion. It's not as simple as shifting all elements back (overwriting the deleted). Instead, I had to flag the item as being "deleted". This wasn't that difficult, however, maintaining quick-access sizing on the data structure was complected by it.

In the end, I had to maintain two states: one that programmers who called __len__ would see and the actual count of stored elements (being actual plus deleted).

Linear Probing is Not as Hard

My "find index" method, boiled down to just

    def __locate_index(self, key):
        i = hash(key) % self.capacity()

        while self.__values[i] and self.__values[i][0] != key:
            i = (i + 1) % self.capacity()

        return i

Where each value is just a tuple where elements 0 and 1 are the key and its value, respectively.

Everything Else is Just Bookkeeping

In the end, the code wasn't too difficult. In the end, the class had a lot more state than I would've liked, however, "getting it right" wasn't that difficult. As always, I hope I'm not missing any edge cases with my tests.

As usual, the code is on github and I'm open to any suggestions or thoughts.

Controversial Programming Opinions I Agree With

I recently came across Bill the Lizard's blog post about controversial programming opinions. Shockingly, some of these really threw me off guard. Others, however, I kind of agree with. I'm fairly new to this development thing, but I would still like to take my chance to chime in on some of these "controversial" opinions that I fully agree with.

5. "Googling it" is okay!

So, there's been a lot of debate about whether google is helping or hindering us. One of my favorite articles about google's psychological affects argues that we are becoming reliant on google for "mindshare" (the process of delegating memory tasks to people around us). Some people are disturbed by the idea that google could be "replacing our memory" but I see it as a good thing, and here's why:

• If we didn't have google to quickly retrieve information for us, we would have to use some other form of reference (dictionary, textbooks) which are expensive, are not always available, and have a longer look-up time. Or maybe we would just neglect to pursue correct information altogether (let's face it, we're pretty lazy).
• Consider the quotes: "I never commit to memory anything that can easily be looked up in a book" and "Never memorize what you can look up in books." (Einstein) and ask yourself, "does this apply to the opinion 5?"
• There is too much information to store it all in your mind. I mean, don't get me wrong, there are plenty of things we should know as citizens and craftsmen in general, however, computer science is growing by the second. We can't know it all. Personally, I'm thankful that google knows things that I don't.

6. Not all programmers are created equal.

The gist of this one says that it's wrong to think that the amount of experience a developer has will indicate how good of a developer he (or she) is. I think Coding Horror has a few important points to make about this when he writes about becoming a better programmer, without programming.

7. I fail to understand why people think that Java is absolutely the best “first” programming language to be taught in universities.

Here's why I agree with this one:

• Although OOP is a good thing to teach, universities (perhaps unfortunately) have to cater to a variety of majors, not just computer science. OOP is not necessary for many engineering students (e.g. electrical engineers who program chips in C and Assembly).
• Java is difficult to "ease into." Intro to programming classes are just that, an intro. They should illustrate basic concepts. Java has a lot of overhead. For example, in Java, the classic "Hello, World" program has overhead that teachers, upon first exposure to students, are forced to wave their hands at. Right off the bat students are told to "just ignore 80% of what they're typing, just to make the computer say hello." Whereas, in simple languages like Python and Ruby, "Hello, World" can be as simple as a print statement and a string, two simple intro concepts that are isolated and less distracting than embedded classes.
• For more advanced classes, a language like Java may be appropriate; however, there is a lot of speculation going around that Java is on the decline in the industry. The point is, even if it is the current, best language to teach -- it won't always be. It will die.
• Java is a great language for teaching OOP, I'll give it that. But it fails to illustrate certain, slightly advanced, fundamental programming concepts (that schools like to teach) like pointers, manual memory allocation, etc... So even for advanced classes it isn't capable of teaching some slightly more advanced concepts.
• I am, personally, fine with schools using Java, it is a good language. The statement that "it is absolutely the best" is flawed in that, it's just one of many excellent programming languages. To anyone who thinks otherwise, I would highly suggest Guido's PyCon keynote in which he criticizes language holy wars and trolls.

9. It’s OK to write garbage code once in a while.

• It's better to write quick garbage code that does the job and later refactor it than it is to be an Artist.
• Proof of Concept (POC) code is just proving a point. It doesn't necessarily need to be later maintained, read or extended.
• Writing crappy code is part of learning to write better code. Also, refactoring your bad code can help you learn how to refactor others' bad code.

18. If you’re a developer, you should be able to write code.

Assuming "developer" means "one who constructs software" it seems necessary to be able to "stack the legos." Similarly to you can't break an omelette without breaking some eggs, you can't construct software without writing some code.

There are the opinions I find myself pretty much for. Please feel free to disagree in comments and let my know what you think.

Determinant in Haskell

In linear algebra, the determinant is quite a useful operation that can be done on matrices. To further my understanding of Haskell, I decided to program a solver for systems of equations. One of the best ways to do this dynamically is through Cramer's Rule which needs to be able to calculate determinants. So, here's my recursive code for finding determinants:

determinant :: (Num a, Fractional a) => [[a]] -> a

determinant [[x]] = x
determinant mat =
 sum [(-1)^i*x*(determinant (getRest i mat)) | (i, x) <- zip [0..] (head mat)]

So, in this code, the base case is a 1x1 matrix. The getRest function simply returns the matrix without the head row (topmost) and without the \(i\)th column.

The code and tests are available on my github.

Proof by Induction Example

Proof by induction is a powerful, accepted tool for producing not only mathematical proofs but also proofs of algorithms in computer science and other fields as well.

The concept of proof by induction, is generally described as being a three step process:

1. Prove a base case (in many cases we call this \(P(1)\)).
2. Assume that the \(k\)th case is true (we call this \(P(k)\)).
3. Show that the \(k+1\)th case is true (we call this \(P(k+1)\)).

As can be seen \(P(1) \rightarrow P(2)\), since our base case has been established at \( P(1)\) and we have shown that for our \( k+1\)th case, when \( k = 1\) (i.e. \(P(2)\)) our proposition stands. This can be further extended to show that \( P(2) \rightarrow P(3) \rightarrow ... \rightarrow P(n)\).

So, in less-mathematical terms, proof by induction is as simple as proving some proposition is true for some starting value, and then verifying that it is true for the next one, and the next one, continuing on as far as it needs to or, in other words, to the \(n\)th value.

The following is a simple, somewhat standard example.

Problem

\( \forall n \in \mathbb{N} \), prove that: \[ \sum_{i = 1}^{n} i = \frac{n \left( n + 1 \right)}{2} \]

(This is saying that if we sum up all the numbers from one to \(n\), that sum should equivalently be calculable by \( \frac{n \left( n + 1 \right)}{2} \))

Proof

 Before we start the proof, it's useful to...
\[
  \text{let } P(n) =  \sum_{i = 1}^{n} i
\]

Now...

Proof by Induction

Step 1: Prove base-case, \( P(1) \):

So, the sum of all number from one to one is:
\[
  P(1) = \sum_{i = 1}^{1} i = 1
\]

Now we verify that our formula works for \( n = 1\):
\[
  \frac{n \left(n + 1 \right)}{2} = \frac{1 \left(1 + 1 \right)}{2} = \frac{2}{2} = 1
\]

It checks!

Step 2: Assume that \( P(k) \) is true:

So, here we are assuming that:
\[
  P(k) = \sum_{i = 1}^{k} i = 1 + 2 + 3 + ... + k = \frac{k \left( k + 1 \right)}{2}
\]

Step 3: Show that \( P(k+1) \) is consistent:

So, \( P(k+1) \) looks like, (replacing \(n\) with \( k + 1\)):
\[
  P(k+1) =  \sum_{i = 1}^{k+1} i = 1 + 2 + 3 + ... + k + (k + 1) = \frac{\left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]}{2}
\]

Noticing that \( 1 + 2 + 3 + ... + k \) is the same as \( P(k) \) from Step 2:
\[
  \frac{k \left( k + 1 \right)}{2} + \left( k + 1 \right) = \frac{\left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]}{2}
\]

Multiplying both sides by \(2\):
\[
   k \left( k + 1 \right) + 2\left( k + 1 \right) = \left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]
\]

Distribute \(k\) and \(2\) on the left, add the \(1\)s on the right:
\[
  k^2 + k + 2k + 2 = \left( k + 1 \right) \left( k + 2 \right)
\]

FOIL the right:
\[
  k^2 + k + 2k + 2 = k^2 + 2k + k + 2 \text{      $\square$}
\]

It's really as easy as that!

Nieve Prime Finder in Haskell

To solve a cyber-dojo challenge (implement a function/method that returns the prime factors of a number) I decided to implement a somewhat nieve (but workable) isPrime function in Haskell. Here's the code:

-- Public type-definition
isPrime :: Integer -> Bool

-- Private type-definition
lookForPrimeFrom :: Integer -> Integer -> Bool

isPrime 2 = True
isPrime n
 | n < 2     = False
 | even n    = False
 | otherwise = lookForPrimeFrom n 5

lookForPrimeFrom n i
 | ceiling (sqrt (fromIntegral n))+1 < i   = True
 | (n `mod` i) == 0                        = False
 | otherwise                               = lookForPrimeFrom n (i+2)


This code (to me at least) seems very self-documenting. The more I'm playing around with Haskell, the more I'm enjoying it and seeing its strength as a functional language. I think if I were to map this algorithm into more mathematical notation it would look like:

\[
  \forall n \in \mathbb{N}
\]
\[
  p \left( n \right) = \left\{ \begin{array}{lr}
  0, & n = 1 \\
  1, & n = 2 \\
  0, & \text{$n$ is even} \\
  1, & \nexists m \in \left\{ x \in \mathbb{N} \, | \, 5 \leq x \leq{\sqrt{n}}, \text{$x$ is odd}  \right\}
  
\end{array} \right.
\]

As you can see, this is somewhat nieve; however, the Haskell code really is quite similar to the mathematical notation.

Latest Project: Ultimate Dev. Machine Script

The latest thing I have been working on is pretty cool. It's simply a Python script called udm.py that you toss onto a virtual machine (Debian based) and run using:

sudo ./udm.py

Then, it works its magic and installs compilers, interpreters, IDEs, editors, documentation generators, source control software, and much more! So far, it has been successfully tested on Linux Mint 14.1. Here's a brief view of it:

As it stands, it is very configurable. You can add and remove packages, and even include special installation instructions all with plug-and-play-like ease. Packages are organized by topic, in simple, struct-like objects I call containers. In the udm_script/desired_packages.py script, entire containers can be added or removed from the installation. In the containers, specific packages can be added or removed. If you know of any interesting development packages that I should add, let me know!

All code is available on my github account.

Latest Project: Email Miner

Just to add to my collection of "data miners" built in Python, I made a (very bare-bones) email miner. Basically all it does is strip emails out of a given URL and save them in some output file. Here's what it looks like (again, forgive my strange windowing system):

So, as you can see it's pretty straightforward. I used a little bit of polymorphism-type classes to make the output formats. Basically, all that needs to happen to add more is the definition of a derived class, the implementation of a writer method and then the new class's name needs to be added to a dictionary of other writer class-names and it's good to go! I love this Python thing...

All code is on my github.

Haskell DSA: Quick Sort

Haskell continues to astound me! I have never implemented the quicksort as simply and, frankly, elegantly as this:

quickSort :: (Ord a) => [a] -> [a]

quickSort [] = []
quickSort (x:xs) = quickSort lesser ++ [x] ++ quickSort greater
 where lesser = [e | e <- xs, e < x]
       greater = [e | e <- xs, e >= x]

Here's a quick, line-by-line for anyone who's interested.

• quickSort :: (Ord a) => [a] -> [a]
  The optional (gotta love that word in programming) function definition. It basically says that quickSort is a function that takes a list of objects, [a] and returns another list of a. Ord a means that a is ordinal, or, as far as we're concerned, sortable
• quickSort [] = []
  The first pattern we're trying to match -- if we're given an empty list, return an empty list!
• quickSort (x:xs) = quickSort lesser ++ [x] ++ quickSort greater
  This line does a few cool things: (1) split up a passed list into a first element and remainder, then (2) return the lower ordered elements and the higher sorted on either sides of the first element!
• where less = [e | e <- xs, e < x]
      greater = [e | e <- xs, e >= x]
  This where clause uses list comprehensions to build and define the lists of lower and higher ordered values. Note that the higher values are also (if the case may be) equal to the head of the list (also know as the pivot).

Heap (Max) in Python

Lately I've been practicing my data structures and algorithms and I came up with this interesting implementation for a max heap:

class Heap(object):
    """ A max heap, parents have two or less equal or smaller children """
    def __init__(self):
        """ Set the count to 0 and it has no root node """
        self.count = 0
        self.root = None

    def heapify(self, iterable):
        """ loops elements in the iterable and adds them to the heap """
        for elem in iterable:
            self.add_item(elem)

    def add_item(self, ordinal):
        """ Adds an ordinal item using priority """
        self.count += 1
        if self.count == 1:
            self.root = Node(ordinal)
            return

        i = self.count
        current_node = self.root
        new_node = Node(ordinal)

        while i != 1:
            if current_node.data < new_node.data:
                current_node.data, new_node.data = new_node.data, current_node.data
            if i%2 == 0:
                if current_node.left:
                    current_node = current_node.left
                else:
                    current_node.left = new_node
            else:
                if current_node.right:
                    current_node = current_node.right
                else:
                    current_node.right = new_node
            i /= 2

class Node(object):
    """ Used to traverse the heap """
    def __init__(self, ordinal):
        """ Require data, make the pointers empty (to None) """
        self.data = ordinal
        self.left = None
        self.right = None 

This design of a heap is pretty interesting because it uses the binary representation of Heap.count (the number of elements in the heap) to determine where the next node should go. The algorithm for this is pretty straight forward:

Increment the `count` by 1         // We're adding a new item 
`i` is `count`
`current node` is `root node`

Check 1: if `new node's value` > `current node's value`,
             then swap(`new node's value`, `current node's value`)

Check 2: if binary(`i`) ends in 0, // AKA is even, (i%2 == 0),
             then `current node` is `current node's left`
         otherwise `current node` is `current node's right`

Check 3: if `current node` is null
             then `current node` is `new node`
         otherwise `i` /= 2 and goto Check 1

The end result is a balanced heap! I also added a __str__ method to the Node class for testing:

    def __str__(self):
        return "[%s <- %s -> %s]" % \
                 (str(self.left) if self.left != None \
                                 else 'END', str(self.data), \
                  str(self.right) if self.right != None \
                                 else 'END')

One Line Fizz Buzz Test in Python

Here it is (in all its ugliness):

print '\n'.join("Fizz"*(i%3==0)+"Buzz"*(i%5==0) or str(i) for i in range(1,101))

Python is pretty astounding. This little bugger was easy to code, it is somewhat readable, and it is even understandable. Pretty cool, eh?

Short explanation:

• '\n'.join(...)
  Every item generated in the join function will be on its own line
• for i in range(1,101)
  Loop from 1 to 101, giving i the value of each
• "Fizz"*(i%3==0)+"Buzz"*(i%5==0) or str(i)
  If i is divisible by 3 then keep "Fizz", do the same for "Buzz" with 5. Add the kept values together. Or it will simply output i as a string if it fails to get "Fizz" or "Buzz"

Maybe, Just and Nothing (More Bragging on Haskell)

Man, this Haskell thing is pretty cool. One of (in my opinion) the most annoying things that a programming paradigm can do is consider unexpected behavior to be normal behavior. For instance, most list searches return -1 when the element you are looking for does not exist. Does returning -1 makes sense? No... Not really. Well, anyways, Haskell defeats this type of thing with the following line (this comes with the standard library):

data Maybe a = Nothing | Just a  

Basically all it means is, there's this data type called Maybe (remember, uppercase means constant) and when it is given a type it may just return it or it may return nothing!

This tool is one of the coolest things I have seen in Haskell, thus far. What is the power in this? You can make functions with expected behavior! For instance, consider this quick, binary search I built:

binarySearch :: Ord a => [a] -> a -> Int -> Int -> Maybe Int

binarySearch l e beg last
 | lookat == e = Just i
 | i == (length l)-1 || i == 0 = Nothing
 | lookat < e = (binarySearch l e i last)
 | lookat > e = (binarySearch l e beg i)
 where i = quot (beg+last) 2
       lookat = l !! i

The Maybe, Just and Nothing allow the function to be loose enough that the function can respond with ,"I couldn't find what you were looking for; I found nothing!" This seems to be a huge plus of Haskell. I don't know of many strongly-typed languages that allow this level of Dynamicity.

Programming Challenge Sites

    You know, as a developing programmer one of my biggest challenges is finding ways to exercise new languages/skills/tools that I am learning. There's nothing worse than reading about some new language or paradigm and then thinking, okay, I get it but what now? This is where programming challenge sites come in handy! They tend to provide small problems that can serve as an outlet for new skills and technologies as well as stretch your problem-solving abilities. Here are a few of my favorites:

 

1. Project Euler is a superior collection of mathematical programming challenges which grows progressively more difficult with each new problem. At this point there are 267248 members who have solved at least on problem on PE; however, some problems have as few as 100 solvers! PE is by far one of my favorite sites to turn to for programming challenges on my days off; also it's named after one of the mathematical greats, Leonhard Euler.

    2.  Usually, the StackExchange code golf site's member-provided problems are concerned with shortest code-length solutions (thus the "golf") but there are also a frequent slew of bizarre problems. This is such a cool site. IMHO, the feedback-oriented, well designed StackExchange engine works well in code golf form.

3. Rosalind is a biology programming challenge collection. It has a similar feel to Euler, except what it lacks in mathematical problems it makes up for in string manipulation. The challenges are fun, and more suited for beginners in programming (don't get me wrong, there are some really difficult ones!)

4. Dave Thomas' code katas are designed to challenge and insight the mind. Thomas, co-author of Pragmatic Programmer (that legendary book that us developers should all read) constructed a nice little set of though-provoking challenges, that will (if used properly) increase your critical thinking capacities.

5. Cyber-dojo is a set of team-oriented problems with a focus on TDD. It is meant to be a simplistic environment in which programmers are encouraged to focus on the solving; not the solution. It can be a great way to improve problem solving abilities, hone testing skills and expand your knowledge of new (or old) languages.

Twitter for Learning

    I used to be a twitter hater. It just seemed like some enormous aggregate of worthless quotes from shallow celebrities and humorous meme-like one-liners from role players.

I couldn't have been more wrong...

    It turns out that, sure, although there exists banality on twitter there are also many valuable resources for gaining information regarding just about anything. Here are some practical aspects of twitter that I have discovered:

1. Twitter can help you recognize trends in software development, by keeping you up to date on the thoughts of the "rockstars" and professionals in the field. Through their comments, and links to recent blogs you can begin to gauge where the field is heading.
2. If you are learning a new technology, or already have an abundance of knowledge, you can follow tip-providing twitter accounts which give practical, to-the-point insight. For example, I follow @vimtips, @RegexTip, @java_tips, @TexTip, @AlgebraFact and more. Each of these has taught me some new tricks for tools that I use nearly every day.
3. Finally, twitter can keep you updated on group activities. The last few months I have gone to local Python and Ruby user group meeting which I heard were happening solely because of twitter.

    Through the last few months of using twitter, I'd really like to say that I have gained some practical knowledge. Do you agree and think that twitter is a useful tool for learning? Perhaps I left out more benefits of twitter? Or is twitter just pure evil? Feel free to share your thoughts.

Why I am in Computer Science and Math

    You know, 8 years ago when my dad first tried to teach me programming in BASIC, I couldn't stand it and thought, why in the world would anyone want to do this? A few years gone by, however, I started playing the massive online virtual reality game titled (quite justly) Second Life.

    I spent a good amount of time on weekends in the virtual world, not to socialize, not to participate in the "gun fights" held therein -- something else drew me in -- building. Second Life provides a very rich environment for constructing objects from basic, mutable shapes called prims. I quickly began constructing swords, jetpacks, guns, and anything else that could come to mind. Building these structures was a blast, but these structures were "dumb;" the extent of their interaction with the world was their ability to be attached to my avatar. This led to my discovery of Second Life's scripting capabilities.

    Scripting the structures was like giving them souls (so to speak), engendering in them an ability to interact with their surroundings. My enjoyment for scripting quickly surpassed my enjoyment for building. It was a very fun experience; I would construct objects, give them "minds" or other teenagers on the site would hire me to give their objects minds. In the end I received a new appreciation for programming, through this virtual sandbox. Later in high school, after I had taken a C programming class for fun, I decided that SW development is what I want to do. Ever since, I have been enjoying learning about new technologies, languages and methodologies and I hope to share some of these here.

    "What about math?" you may ask. Well, the story of my experiences with math is simpler: I have been doing it since I was a small child and it has never ceased to be fun, challenging, and exciting for me.