Patrick Thunstrom wrote: >>>> The generalized problem: >>>> >>>> L = [V0, V1, ..., Vn], where V0 >= V1 >= V2 >= ... >= Vn . >>>> Find index i, such that V[i] >= Vt >= V[i + 1], where Vt is the test >>>> value being searched for. I need to know the indices i and i + 1, >>>> which I need to interpolate based on where Vt falls. >>>> >>>> The solution (As a sublist, S) I worked out tonight after >>>> experimenting with comprehension syntax is: >>>> S = [i for i, V in enumerate(L) if L[i] >= Vt >= L[i + 1]] >>>> >>>> And, of course, the index i I need is: >>>> i = S[0] >>>> >>>> I tested this out with concrete examples in the interpreter, such as >>>> with a list, L: >>>> >>>> L = [item for item in range(10000, 0, -1)] >>>> >>>> and trying different test values. It was blazingly fast, too! >>>> >>>> All I can say is: WOW!!! >> >> By the way, if you were to use a plain old loop the expected speedup over >> the listcomp would be 2. You can break out of the loop when you have >> found the gap, after iterating over one half of the list on average. >> >> So for-loops are twice as amazing ;) > > For the same basic speed up, a generator expression with a call to > next() will produce similar results. Without the additional code to > get the indexed item. > > index = (i for i, _ in enumerate(original_list) if original_list[i] >= > target >= original_list[i + 1]).next() > > The only catch is it raises a StopIteration exception if no element > fits the test.
In new code you shouldn't call the next() method (renamed __next__() in Python 3) explicitly. Use the next() builtin instead which also allows you to provide a default: >>> exhausted = iter(()) >>> next(exhausted) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration >>> next(exhausted, "default_value") 'default_value' That said, rather than polishing the implementation of the inferior algorithm pick the better one. Ceterum censeo bisect is the way to go here ;) _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
