Кто-нибудь знает большую редкую библиотеку одномерных массивов в Python?

Question

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

Я бы хотел, чтобы реализация массива не теряла пространство для значений, которые не используются, и допускала смещение индекса, отличное от нуля.Например, если мои числа начинаются с 1 000 000, я хотел бы иметь возможность индексировать мой массив, начиная с 1 000 000, и не обязан тратить память на миллион неиспользуемых значений.,Расширение на новую территорию может быть небольшой задержкой, но чтение и запись должны быть по возможности равны O (1).

Кто-нибудь знает библиотеку, которая может это сделать?

Обновлено, чтобы упомянуть int64 в качестве типа данных.

Answer 1

Похоже, что тип blist ( документация , загрузка ) может быть именно тем, что вы ищете (отказ от ответственности: я автор). У него точно такой же интерфейс, как у list в Python, поэтому нет кривой обучения, но у него другие характеристики производительности. В частности, он может эффективно обрабатывать разреженные списки во многих случаях. Ниже приведен пример, который создает список из 2 ** 29 элементов. Это в значительной степени мгновенно. Разреженные списки, созданные таким образом, используют пробел O (log n).

>>> from blist import *
>>> x = blist([0])             # x is a blist with one element
>>> x *= 2**29                 # x is a blist with > 500 million elements
>>> x.append(5)                # append to x
>>> y = x[4:-234234]           # Take a 500 million element slice from x
>>> del x[3:1024]              # Delete a few thousand elements from x

Операции, которые повторяются по всему списку, по-прежнему занимают O (n) времени (remove, reverse, count и т. Д.). В документации описывается сложность времени для каждой операции, поэтому вы сможете оценить, соответствует ли она вашим потребностям.

Answer 2

Другой вариант - по крайней мере, если вы хотите реализовать его самостоятельно - это Страница таблицы . Это обычно используется в системах виртуальной памяти для сопоставления виртуальных адресов с физическими адресами, и это лучше всего работает, если ваше адресное пространство мало заполнено, а используемые адреса кластеризованы. Если используемые адреса распределены случайным образом, это будет менее эффективно.

Базовый подход к таблице страниц такой же, как Trie - рекурсивное подразделение. Таблица страниц имеет фиксированное количество уровней, и каждый узел представляет собой массив фиксированного размера. Если запись для данного подузла равна нулю, все листья, покрываемые этим узлом, равны нулю. Основным преимуществом таблицы страниц является то, что поиск выполняется быстро, требуя лишь нескольких сдвигов и разыменований.

Давайте посмотрим на простую реализацию Python двухуровневой таблицы страниц:

class Pagetable(object):
  def __init__(self, num_bits=8):
    """Creates a new Pagetable with num_bits bits per level.

    Args:
      num_bits: The number of bits per pagetable level.
        A 2 level pagetable will be able to store indexes between 0 and 2^(num_bits*2).
    """
    self.num_bits = num_bits
    self.mask = (1 << num_bits) - 1
    self.root = [None] * (2 ** num_bits)

  def __getitem__(self, idx):
    page = self.root[idx >> self.num_bits]
    return page and page[idx & self.mask]

  def __setitem__(self, idx, val):
    page = self.root[idx >> self.num_bits]
    if not page:
      page = self.root[idx >> self.num_bits] = [None] * (2 ** self.num_bits)
    page[idx & self.mask] = val

Answer 3

Почему бы просто не использовать диктовку?

sparse = dict()
sparse[100000] = 1234
sparse[123456] = 2345

Answer 4

Я не знаю Python, так что это, вероятно, не ответ:

В некоторых языках вы можете моделировать разреженный массив, определяя функцию из вашего индексного пространства в ваше пространство данных.Например (псевдокод):

f[1000000] = 32;
f[2000000] = 51;

В некоторых языках (лучшие) форма ссылки на массив (например, f[3]) выглядит как форма вызова функции (например, * 1007).*).Это, конечно, потому что массив определяет функцию из индексного пространства в пространство данных.Таким же образом очень легко реализовать разреженные массивы больших размеров.

Answer 5

Вы можете переназначить пустую разреженную матрицу в разреженный массив - или рассмотреть возможность использования хеш-таблицы (python dict). Что касается смещения, просто оберните любой класс хранения, который вы используете, и сделайте ваши собственные методы вставки / поиска / удаления.