Instantly share code, notes, and snippets.

# timvieira/reverse.py Last active Jan 16, 2018

What would you like to do?
Reversing a singly-linked sequence defined by a function application with sublinear space.
 # -*- 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()