Python:搜索元组的排序列表 [英] Python: Search a sorted list of tuples

问题描述

有用的信息:

有关如何对各种数据类型的列表进行排序的信息，请参见:如何对列表/元组进行排序(列表/元组)?

..以及有关如何在排序列表上执行二进制搜索的信息，请参见: Binary在Python中搜索(二等分)

我的问题:

如何将二进制搜索(或其他log(n)搜索算法)巧妙地应用于某些数据类型的列表，而键是数据类型本身的内部组成部分?为了使问题简单，我们可以使用元组列表作为示例:

  x = [("a"，1)，("b"，2)，("c"，3)]binary_search(x，"b")#搜索"b"，应返回1#注意我们如何不搜索("b"，2)，但无论如何我们要返回("b"，2) 

为了进一步简化:我们只需要返回一个搜索结果，如果同时存在("b"，2)和("b"，3)，则无需返回多个搜索结果.

更好:

我们如何修改以下简单代码来执行上述操作?

从bisect导入

  bisect_leftdef binary_search(a，x，lo = 0，hi = None):#不能使用a为hi指定默认值hi = hi，如果hi不为其他，则为len(a)#hi默认为len(a)pos = bisect_left(a，x，lo，hi)#查找插入位置return(pos如果pos！= hi和a [pos] == x else -1)#不要走到尽头 

请注意:我不是寻找完整的算法本身.相反，我正在寻找Python的某些标准库的应用程序和/或Python的其他功能，以便可以随时轻松搜索一些任意数据类型的排序列表.

谢谢

解决方案

利用词典顺序如何处理不等长的元组:

 #bisect_right也可以索引= bisect.bisect_left(x，('b'，)) 

有时将自定义序列类型提供给 bisect :

  class KeyList(object):#bisect不接受键函数，因此我们将键构建到序列中.def __init __(self，l，key):self.l = lself.key =键def __len __(自己):返回len(self.l)def __getitem __(self，index):返回self.key(self.l [index])进口经营者#bisect_right对此*不起作用.索引= bisect.bisect_left(KeyList(x，operator.itemgetter(0))，'b') 

Useful information:

For information on how to sort a list of various data types see: How to sort (list/tuple) of lists/tuples?

.. and for information on how to perform a binary search on a sorted list see: Binary search (bisection) in Python

My question:

How can you neatly apply binary search (or another log(n) search algorithm) to a list of some data type, where the key is a inner-component of the data type itself? To keep the question simple we can use a list of tuples as an example:

x = [("a", 1), ("b",2), ("c",3)]
binary_search(x, "b") # search for "b", should return 1
# note how we are NOT searching for ("b",2) yet we want ("b",2) returned anyways

To simplify even further: we only need to return a single search result, not multiple if for example ("b",2) and ("b",3) both existed.

Better yet:

How can we modify the following simple code to perform the above operation?

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):  # can't use a to specify default for hi
    hi = hi if hi is not None else len(a)  # hi defaults to len(a)   
    pos = bisect_left(a, x, lo, hi)  # find insertion position
    return (pos if pos != hi and a[pos] == x else -1)  # don't walk off the end

PLEASE NOTE: I am not looking for the complete algorithm itself. Rather, I am looking for the application of some of Python's standard(ish) libraries, and/or Python's other functionalities so that I can easily search a sorted list of some arbitrary data type at any time.

Thanks

解决方案

Take advantage of how lexicographic ordering deals with tuples of unequal length:

# bisect_right would also work
index = bisect.bisect_left(x, ('b',))

It may sometimes be convenient to feed a custom sequence type to bisect:

class KeyList(object):
    # bisect doesn't accept a key function, so we build the key into our sequence.
    def __init__(self, l, key):
        self.l = l
        self.key = key
    def __len__(self):
        return len(self.l)
    def __getitem__(self, index):
        return self.key(self.l[index])

import operator
# bisect_right would *not* work for this one.
index = bisect.bisect_left(KeyList(x, operator.itemgetter(0)), 'b')

这篇关于Python:搜索元组的排序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！