Posts

Showing posts from November, 2016

Binary Search in Python and C

Earlier this year I was writing a Python script wherein I had to search a two dimensional grid of longitude and latitude values to retrieve the correct elevation at that point. I originally started with linear search, but it became evident when that grid became fine enough that linear search was wasting precious time. Instead, I read up on binary search (also, interpolation search, which is even faster given that the data are evenly distributed, but that's a topic for a future post).

Binary search will locate a point in a sorted array in \(\mathcal{O}(\log(N))\) time. If you're curious about the mathematics/reasoning for this conclusion, see this answer on SO; I'll paraphrase the logic here, because it's really quite interesting.

Binary search works by starting in the middle of the array, as opposed to either end. Next, we ask, is the entry we're looking for greater than, less than, or equal to the current one? If it's greater, we move to the middle of the upp…

Matrix multiplication in Python

Image
Linear algebra is absolutely everywhere, and many algorithms and data structures use this basic mathematical operation. There are several ways we can multiply arrays of data together in Python - some slow, and some extremely efficient/fast.

First and foremost, we have NumPy's dot method, which multiplies two arrays together (I, however, tend to write something along the lines of from numpy import dot as mult, so the fact that it's a matrix multiplication is more obvious). EDIT: It should also be noted that in Python 3.5+, the __matmul__ method defines the @ infix operator, so instead of np.dot(arr1, arr2), we may write arr1 @ arr2 (c.f. PEP 465).

We may also use NumPy's einsum method, which was recently brought to my attention by a friend. For example, given two matrices:
>>> X = np.random.randn(4, 4) >>> Y = np.random.randn(4, 4) >>> X array([[ 1.65507608, -0.39287161, -1.05303575, -0.61274276], [-0.88893625, -0.06474647, 0.78705911, 2…

Bubble Sort in C and Python

This blog is just going to be filled with programming/algorithm examples, which are sometimes thorough, and sometimes not.

Here's an example of bubble sort in Python (probably easier to understand than C).
#! /usr/bin/env python3.4 # -*- coding: utf-8 -*- """ A quick implementation of Bubble Sort """ from random import randint from array import array from typing import Iterable from types import FunctionType def checkReturnArray(f: FunctionType) -> bool: """ Decorator to ensure array has been sorted """ def new_f(*args, **kwds) -> bool: res = f(*args, **kwds) for i in range(len(res) - 1): if (res[i] < res[i + 1]): return False else: return True return new_f @checkReturnArray def bubbleSort(arr: array =array('I', [0])) -> Iterable[int]: """ O(N^2) time complexity """ arrLength = len(a…