Блог

Краткая версия вопроса:

При сравнении словаря, для которого ключи являются целыми числами в диапазоне (n), и списка длины n, какие ключевые моменты реализации для выбора между одним или другим? Что-то вроде «если вы много чего делаете со своим объектом, то словарь лучше».

Длинная версия вопроса

Я не уверен, что следующие детали моей реализации имеют значение для вопроса… Итак, вот оно. Пытаясь сделать свой код немного более питоническим, я реализовал подкласс UserList, который принимает в качестве индекса как целое число, так и список, представляющий целое число в базе l.

 from collections import UserList

class MyList(UserList):
    """
    A list that can be accessed both by a g-tuple of coefficients in range(l)
    or the corresponding integer.
    """
    def __init__(self, data=None, l=2, g=None):
        self.l = l
        if data == None:
            if g == None:
                raise ValueError
            self.data = [0]*(l**g)
        else:
            self.data = data
        
    def __setitem__(self, key, value):
        if isinstance(key, int):
            self.data[key] = value
        else:
            self.data[self.idx(key)] = value

    def __getitem__(self, key):
        if isinstance(key, int):
            return self.data[key]
        return self.data[self.idx(key)]

    def idx(self, key):
        l = self.l
        idx = 0
        for i, value in enumerate(key):
            idx  = value*l**i
        return idx
  

Который можно использовать следующим образом:

 L = MyList(l=4, g=2) #creates a list of length 4**2 initialized at zero
L[9] = 'Hello World'
L[9] == L[1,2]
  

Я обобщил этот класс, чтобы он также принимал l значение кортежа баз (давайте назовем этот обобщенный класс MyListTuple ), но код находится в SageMath, поэтому я не очень хочу переводить его и на чистый python, но он отлично работает.

Это выглядело бы примерно так:

 L = MyListTuple(l=[2,4], g=2) #creates a list of length 2^2*4^2 initialized at zero
L[0,9] = 'Hello World'
L[0,9] == L[[0,0],[1,2]]
  

Следующая часть, которую я хочу улучшить, в настоящее время я использую словарь, ключи которого представляют собой кортежи целых чисел (поэтому вы могли бы обращаться к нему как d[9,13,0] ), но я хочу также иметь возможность использовать в качестве (эквивалентных) списков ключей, представляющих целое число в базе l, как указано выше (так что для l = 4 это было бы d[[1,2], [1,3], [0,0]] ).

Это очень похоже на то, что я делал в MyListTuple , но в этом случае многие ключи никогда не используются.

Итак, мой вопрос: как выбрать между созданием подкласса UserDict, который эквивалентен MyListTuple при обработке данного ключа, или просто использовать MyListTuple, даже если в большинстве случаев большинство записей никогда не будут использоваться? Или, как я сформулировал это выше, на какие детали в использовании этой структуры я должен обратить внимание, чтобы выбрать между ними? (что-то вроде «если вы много чего делаете со своим объектом, то словарь лучше»)

(Попытаемся обратиться только к общей части «список против dict».
Отнеситесь к этому с недоверием; от пользователя, а не от разработчика.
Это не настоящий ответ, скорее большой комментарий.)

Список (возможно, двусвязный список) должен обеспечивать эффективную
вставку и удаление в любом месте (только изменяя указатели на
следующие / предыдущие элементы, O (1)).
Поиск будет неэффективным (как O (n) — проверить все элементы-,
так и промахи в кэше * — неверная локализация ссылки-).
(*по сравнению с элементами, хранящимися последовательно в памяти (например, numpy.array)).

Dict (своего рода хэш-карта) теоретически должен обеспечивать
эффективный поиск, вставки и удаления (амортизированный O (1));
но это может зависеть от качества хэш-функции,
размера корзины, шаблонов использования и т.д. (Я недостаточно знаю).

Последовательное перебирание всех элементов будет неэффективным
для обоих, из-за промахов кэша / неправильного расположения ссылок
(следование указателям вместо последовательного доступа к памяти).

Насколько я знаю:
Вы бы использовали списки как изменяемые последовательности (когда вам нужно
перебирать все элементы) в Python из-за отсутствия лучшей
альтернативы (массивы C, C std::array / std:: vector / и т.д.).
Вы бы использовали dicts для быстрого поиска на основе ключей,
когда поиск важнее / чаще, чем вставка / удаление.