在Python中搜索对象列表

Question

我有一个包含多个物品（Item）对象的列表，每个物品都有一个日期属性。同时，我从数据库中获取了一个单独的日期。

我想在这个列表中查找所有日期晚于我从数据库获取的日期的物品。

我的物品列表里有上千个对象，所以我希望能尽可能高效地完成这个任务。

我觉得逐个遍历列表中的每个物品，检查它们的日期是否晚于我从数据库得到的日期，这样做可能不是最有效的方法。

class Item(object):    
    def __init__(self, title, link, description, date):
        self.title = title
        self.link = link
        self.description = description
        self.date = date

item_list = [] 
...
#assume I populate the list with a 1,000 Item objects

filtered_list = []
for it in item_list:
    if date_from_db > it.date:
        filtered_list.append(it)

Answer 1

针对有人说这个列表生成式让人困惑，我想分享一种更清晰的格式。我最近经常用这个。

filtered_list = [item                         # What we're collecting
                 for item in item_list        # What we're collecting it over 
                 if date_from_db < item.date] # the conditions

虽然这样会把原本可以用一行代码写成的内容变成三行，就像普通的for循环那样，但在很多情况下，甚至在这里，它都能提高可读性，同时还能让你享受到更高的效率。

Answer 2

要避免逐个检查列表中的每个项目，最简单的方法是先按日期排序，然后从后往前查找，直到找到一个比目标日期大的最后一个项目，然后把它们一个个加到你的 filtered_list 里。

或者，你也可以把列表按降序排序，然后从前往后查找，直到找到第一个比目标日期大的项目。这样你就可以轻松地修改你的循环，像这样：

filtered_list = [] 
for it in item_list: 
    if date_from_db > it.date: 
        filtered_list.append(it) 
    else:
        break

另外，如果你预计过滤后的列表会有很多项目，使用 二分查找 来找到第一个符合条件的项目可能会更快，然后用列表切片把它复制到 filtered_list 中：

first = binary_search(item_list, lambda it: cmp(date_from_db, it.date))
if first == -1:
    return []
return item_list[first:]

这里有一个我从上面链接中改编的二分查找函数。我相信它应该能正常工作：

def binary_search(a, comp, lo=0, hi=None): 
    if hi is None: 
        hi = len(a) 
    while lo < hi: 
        mid = (lo+hi)//2 
        cmpval = comp(a[mid])
        if cmpval < 0:
            lo = mid+1 
        elif cmpval > 0:
            hi = mid 
        else: 
            return mid 
    return -1 

Answer 3

列表推导是一种相对高效的方法，可以在不使用数据库的情况下完成这个任务：

[it for it in item_list if date_from_db > it.date]

另外，你也可以使用内置的 filter 函数：

filter(lambda it: it if date_from_db > it.date, item_list)