Skip to content

Instantly share code, notes, and snippets.

@timvieira
Last active January 16, 2018 17:26
Show Gist options
  • Save timvieira/d2ac72ec3af7972d2471035011cbf1e2 to your computer and use it in GitHub Desktop.
Save timvieira/d2ac72ec3af7972d2471035011cbf1e2 to your computer and use it in GitHub Desktop.
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment