Python Modules Hiding in Plain Sight — Part I (bisect)

Python bisect module — artist depiction

A free-to-read version of this story appears on my blog at this link if you are unable to read it here.

A tour of the Python standard library shows a number of modules that are popular and in every day use and a number of others which are either underused, underappreciated or works behind the scenes powering other modules. In this article series, I will try and discuss some of the most interesting ones.

First up is the bisect module which, given its size — provides a lot of power to the programmer in working with sorted containers.

Bisect — Binary Search and Insertion

The core of this module are four functions — two of which provide binary search into an sorted list or container, and the other two using these functions to insert a new element into the list, while maintaining the sorted order.

The first two are,

1. bisect_left(a, x, lo=0, hi=len(a), key=None) — Return the insertion point in the list a for the new item x so that the sorted order is maintained. The insertion point will be to the left of any existing entries.
2. bisect_right(a, x, lo=0, hi=len(a), key=None) — Return the insertion point in the list a for the new item x to the right of any existing entries so that the sorted order is maintained.

The next two are,

1. insort_left(a, x, lo=0, hi=len(a), key=None) — This function uses bisect_left to find the insertion point for x into a and inserts it into that position, while keeping the sorted order.
2. insort_right(a, x, lo=0, hi=len(a), key=None) — This function uses bisect_right to find the insertion point for x into a and inserts it into that position, while keeping the sorted order.

NOTE: By default, the entire list is used. The params lo and hi can be used to indicate a subset of the list as lower and upper indices respectively .

The simplest example is a binary search for an existing item in a sorted list.

[embed]binary search using bisect_left

Let us try this on a sorted list.

[embed]binary search function demo

NOTE: The bisect module assumes that the input list is already sorted, but doesn’t raise any exception if it isn’t. Hence using the bisect module’s methods on unsorted list will return meaningless and incorrect results.

Let us now try the insort functions to try and insert some data at the right place.

[embed]Example of using the “insort_…” functions

List Search Functions

We can now write some generic list search functions to return the index of an element in a sorted list using the bisect module. These functions assume the entire list is used for the search.

[embed]Generic search functions from left and right on sorted lists using bisect

Here are examples of these functions in action.

[embed]Examples of the list search functions usage

You can find more examples of a similar nature in the Python module documentation for bisect.

It is possible to write more interesting functions which are built upon these generic functions. Here is an example of a function that returns all occurrences of an element in a list as a range — and examples of its usage.

[embed]A generic function returning the range of occurrences of an element in a (sorted) list

[embed]Examples of usage of the occurrences function

Numerical Range/Table Look-ups

The bisect functions are very handy for implementing functions which need numerical range/table look-ups. For example, one can think of these as functions that create a statistical mapping from a range of numeric data to specific classes of outputs.

Common examples are class grades, ratings and/or reviews.

Here is an example of an IQ (Intelligence Quotient) mapping function written from first principles using numeric ranges.

[embed]A function mapping an IQ score to its class

[embed]Examples of the IQ function in action

The function can be written in a much nicer way using the bisect module — using the idea of finding the position for an element in an existing list — and then mapping its index to a specific class.

[embed]IQ score -> class function rewritten using bisect

You can verify that this gives the same results as the original function.

NOTE: Apart from a cleaner approach, this is also a faster solution since the bisect lookup works in O(log(N)) time complexity, whereas the cascading if..else logic of the original function is much slower.

A Custom Range Look-up Dictionary

One can extend the idea of the range look-up function developed above to write a custom dictionary suited for these kind of problems. The idea naturally evolves from the observation that we are doing a mapping from a set of numbers to a set of classes (strings) in the modified function above.

The code of the dictionary itself is so simple that it seems almost too good to be true.

[embed]

Let us see how to use this dictionary for the IQ example.

[embed]

You may observe how we had to introduce an extra class — with the key 0 — in the new scores_class_dict which we are using to initialize the range dictionary instance with. This is required because we are now converting a range of values to exact key look-ups with one-down logic, so every class kind of shifts down.

You may verify that this produces the same output as the earlier two functions.

Word Search

Since bisect functions work with sorted lists — they can work with list of words as well in a very natural way. As words are sorted in alphabetical order — searching for words in a sorted list of words by a prefix sub-string is a direct application of the binary search provided by these functions.

Here is a fully developed example of this, where we process a wordlist file, containing one word per line and then search for all words matching a certain prefix.

[embed]

On Linux and related nix systems, there is a standard word list file which can be used to test this code. Here are examples of this function in action. (The output has been modified to reduce the line length*)

[embed]

I hope these examples helped to convey that even being a tiny module, the bisect module punches above it’s own weight and provides a powerful set of functions to add to any Python programmer’s toolkit.