Reversing a singly-linked sequence defined by a function application with sublinear space.

reverse.py

# -*- coding: utf-8 -*-
"""
Reversing a singly-linked sequence defined by a function application in
sublinear space.

  s[t] = f(s[t-1]) where s[0] is given as input.

Code associated with blog post
"Reversing a sequence with sublinear space"
http://timvieira.github.io/blog/post/2016/10/01/reversing-a-sequence-with-sublinear-space/

Includes two algorithms along with unit tests.

  sqrt:      time O(n),       space O(√n)
  recursive: time O(n log n), space O(log n)

"""
from numpy import ceil, sqrt, log2
from collections import Counter


def recursive(f, s0, b, e):
    if e - b == 1:
        yield s0
    else:
        # do O(n/2) work to find the midpoint with O(1) space.
        s = s0
        d = (e-b)//2
        for _ in range(d):
            s = f(s)
        for s in recursive(f, s, b+d, e):
            yield s
        for s in recursive(f, s0, b, b+d):
            yield s


def step(f, s, k):
    "Take `k` steps from state `s`, save path. Cost: O(k) space, O(k) time."
    if k == 0:
        return []
    B = [s]
    for _ in range(k-1):
        s = f(s)
        B.append(s)
    return B


def sqrt_space(f, s0, n):
    k = int(ceil(sqrt(n)))

    memory = {}
    s = s0
    t = 0
    while t <= n:
        if t % k == 0:
            memory[t] = s
        s = f(s)
        t += 1

    b = n
    while b >= k:
        # last chunk may be shorter than k.
        c = ((n % k) or k) if b == n else k
        for s in reversed(step(f, memory[b-c], c)):
            yield s
            b -= 1


def _test_sqrt_space(N):

    calls = Counter()
    def simple(s):
        calls[s] += 1
        return s+1

    got = list(sqrt_space(simple, 0, N))
    assert got == list(reversed(range(N))), N
    for k,v in calls.items():
        assert 1 <= v <= 2, [k, v]


def _test_recursive(N):

    calls = Counter()
    def simple(s):
        calls[s] += 1
        return s+1

    got = list(recursive(simple, 0, 0, N))
    want = list(reversed(range(N)))
    assert got == want, [N, got, want]

    # not as tight a bound as before because earlier elements are computed more
    # often due to short circuiting.
    B = ceil(log2(N))
    for k,v in calls.items():
        assert v <= B, [k, v, B]


def tests():
    for N in range(1, 100):
        _test_sqrt_space(N)

    for N in range(1, 100):
        _test_recursive(N)

    print 'pass!'


if __name__ == '__main__':
    tests()