1

I have a sorted list of tuples of the form

x = 
[(0,1), (0,2), (0,3), ... 
 (1,1), (1,3), (1,4), ...
 ...
 (n,0), (n,4), ...
]

I want to slice the list such that all numbers of (x,y) where x is a certain value in the new list and the order is kept. Now, this would obviously work:

y = [(a,b) for (a,b) in x if a == n]

But it is really slow. It would be faster to find the first and last index that satisfies this condition with binary search. index gives you the first index for a value, and index of the reversed list would give the last index. How would apply it though without doing [a for (a,b) in x] and copying the whole list, in a pythonic way?

kmario23
  • 57,311
  • 13
  • 161
  • 150
Joachim
  • 3,210
  • 4
  • 28
  • 43
  • As it cannot assume an _ordered_ list, `index` probably doesn't do a binary search, but a list traversal, so I doubt that'd be much faster. – das-g Mar 27 '16 at 22:10
  • 2
    Consider using [bisect](https://docs.python.org/3/library/bisect.html#searching-sorted-lists), the preferred way to handle sorted lists. – Akshat Mahajan Mar 27 '16 at 22:15
  • As for accessing the subrange (slice) within your list once you know begin and end position: See http://stackoverflow.com/questions/509211/explain-pythons-slice-notation or even just https://docs.python.org/2/tutorial/introduction.html#strings – das-g Mar 27 '16 at 22:20

1 Answers1

2

As suggested in the comments by @Liongold, you can use bisect. Assuming you want all tuples t with t[0] == 1:

from bisect import bisect_left

x = [(0, 1), (0, 2), (1, 1), (1, 2), (2, 1), (2, 2)]

start = bisect_left(x, (1, None))  # index of the very first (1, i) 
end = bisect_left(x, (2, None))  # index after the very last (1, i)

y = x[start:end]

# y: [(1, 1), (1, 2)]

You can find details in the bisect docs.

user2390182
  • 72,016
  • 6
  • 67
  • 89
  • What if I can't assume that 2 is in the list? – Joachim Mar 27 '16 at 22:26
  • 1
    `bisect_left(x, (2, None)` will return the insertion point of the provided element. Since `None < i` for any integer `i`, this should always return the exact index after the last `(1, i)`. This can be `len(x)` if necessary – user2390182 Mar 27 '16 at 22:30