DEV Community: orenovadia

Solution: Chunked Iterator, Python Riddle

orenovadia — Sat, 03 Aug 2019 22:59:18 +0000

This is a detailed solution to this riddle.

Here it is again: write a function (chunks) where the input is an iterator. And the output is an iterator of n sized iterators.

The first challenge is that the length of the original iterator is unknown. Let's start with a naive broken solution using itertools.islice to create n size iterators without caring about the length of the original iterator:

import itertools
from typing import TypeVar, Iterator

T = TypeVar('T')


def chunks(iterator: Iterator[T], n: int) -> Iterator[Iterator[T]]:
    while True:
        yield itertools.islice(iterator, 0, n)  # yield `n` size chunk of the iterator


for chunk in chunks(iter(range(10)), 3):
    print(f'A {type(chunk)} type chunk, contains items: {tuple(chunk)}')

The output is:

A <class 'itertools.islice'> type chunk, contains items: (0, 1, 2)
A <class 'itertools.islice'> type chunk, contains items: (3, 4, 5)
A <class 'itertools.islice'> type chunk, contains items: (6, 7, 8)
A <class 'itertools.islice'> type chunk, contains items: (9,)
A <class 'itertools.islice'> type chunk, contains items: ()
A <class 'itertools.islice'> type chunk, contains items: ()
.... forever

Using itertools.islice we managed to chunk up the original iterator, but we don't know when it is exhausted. And so, chunks is a generator function that never ends.

To overcome this problem we need to take one item out of the original iterator. Then, we'll use itertools.chain to create a chunk featuring this one item and n-1 more items.


def chunks(iterator: Iterator[T], n: int) -> Iterator[Iterator[T]]:
    for first in iterator: # take one item out (exits loop if `iterator` is empty)
        rest_of_chunk = itertools.islice(iterator, 0, n - 1)
        yield itertools.chain([first], rest_of_chunk)  # concatenate the first item back

The output is:

A <class 'itertools.chain'> type chunk, contains items: (0, 1, 2)
A <class 'itertools.chain'> type chunk, contains items: (3, 4, 5)
A <class 'itertools.chain'> type chunk, contains items: (6, 7, 8)
A <class 'itertools.chain'> type chunk, contains items: (9,)

And That is it!

And in comprehension form (I usually prefer comprehensions, but I must admit that this one is not as readable as the loop form):

    return (itertools.chain([first], itertools.islice(iterator, 0, n - 1))
            for first in iterator)

Performance

The runtime overhead of islice-ing and chain-ing is way smaller than writing your own custom code for chunks since both these functions are implemented in C (for the CPython runtime).

The Caveat

There is a caveat here: This whole solution assumes that the consumer of chunks is consuming the iterators fully and in order. If that is not the case, the order of items in our chunks might not be consistent with the original iterator, due to the laziness of chunks.

Example:

chunk_iterator = chunks(iter(range(10)), 3)
first_chunk = next(chunk_iterator)
second_chunk = next(chunk_iterator)
print(tuple(second_chunk))  # (1, 2, 3)
print(tuple(first_chunk))  # (0, 4, 5)

Cheers!

Chunked Iterator: Python Riddle

orenovadia — Sat, 03 Aug 2019 01:22:30 +0000

I really like this python riddle. And it is (almost) a practical problem.

Say you have an iterator (stream of objects of unknown length). And you want to separate it to equal size chunks. An example: splitting a file to multiple smaller sized files.

Doing the same with lists is much easier because the length of the list is known:

from typing import List, TypeVar

T = TypeVar('T')


def chunks(l: List[T], n: int) -> List[List[T]]:
    return [l[i:i + n]
            for i in range(0, len(l), n)]


items = list(range(10))
print(chunks(items, 3))
# [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]]
print(chunks(items, 4))
# [[0, 1, 2, 3], [4, 5, 6, 7], [8, 9]]

The riddle is: write chunks where the input is an iterator. And the output is an iterator of iterators


def chunks(l: Iterator[T], n: int) -> Iterator[Iterator[T]]:
    ????

I will add the solution later today or tomorrow.

Extra points for run-time performance

Followup question: What problem can you spot in the solution to this problem?

Enjoy

Edit: Solution is here

When Was a Bug Introduced? Bisecting with Pytest

orenovadia — Mon, 24 Jun 2019 21:59:39 +0000

Turns out that a very old test was broken for a while and wasn't running in the automatic build, whoops.

It would be very helpful to find the exact commit that broke the test. Well, git-bisect to the rescue: git bisect will binary search the commit history to find the bad commit. And we can use pytest to tell git if the test is passing or not for any possible commit.

Set Up

Here is a toy repository with a simple function and a unit test:

$ ls
my_script.py  README

And this is my_script.py:

from functools import reduce
from operator import mul

def product(factors):
    return reduce(lambda x , y: x - y, factors)


def test_product():
    assert product([1, 2, 3,]) == 6

Pretty simple so far. test_product broke for some reason.

Let's look at the commit history:

$ git log --oneline
7e26872 Unrelated commit # 21
f67f19e Unrelated commit # 20
...
2b37410 Unrelated commit # 15
80956a1 Unrelated commit # 14
d2a3327 Some innocent change that certainly did not break anything
8cc3f8b Unrelated commit # 13
1b09ced Unrelated commit # 12
...
3e73dfa Unrelated commit # 2
790ba87 Unrelated commit # 1
0c75c27 unrelated commit
d7af196 Added product function with a unit-test

Bisecting

There are several ways to use bisect. We are going to tell it when the test was passing, and how to run the test, and it will take care of the rest.

We begin with bisect start:

$ bisect_start

Tell it that our current commit is broken:

$ git bisect bad HEAD

Let's find a commit where we know the test was passing. Say, the commit that introduced the test:

$ git blame my_script.py | grep test_product
d7af196a (oren 2019-06-24 12:48:35 -0700 8) def test_product():

Tell bisect this commit is good:

$ git bisect good d7af196a
Bisecting: 11 revisions left to test after this (roughly 4 steps)
[97c3a24f28f72bec1885445eb3947e446d0804fe] Unrelated commit # 10

Now we start bisect off with a command to run the test, bisect uses the exit code of the command to tell whether each commit is good or bad, that works because pytest has a non-zero exit code if tests fail (And, pytest can run a specific function):

git bisect run pytest -qqq my_script.py::test_product
....
....
....
d2a3327df55cb9bf9b43780f9adb223e93ba093d is the first bad commit
commit d2a3327df55cb9bf9b43780f9adb223e93ba093d
Author: oren <----@----.--->
Date:   Mon Jun 24 12:50:58 2019 -0700

    Some innocent change that certainly did not brake anything

:100644 100644 0be2cd4c2d0e450026507ee86e058785de56cadc 98c1b14d74c4f46b538df5cc1d32b9bb42afc791 M  my_script.py
bisect run success

Cool!

And indeed, this is the bad commit:

$ git show d2a3327df55cb9bf9b43780f9adb223e93ba093d
commit d2a3327df55cb9bf9b43780f9adb223e93ba093d
Author: oren <----@----.--->
Date:   Mon Jun 24 12:50:58 2019 -0700

    Some innocent change that certainly did not brake anything
.......
.......

 def product(factors):
-    return reduce(mul, factors)
+    return reduce(lambda x , y: x - y, factors)

Note: if you are using a script as a command to git bisect run. Make sure this script is not tracked by git, otherwise it might change when git changes revisions.

Cheers!