SHOW:
|
|
- or go back to the newest paste.
| 1 | #!/usr/bin/python | |
| 2 | ||
| 3 | def approx_eq(A, B, eps): | |
| 4 | """ [real] [real] epsilon => Boolean | |
| 5 | ||
| 6 | Checks if A and B are approximately equal, within epsilon | |
| 7 | ||
| 8 | >>> approx_eq([1, 2], [1.0, 2.0], 1e-6) | |
| 9 | True | |
| 10 | >>> approx_eq([1.5, 2.75], [1.5, 2.7], 0.01) | |
| 11 | [1.5, 2.75] | |
| 12 | [1.5, 2.7] | |
| 13 | False | |
| 14 | """ | |
| 15 | for a, b in zip(A, B): | |
| 16 | if abs(a-b) > eps: | |
| 17 | print A | |
| 18 | print B | |
| 19 | return False | |
| 20 | return True | |
| 21 | ||
| 22 | def algo0(l, queries, a=0.01): | |
| 23 | """ | |
| 24 | [positive nums], [positive nums] => [positive nums] | |
| 25 | ||
| 26 | Compute exponentially weighted moving average | |
| 27 | ||
| 28 | Assumes l and queries are sorted | |
| 29 | ||
| 30 | >>> algo0([3.0,7.0,10.0,20.0,200.0], [23,68,103]) | |
| 31 | [0.03552711850193005, 0.022601837152599107, 0.015899210247751473] | |
| 32 | """ | |
| 33 | assert l == sorted(l) | |
| 34 | assert queries == sorted(queries) | |
| 35 | ||
| 36 | y = [0]*1000 | |
| 37 | for item in l: | |
| 38 | y[int(item)]=1 | |
| 39 | s = [0]*1000 | |
| 40 | for i in xrange(1000): | |
| 41 | s[i] = a*y[i-1]+(1-a)*s[i-1] | |
| 42 | ||
| 43 | return [s[q] for q in queries] | |
| 44 | ||
| 45 | def decay(t0, x, t1, a): | |
| 46 | """ | |
| 47 | (real, real, real, real) => real | |
| 48 | ||
| 49 | Exponentially decays value x at time t0 to a value x' at time t1 | |
| 50 | according to decay rate a. | |
| 51 | ||
| 52 | >>> decay(0, 0, 4, 0.01) | |
| 53 | 0.0 | |
| 54 | >>> decay(4, 0.01, 5, 0.01) | |
| 55 | 0.0099 | |
| 56 | >>> decay(4, 0.01, 6, 0.01) | |
| 57 | 0.009801 | |
| 58 | >>> decay(4, 0.01, 7, 0.01) | |
| 59 | 0.00970299 | |
| 60 | >>> decay(4, 0.01, 8, 0.01) | |
| 61 | 0.0096059601 | |
| 62 | """ | |
| 63 | - | return (1-a)**(t1-t0)*x |
| 63 | + | from math import pow |
| 64 | return pow((1-a), (t1-t0))*x | |
| 65 | ||
| 66 | def algo1(l, queries, a=0.01): | |
| 67 | """ | |
| 68 | Compute exponentially weighted moving average | |
| 69 | ||
| 70 | Assumes l and queries are sorted | |
| 71 | ||
| 72 | >>> l,queries = [3.0, 7.0, 10.0], range(11) | |
| 73 | >>> approx_eq(algo0(l, queries), algo1(l, queries), 1e-7) | |
| 74 | True | |
| 75 | >>> l, queries = [3.0,7.0,10.0,20.0,200.0], [23,68,103] | |
| 76 | >>> approx_eq(algo0(l, queries), algo1(l, queries), 1e-7) | |
| 77 | True | |
| 78 | """ | |
| 79 | assert l == sorted(l) | |
| 80 | assert queries == sorted(queries) | |
| 81 | ||
| 82 | samples = [] | |
| 83 | try: | |
| 84 | t0, x0 = (0.0, 0.0) | |
| 85 | it = iter(queries) | |
| 86 | q = it.next()-1.0 | |
| 87 | ||
| 88 | for t1 in l: | |
| 89 | # new value is decayed previous value, plus a | |
| 90 | x1 = decay(t0, x0, t1, a) + a | |
| 91 | # take care of all queries between t0 and t1 | |
| 92 | while q < t1: | |
| 93 | samples.append(decay(t0, x0, q, a)) | |
| 94 | q = it.next()-1.0 | |
| 95 | # take care of all queries equal to t1 | |
| 96 | while q == t1: | |
| 97 | samples.append(x1) | |
| 98 | q = it.next()-1.0 | |
| 99 | # update t0, x0 | |
| 100 | t0, x0 = t1, x1 | |
| 101 | ||
| 102 | # take care of any remaining queries | |
| 103 | while True: | |
| 104 | samples.append(decay(t0, x0, q, a)) | |
| 105 | q = it.next()-1.0 | |
| 106 | except StopIteration: | |
| 107 | return samples | |
| 108 | ||
| 109 | if __name__ == "__main__": | |
| 110 | import doctest | |
| 111 | doctest.testmod() |
