CODEWITHSUNDEEP
pythonlistpython-3.xbinary-search
Ollu_
Ollu_

Reputation: 126

bisect_left on first item of list within list, Python 3

I have a list like this for example:

L = [(0, "test", "value"), (0, "test2", "value2")]

and I need to = bisect_left the first item of each tuple to find an index in the list. However, I can't think of a way of doing this without creating a list of all of these first items before hand:

exampleList = [L[i][0] for i in range(len(L))]

any ideas on another way to do this as it works but when my list gets to 5000 items long it is very slow and I need a faster way of doing it?

Upvotes: 3

Views: 1744

Answers (3)

Midhilesh Momidi
Midhilesh Momidi

Reputation: 575

L = [(0, "test1", "value1"), (1, "test2", "value2"), (3, "test3", "value3")]

From Python 3.10

print(bisect_left(L, 4, key = itemgetter(0))) # output : 3

For below Python 3.10 another way is to use zip function

a, _, _ = zip(*L)

print(bisect_left(a, 2)) # output : 2
print(bisect_left(a, 4)) # output : 3

Upvotes: 0

wim
wim

Reputation: 362547

Python has a builtin bisect_left, you can use it. You don't need to build the whole intermediate list, you just need a lazy object that retrieves the first item from the tuple at that position.

Something simple like:

class Proxy(object):
    def __getitem__(self, item):
        return L[item][0]

Beginning with Python 3.10's bisect you can use a key function for the search, so a wrapper is no longer required. In your case it would be key=operator.itemgetter(0).

Upvotes: 6

Joran Beasley
Joran Beasley

Reputation: 113940

import bisect
L = [(0, "test", "value"), (1, "test2", "value2"),(3,"test3","value3")]
print (bisect.bisect_left(L,(2,)))

python deals with tuple comparisons great... just pass it (2,"asd","dsa") or even just (2,) (or whatever your index location item you are trying to find)

or you could pass it (0,"asd","value") and it would know to put it to the left of the other (0,"test","value") item tuple ... or (0,"zzzz","value") and it would know to put it to the right of that item

Upvotes: 3

Related Questions