在大型 Python 列表中高效搜索自定义对象

Question

我有一个自定义 Python 对象列表，需要在该列表中搜索特定对象的存在。我担心的是搜索大型列表对性能的影响，尤其是频繁搜索。

这是一个使用带有属性名称和年龄的自定义 Person 类的简化示例：

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

people = [Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35)]

目前，我正在使用列表理解和 any() 函数来检查列表中是否存在具有特定姓名和年龄的人：

if any(p.name == "Bob" and p.age == 25 for p in people):
    print("The person exists.")

是否有更有效的方法来搜索大型 Python 列表中特定自定义对象的存在？

Answer 1

如果您要过滤的字段很少，那么您可以先创建这些字段的哈希集。然后在列表迭代的情况下知道一个名为“bob”的人是否存在是 O(1) 而不是 O(n)

Answer 2

提高在大型 Python 列表中搜索特定对象的性能的一种方法是使用字典而不是列表。这种方法涉及创建一个字典，其中键是您要搜索的属性，值是对象本身。

这是一个如何将此方法应用于您的 Person 类的示例：

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

people = [Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35)]

people_dict = {}
for person in people:
    people_dict[(person.name, person.age)] = person

if ("Bob", 25) in people_dict:
    print("The person exists.")

Answer 3

我的意思是从技术上讲，如果为它设置了相等检查，你可以创建你正在寻找的

Person

对象，然后看看它是否在列表中。

people = [Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35)]

if Person("Bob", 25) in people:
    print("The person exists.")

仅当您在条件中使用的

Person

对象和列表中的

Person

对象评估为同一对象时，这才有效。所以这个解决方案可能适合也可能不适合你。

您也可以通过使用集合而不是@RandomGuy 评论中所述的列表来获得性能。

编辑：

如果你想要更合适的搜索，你可以使用集合或字典：

people_set = {(p.name, p.age) for p in people}
people_dict = {(p.name, p.age): p for p in people}

if ("Bob", 25) in people_set:
    print("Exists")

bob = people_dict[("Bob", 25)]

Answer 4

如果我们在你的类中实现了几个 dunder 方法，我们就可以使用一个集合如下：

class Person:
    def __init__(self, name, age):
        self._name = name
        self._age = age
    def _key(self):
        return self._name, self._age
    def __hash__(self):
        return hash(self._key())
    def __eq__(self, other):
        return isinstance(other, type(self)) and self._key() == other._key()

_set = {Person('Andy', age) for age in range(18, 100)}

print(Person('Andy', 55) in _set)

输出：

True

Answer 5

如果您的

Person()

类是不可变的，您可以使用冻结的数据类和集合：

from dataclasses import dataclass


@dataclass(frozen=True)
class Person:
    name: str
    age: int


people = {Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35), Person("Mary", 47)}

print(people)
>>> {Person(name='Bob', age=25), Person(name='Charlie', age=35), Person(name='Alice', age=30), Person(name='Mary', age=47)}

print(f'{Person("Bob", 25) in people=}')
>>> Person("Bob", 25) in people=True

print(f'{Person("Mary", 44) in people=}')
>>> Person("Mary", 44) in people=False

但是你不能改变它们：

p = people.pop()
print(p)
>>> Person(name='Mary', age=47)

p.age = "99"
dataclasses.FrozenInstanceError: cannot assign to field 'age'