Список Python, имя объекта поиска, советы по эффективности - PullRequest
Новая
       4

Список Python, имя объекта поиска, советы по эффективности

3 голосов
/ 24 июля 2010

Предположим, у меня есть следующий объект: 

class Foo(object):
  def __init__(self, name=None):
    self.name = name

  def __repr__(self):
    return self.name

И список, содержащий несколько экземпляров, например: 

list = [Foo(name='alice'), Foo(name='bob'), Foo(name='charlie')]

Если я хочу найти объект с заданным именем, я мог бы использовать следующее: 

def get_by_name(name, list):
  return [foo for foo in list if foo.name == name][-1]

Что, очевидно, означало бы: 

print get_by_name('alice', list)
>> alice

Однако существует ли более эффективная структура данных или метод для извлечения таких объектов? В действительности имена объектов известны только во время выполнения и теоретически могут меняться на протяжении всего жизненного цикла объекта.

Любой совет?

UPDATE:

Благодаря ответу Matt Joiners я обновил его для поддержки нескольких Foo с тем же именем: 

class Foo(object):
    _all_names = {}    
    def __init__(self, name=None):
        self._name = None
        self.name = name        
    @property
    def name(self):
        return self._name        
    @name.setter
    def name(self, name):
        if self._name is not None:
            self._all_names[self._name].remove(self)
        self._name = name
        if name is not None:
            self._all_names.setdefault(name, []).append(self)
    @classmethod
    def get_by_name(cls, name):
        return cls._all_names[name]        
    def __repr__(self):
        return "{0}".format(self.name)

l = [Foo("alice"), Foo("bob"), Foo('alice'), Foo('charlie')]
print Foo.get_by_name("alice")
print Foo.get_by_name("charlie")

Есть какие-нибудь комментарии по этому подходу?

Ответы [ 2 ]

8 голосов
/ 24 июля 2010

Попробуйте это для размера: 

class Foo(object):
    _all_names = {}
    def __init__(self, name=None):
        self.name = name
    @property
    def name(self):
        return self._name
    @name.setter
    def name(self, name):
        self._name = name
        self._all_names[name] = self
    @classmethod
    def get_by_name(cls, name):
        return cls._all_names[name]
    def __str__(self):
        return "Foo({0})".format(self.name)

a = Foo("alice")
b = Foo("bob")
print Foo.get_by_name("alice")

Имейте в виду, что оно минимально, чтобы передать идею, есть много настроек и проверок, которые вы можете сделать здесь и там.

1 голос
/ 24 июля 2010

Ситуация немного запутанная.

Вы будете искать этот объект в списке , который представляет собой линейную структуру данных. Единственный способ найти что-то - пройти по одному. Это заставляет время расти линейно с длиной списка. Итак, , что - вот где ваша проблема скорости.

Способ получения некоторого прироста скорости заключается в использовании некоторой схемы хеширования для прямой индексации объектов по ключу, который вас интересует (в вашем случае, name). Это позволит вам искать объект аналогично поиску по словарю. Это операция с постоянным временем. Это в основном то, что делает ответ Мэтта. Он хранит «индекс» как структуру уровня класса, чтобы вы могли искать вещи, используя хеширование, а не обходя список.

...