Using bisect in a list of tuples?

Question

I'm trying to figure out how to use bisect in a list of tuples for example

[(3, 1), (2, 2), (5, 6)]

How can I bisect this list according to the [1] in each tuple?

list_dict [(69, 8), (70, 8), ((65, 67), 6)]
tup1,tup2 (69, 8) (70, 8)
list_dict [((65, 67), 6)]
fst, snd ((65, 67),) (6,)

And I'm inserting to bisect

idx = bisect.bisect(fst, tup1[1]+tup2[1])

Which gives me unorderable types: int() < tuple()

Voorhis

Answer 1

You can separate out the values into separate lists.

from bisect import bisect

data = [(3, 1), (2, 2), (5, 6)]
fst, snd = zip(*data)
idx = bisect(fst, 2)

Note however, that for bisect to work, your data really should be ordered...

Cistaceous

This specific method doesn't wrok for me since I'm updating the tuples everytime, I'll explain in the edit – Voorhis

@Voorhis you need to make sure what you're bisecting on, and what you're working with are separate (and the bisection be of comparable types) and put them back together later if needs be... – Cistaceous

The main advantage of using bisect is linear time search. Copying the list in a linear time fashion means that you might as well do a linear search. – Dearden

Check this answer if you are using version 3.10+ https://mcmap.net/q/560111/-using-bisect-in-a-list-of-tuples – Elastomer

Answer 2

In some cases just the simple

bisect(list_of_tuples, (3, None))

will be enough.

Because None will compare less than any integer, this will give you the index of the first tuple starting with at least 3, or len(list_of_tuples) if all of them are smaller than 3. Note that list_of_tuples is sorted.

Humanitarianism

that doesn't work in Python 3. If you pass the exact number 3, you'll get TypeError: unorderable types: int() < NoneType(). BUT bisect(list_of_tuples, (3, )) would be all right. – Zoometry

Answer 3

Since version 3.10 you can pass a key to bisect methods to specify the index you want to search on - more info here:

key specifies a key function of one argument that is used to extract a comparison key from each element in the array. To support searching complex records, the key function is not applied to the x value.

import bisect
tuple_list = [(4, 117), (10, 129), (30, 197)]
# search among first indices - returns 1
bisect.bisect_left(tuple_list, 10, key=lambda i: i[0])
# search among second indices - returns 1
bisect.bisect_left(tuple_list, 129, key=lambda i: i[1])
# 2
bisect.bisect_left(tuple_list, 130, key=lambda i: i[1])

Elastomer

Answer 4

Check the bottom section of the documentation: http://docs.python.org/3/library/bisect.html. If you want to compare to something else than the element itself, you should create a separate list of so-called keys. In your case a list of ints containing only [1] of the tuple. Use that second list to compute the index with bisect. Then use that to both insert the element into the original (list of tuples) and the key ([1] of the tuple) into the new list of keys (list of ints).

Tybi

The main advantage of using bisect is linear time search. Copying the list in a linear time fashion means that you might as well do a linear search. – Dearden

@Dearden That depends on how many times you're searching. My idea here is that you maintain two data structures to work in tandem. They might as well both start empty. – Tybi

Answer 5

Answers that suggest transforming the input list are defeating the purpose of bisect by converting what should be an O(log n) into an O(n) operation. A better solution is to use a view on the input:

class _list_view:
    def __init__(self, a, key):
        self.a = a
        self.key = key

    def __getitem__(self, index):
        return self.key(self.a[index])


def bisect_left(a, x, lo=0, hi=None, key=id):
    from bisect import bisect_left
    hi = hi or len(a)
    if key == id:
        return bisect_left(a, x, lo, hi)
    return bisect_left(_list_view(a, key), x, lo, hi)

Dearden

Answer 6

I faced the same issue. I was storing list of (file_id, word_frequency) tuples and wanted to get the list sorted by second element in the tuple which is word_frequency. I did some research and found out how python compares tuples which is describe here https://howtodoinjava.com/python/compare-tuples/.

Essentially it looks at first element of two tuples and takes the smaller one. If the first elements are same then it compares second values an so on.

So what I did was exchanged the elements in tuple (word_frequency, file_id). Now I got my list sorted according to word frequency using bisect.

Hope this helps

Enfold