Оптимизированный словарь Python / хранилище отрицательных индексов

Question

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

У меня ситуация примерно такая:

someDict = {}
someDict[(-2, -2)] = something
somedict[(3, -10)] = something else

Я храню ключи координат для объектов, которые действуют как массивы плиток в игре.В какой-то момент они будут отрицательными, поэтому я не могу использовать список или какой-то редкий массив (я думаю, что это термин?).

Могу ли я:

• Ускорить поиск по словарю, так что это не будет проблемой
• Найти какой-нибудь контейнер, который будет поддерживать разреженные, отрицательные индексы?

Я бы использовал список, но потомзапрос будет идти от O (log n) к O (n), чтобы найти область в (x, y).(Я думаю, что у меня тоже нет времени).

Answer 1

Словари Python очень очень быстрые, и использование кортежа целых чисел не будет проблемой.Однако в вашем случае использования кажется, что иногда вам нужно выполнить однокоординатную проверку, и, конечно, медленно обходить все данные.

Вместо линейного поиска вы, тем не менее, можете ускорить структуру данных длявам нужен доступ с помощью трех словарей:

class Grid(object):
    def __init__(self):
        self.data = {}  # (i, j) -> data
        self.cols = {}  # i -> set of j
        self.rows = {}  # j -> set of i

    def __getitem__(self, ij):
        return self.data[ij]

    def __setitem__(self, ij, value):
        i, j = ij
        self.data[ij] = value
        try:
            self.cols[i].add(j)
        except KeyError:
            self.cols[i] = set([j])
        try:
            self.rows[j].add(i)
        except KeyError:
            self.rows[j] = add([i])

    def getRow(self, i):
        return [(i, j, data[(i, j)])
                for j in self.cols.get(i, [])]

    def getCol(self, j):
        return [(i, j, data[(i, j)])
                for i in self.rows.get(j, [])]

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

Answer 2

Для начала с

Ускорить поиск по словарю, так что это не будет проблемой

Поиск по словарю довольно быстрый O (1), но (сВаш другой вопрос) вы не полагаетесь на поиск по хэш-таблице в словаре, вы полагаетесь на линейный поиск ключей словаря.

Найдите какой-то контейнер, который будет поддерживать разреженный, отрицательныйиндексы?

Это не индексируется в словаре.Кортеж является неизменным объектом, и вы хэшируете кортеж в целом.Словарь действительно не имеет представления о содержимом ключей, только их хэш.

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

Например, вы можете создавать объекты, которые инкапсулируют нужные вам данные, и упорядочивать их в двоичном дереве для поиска O (n lg n).Вы даже можете зайти так далеко, чтобы обернуть все это в класс, который даст вам красивый синтаксис if foo in Bar:, который вы ищете.

Вам, вероятно, нужна пара скоординированных структур, чтобы выполнить то, что вы хотите.Вот упрощенный пример с использованием диктов и наборов (немного подправив предложение пользователя 6502.)

# this will be your dict that holds all the data
matrix = {}
# and each of these will be a dict of sets, pointing to coordinates
cols = {}
rows = {}

def add_data(coord, data)
    matrix[coord] = data
    try:
        cols[coord[0]].add(coord)
    except KeyError:
        # wrap coords in a list to prevent set() from iterating over it
        cols[coord[0]] = set([coord])
    try:
        rows[coord[1]].add(coord)
    except KeyError:
        rows[coord[1]] = set([coord])

# now you can find all coordinates from a row or column quickly
>>> add_data((2, 7), "foo4")
>>> add_data((2, 5), "foo3")
>>> 2 in cols
True
>>> 5 in rows
True
>>> [matrix[coord] for coord in cols[2]]
['foo4', 'foo3']

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

Answer 3

Поиск в словаре очень быстро.Поиск части ключа (например, всех плиток в строке x) - это не быстрый процесс.Вы могли бы использовать диктовку диктов.Вместо того, чтобы указывать отдельный двукратный индекс, состоящий из 2-х кортежей, используйте вложенные диктовки, например:

somedict = {0: {}, 1:{}}
somedict[0][-5] = "thingy"
somedict[1][4] = "bing"

Тогда, если вы хотите, чтобы все плитки в данной «строке» были просто somedict[0].

Вам понадобится некоторая логика для добавления вторичных словарей, где это необходимо, и так далее.Подсказка: отметьте getitem() и setdefault() для стандартного типа dict или, возможно, типа collections.defaultdict.

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

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

Answer 4

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

например. если ваши индексы смежны так:

...
-2 -> a
-1 -> c
0 -> d
1 -> e
2 -> f
...

Просто сделайте что-то вроде LookupArray [Index + MinimumIndex], где MinimumIndex - это абсолютное значение наименьшего индекса, который вы будете использовать.

Таким образом, если бы ваш минимум был, скажем, -50, он соответствовал бы 0. -20 означал бы к 30 и т. Д.

Edit:

Альтернативой может быть использование хитрости с тем, как вы используете индексы. Определите следующую ключевую функцию

Key(n) = 2 * n (n >= 0)
Key(n) = -2 * n - 1. (n < 0)

Это сопоставляет все положительные ключи с положительными четными индексами и все отрицательные элементы с положительными нечетными индексами. Это может быть непрактично, поскольку, если вы добавите 100 отрицательных ключей, вам придется расширить свой массив на 200.

Еще одна вещь, на которую следует обратить внимание: если вы планируете осуществлять поиск, а количество ключей постоянно (или очень медленно меняется), используйте массив. В остальном словари совсем не плохие.

Answer 5

Использование многомерных списков - обычно реализуется как вложенные объекты. Вы можете легко сделать это обрабатывать отрицательные индексы с небольшой арифметикой. Он может использовать больше памяти, чем словарь, так как что-то должно быть помещено в каждый возможный слот (обычно None для пустых), но доступ будет осуществляться с помощью простого поиска индексации, а не хеширования, как это было бы со словарем.