StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>@Winston Ewert 's <code>future8</code> method is O(n) (!), and is better than all of our previous proposals here. To prove it's O(n), observe that the inner <code>while</code> loop is executed at most once for any value of <code>B[target]</code>.</p> <p>My old answer:</p> <p>Here is a benchmark of three approaches (after a ping pong between @Winston Ewert and me): </p> <ol> <li>Ascending list with binary search. (future2)</li> <li>Full list (future6, by @Winston Ewert)</li> <li>numpy.vectorize (future7, an enhanced version of @Winston Ewert 's future5).</li> </ol> <p>Each of these is significantly faster than the others under different conditions. If the series is random, then "full list" (future6) is fastest. If the series oscillates, then "ascending list" (future2) is fastest. If the series tends to ascend, then vectorize (future7) is fastest.</p> <p>If the data is stock quotes, I would go with "vectorize" (future7), because stocks have an ascending trend, and because it's simple and performs reasonably under all conditions.</p> <p>Output:</p> <pre><code>Random series: future2 ascends : 0.210215095646 future6 full list: 0.0920153693145 future7 vectorize: 0.138747922771 Oscillating series: future2 ascends : 0.208349650159 future6 full list: 0.940276050999 future7 vectorize: 0.597290143496 Ascending trend series: future2 ascends : 0.131106233627 future6 full list: 20.7201531342 future7 vectorize: 0.0540951244451 </code></pre> <p>Code:</p> <pre><code>import numpy as np import time import timeit def future2(A): def reverse_enum(L): for index in reversed(xrange(len(L))): yield len(L)-index-1, L[index] def findnext(x, A, ascends): # find index of first future number greater than x for idx, segment in reverse_enum(ascends): joff=A[segment[0]:segment[1]+1].searchsorted(x,side='right') # binary search if joff < (segment[1]-segment[0]+1): j=segment[0]+joff [ascends.pop() for _ in range(idx)] # delete previous segments segment[0]=j # cut beginning of segment return j return -1 B = np.arange(len(A))+1 # Note: B[i]=-1 where there is no greater value in the future. B[-1] = -1 # put -1 at the end ascends = [] # a list of pairs of indexes, ascending segments of A maximum = True for i in xrange(len(A)-2,-1,-1): # scan backwards #print(ascends) if A[i] < A[i+1]: if maximum: ascends.append([i+1,i+1]) maximum = False else: ascends[-1][0] = i+1 else:# A[i] >= A[i+1] B[i] = findnext(A[i], A, ascends) maximum = True return B def future6(A): # list of tuples (index into A, value in A) # invariant: indexes and values in sorted order known = [] result = [] for idx in xrange(len(A) - 1, -1, -1): value = A[idx] # since known is sorted a binary search could be applied here # I haven't bothered # anything lower then the current value # cannot possibly be used again, since this value will be first index instead # of those known = [(x,y) for x,y in known if y > value] if known: # all values in known are > current value # they reverse sorted by index # the value with the lowest index is first result.append(known[-1][0]) else: # no values exist this high, report -1 result.append(-1) # add to end of the list to maintain invariant known.append( (idx, value) ) # let numpy worry about reversing the array return np.array(result)[::-1] def future7(A): @np.vectorize def values(i): for idx, v in enumerate(A[i+1:]): # loop is faster than genexp with exception if A[i]<v: return idx+i+1 return -1 return values(np.arange(len(A))) if __name__ == '__main__': print('Random series:') tsetup = """import future; import numpy; A = numpy.random.random(1e4)""" t = timeit.timeit('future.future2(A)', tsetup, number=3) print('future2 ascends : '+str(t)) t = timeit.timeit('future.future6(A)', tsetup, number=3) print('future6 full list: '+str(t)) t = timeit.timeit('future.future7(A)', tsetup, number=3) print('future7 vectorize: '+str(t)) print('Oscillating series:') tsetup = """import future; import numpy; A = numpy.random.randint(1e5,size=1e4)-5e4; A = A.cumsum()""" t = timeit.timeit('future.future2(A)', tsetup, number=3) print('future2 ascends : '+str(t)) t = timeit.timeit('future.future6(A)', tsetup, number=3) print('future6 full list: '+str(t)) t = timeit.timeit('future.future7(A)', tsetup, number=3) print('future7 vectorize: '+str(t)) print('Ascending trend series:') tsetup = """import future; import numpy; A = numpy.random.randint(1e5,size=1e4)-3e4; A = A.cumsum()""" t = timeit.timeit('future.future2(A)', tsetup, number=3) print('future2 ascends : '+str(t)) t = timeit.timeit('future.future6(A)', tsetup, number=3) print('future6 full list: '+str(t)) t = timeit.timeit('future.future7(A)', tsetup, number=3) print('future7 vectorize: '+str(t)) </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload