Python я должен использовать генератор для этого случая?

Question

У меня есть список из почти 2 тыс. Словарей. И я использую список несколько раз. Например:

c = myClass()
c.create(source) # where source is a text of approximately 50k chars
                 # this method creates the list that has approximately 2k dictionaries
item = c.get(15012) # now, this one loops thru the list to find an item
                    # whenever the condition is matched, the for loop is broken and the value is returned
item2 = c.prevItem(item) # this one also loops thru the list by reversing it and bringing the next item

Теперь представьте себе сценарий, в котором я снова и снова использую один и тот же список. Поскольку список большой, я бы хотел использовать генератор, но, насколько я понял, генераторы должны быть воссозданы, когда они генерируют StopIteration. Таким образом, в данном случае удобно использовать генератор или есть более эффективный способ с точки зрения скорости?

Answer 1

Мне кажется, что вы должны решить, что вам лучше сделать:

1) Сохраните значения, чтобы вам не приходилось пересчитывать их, но используйте для этого больше места.

2) Каждый раз пересчитывайте их, но экономьте место, потому что вам не нужно их хранить.

Если вы думаете об этом, неважно, какой генератор / список / кем бы вы нииспользуя, одна из этих двух вещей должна произойти.И я не думаю, что есть простое жесткое правило, чтобы сказать, что лучше.(Лично я бы сказал, выбери один и не оглядывайся назад. У тебя вся жизнь впереди.)

Answer 2

Если вы часто получаете элемент с известным смещением от ранее извлеченного элемента, нужно изменить .get, чтобы вернуть не только элемент, но и его позицию в списке. Тогда вы можете реализовать prevItem как:

def previtem(self, pos):
    return self.itemlist[pos - 1]

item, pos = c.get(itemnum)
item2 = c.prevItem(pos)

Если вместо этого вы выполняете какую-то операцию с item для получения нового itemnum, вы должны хранить их в dict вместо list. Таким образом, get - это просто поиск по словарю (намного быстрее, чем поиск по списку):

def get(self, itemnum):
    return self.premade_dict[itemnum]

Таким образом, так или иначе вы сможете заменить некоторые поиски более дешевыми операциями.

Answer 3

Вы можете попробовать этот подкласс OrderedDict. Мое предыдущее представление было неверным (упомянуто внизу):

from collections import OrderedDict

class MyOrderedDict(OrderedDict):
    def index(self, key):
        if key not in self.keys():
            raise KeyError
        return list(d.keys()).index(key)
    def prev(self, key):
        idx = self.index(key) - 1
        if idx < 0:
            raise IndexError
        return list(d.keys())[idx]
    def next(self, key):
        _list = list(d.keys())
        idx = self.index(key)
        if idx > len(_list):
            raise IndexError
        return _list[idx+1]

# >>> d = MyOrderedDict(((3, 'Three'), (2, 'Two'), (4, 'Four'), (1, 'One')))
# >>> d.index(3)
# 0
# >>> d.index(2)
# 1
# >>> d.prev(2)
# 3
# >>> d.prev(3)
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
#   File "<stdin>", line 9, in prev
# IndexError
# >>> d.next(4)
# 1
# >>> d.next(1)
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
#   File "<stdin>", line 16, in next
# IndexError: list index out of range

---

Редактировать - как @agf прокомментировал ниже, это неверно.

Вы ищете быстрый способ получить элемент из myClass, поэтому вы должны использовать словарь. Но в то же время вы хотите, чтобы данные были в некотором порядке, чтобы вы могли сделать prevItem для них. Почему бы вам не сохранить свои данные в collections.OrderedDict, добавленном в Python 2.7, 3.1. ref

Answer 4

Список из двух тысяч словарей вполне нормален. Думаю, у типичного администратора сайта есть много таких списков Если вам редко приходится сталкиваться с подобными проблемами, возможно, вам подойдет специальное решение - возможно, стоит рассмотреть и словарь словарей, чтобы вам не приходилось каждый раз перебирать каждый ключ. Но более обычный способ решения этой структуры данных, из того, что я собираю, состоит в использовании базы данных. Каждый из ваших словарей может иметь некоторый ключ (в идеале условие, которое вы проверяете в цикле). База данных может быть проинструктирована индексировать данные по этому ключу, и если вы посмотрите на работу, которую она выполняет для извлечения нужного словаря, вы можете быть удивлены, обнаружив, что ответ почти отсутствует - она ​​в значительной степени просто сокращает колоду до карта, которую вы запросили, так сказать (хотя для настройки индекса нужно проделать некоторую работу, что-то вроде операции сортировки).

Python предлагает множество отличных способов сопоставить код с базами данных всех видов. Познакомьтесь с мощным, но сложным sqlalchemy, встроенным модулем std library sqlite3, или присоединяйтесь ко мне в экспериментах с базами данных mongoengine и nosql. (Конечно, есть и много других, но вы можете легко найти другой пост здесь с общим обзором). Удачи.

Answer 5

Зависит от того, как вы хотите использовать генератор.Генераторы способны выполнять код только тогда, когда он действительно необходим.Кажется, ваш цикл for с break уже делает это.

Вы можете изменить интерфейс вашего класса, хотя.

def getItems(cond):
    # find item, remember index
    yield item
    # find previous item, possibly much more efficient with the index
    yield previtem

Теперь, после вызова getItems (), вы можете обойти возвращаемый генератор в течение 1 или 2элементов и только столько кода, сколько необходимо.

Answer 6

Вы должны использовать список, потому что вы можете выполнить с ним одну тривиальную оптимизацию: отсортируйте его по атрибуту, который вы ищете (в .get), и выполните бинарный поиск.На 2000 пунктов среднее количество сравнений снижается с 1000 до 10!Получение предыдущего (и следующего) элемента тоже становится тривиальным.

См. модуль деления пополам для алгоритма деления пополам.