Heap Sort

Not a great sort but it is easy to remember. Push everything onto the heap and then pop it back off.

from heapq import heappush, heappop
def heapsort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]

heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

Binary Search

from bisect import bisect_left

def binary_search(list_of_numbers, target):
    in_list = bisect_left(list_of_numbers, target)
    if in_list != len(list_of_numbers) and list_of_numbers[in_list] == target:
        return i
    else:
        return -1

Tail

This will read n lines from the file f. I am pretty sure… I need to double check if it is fully buffering the file.

from collections import deque
def tail(filename, n=10):
    'Return the last n lines of a file'
    with open(filename) as f:
        return deque(f, n)

Moving Average

Smooth out data in time series.

from collections import deque
def moving_average(iterable, n=3):
    # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
    # https://en.wikipedia.org/wiki/Moving_average
    it = iter(iterable)
    d = deque(itertools.islice(it, n-1))
    d.appendleft(0)
    s = sum(d)
    for elem in it:
        s += elem - d.popleft()
        d.append(elem)
        yield s / n

Round Robin

Could probably use this as in deque to implement a circular buffer.

rotate(-1) just shifts elements to the left by one without truncating or pushing elements off the end of the queue. They get requeued on the right if the fall off the left side of the queue.

from collections import deque
def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    iterators = deque(map(iter, iterables))
    while iterators:
        try:
            while True:
                yield next(iterators[0])
                iterators.rotate(-1)
        except StopIteration:
            # Remove an exhausted iterator.
            iterators.popleft()

Efficient Counter

from collections import Counter
c = Counter({'red': 4, 'blue': 2})
# top two 
c.most_common(2)

Build a dictionary of lists

from collections import defaultdict
s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
d = defaultdict(list)
for k, v in s:
    d[k].append(v)

sorted(d.items())

Regular expression matching

You generally want to use a compiled regex pattern if you are going to be searching multiple times.

import re
def displaymatch(match):
    if match is None:
        return None
    return '<Match: %r, groups=%r>' % (match.group(), match.groups())
valid = re.compile(r"^[a2-9tjqk]{5}$")
displaymatch(valid.match("akt5q"))

Split() on steroids

You can use re.split() to split on multiple delimiters and regular expression patterns.

import re
re.split('r\W+')
re.split('\[\,\!')

Useful random selection

import random
# 5 numbers between 1 and 10
my_list = random.sample(range(1, 11), 5)
random.shuffle(my_list)
random.choice(my_list)

LRU Cache

from functools import lru_cache
@lru_cache
def count_vowels(sentence):
    return sum(sentence.count(vowel) for vowel in 'AEIOUaeiou')