Как я могу реализовать словарь с массивом NumPy?

Question

Мне нужно записать огромное количество пар число-число в массив NumPy. Поскольку многие из этих пар имеют второе значение 0, я подумал о создании чего-то похожего на словарь. Проблема в том, что я прочитал документацию NumPy по структурированным массивам, и кажется, что словари, построенные так же, как и на странице, могут использовать только строки в качестве ключей.

Кроме этого, мне нужна вставка и поиск, чтобы иметь сложность log(N). Я думал о том, чтобы создать свою собственную красно-черную древовидную структуру с использованием обычного массива NumPy в качестве хранилища, но я уверен, что есть более простой способ сделать это.

Язык Python 2.7.12.

Answer 1

Самая основная форма словаря - это структура, называемая HashMap, Реализация хэш-карты основана на превращении ключа в значение, которое можно быстро найти. Патологический пример будет использовать ints as keys: значение для ключа 1 пошел бы в array[1], значение для ключа 2 пошел бы в array[2]Хэш-функция - это просто функция тождества. Вы можете легко реализовать это, используя массив numpy.

Если вы хотите использовать другие типы, это просто написание хорошей хэш-функции для превращения этих ключей в уникальные индексы в вашем массиве. Например, если вы знаете, что у вас есть (int, int) кортеж, и первое значение никогда не будет больше 100, вы можете сделать 100*key[1] + key[0],

Реализация вашей хеш-функции - это то, что сделает или сломает замену словаря.

Answer 2

Итак, у вас есть (N,2) массив, и много значений в x[:,1] 0

Что вы подразумеваете под insertion? Добавление значения в массив, чтобы сделать его (N+1,2)? Или просто меняется x[i,:] к чему-то новому?

А как насчет поиска? numpy массив отлично подходит для поиска значений ih, x[i,:], но не так хорошо, чтобы найти значения, которые соответствуют z, двухъярусный массив фильтров Python по условию

scipy.sparse реализует различные формы разреженных матриц, которые полезны, если менее одной десятой возможных значений не равны нулю. Один формат dok, словарь ключей. Это на самом деле dict подкласс, и ключи являются двумерным индексным кортежем (i,j), Другие форматы хранят свои значения в виде массивов, например, строки, столбцы и данные.

structured arrays предназначены для случаев со скромным количеством именованных полей, и каждое поле может содержать данные различного типа. Но я не думаю, что это помогает повернуть (N,2) массив в (N,) массив с 2 полями.

================

Ваши комментарии показывают, что вы не знакомы с тем, как numpy массивы хранятся или доступны.

Массив состоит из плоского 1d data buffer (просто c массив байтов) и такие атрибуты, как shape, strides, itemsize а также dtype,

Скажем так np.arange(100),

In [1324]: np.arange(100).__array_interface__
Out[1324]: 
{'data': (163329128, False),
 'descr': [('', '<i4')],
 'shape': (100,),
 'strides': (4,)
 'typestr': '<i4',
 'version': 3}

Так что, если я попрошу x[50], он вычисляет шаги, 4 байта / элемент, * 50 элементов = 200 байтов, и спрашивает, в c код для 4 байтов в 163329128+200и возвращает их как целое число (объект np.int32 типа на самом деле).

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

Шаг для (N,2) целочисленного массива равен (8,4). Так что доступ к x[10,1] элемент с 10*8 + 1*4 = 84 смещение. И доступ к x[:,1] это с i*8 for i in range... Смещения.

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

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

Есть только несколько встроенных numpy подклассы массива, в основном np.matrix а также np.masked_arrayи они не расширяют методы доступа. Создание подклассов не так просто, как с обычными классами Python, так как numpy имеет немного собственного скомпилированного кода. Подкласс должен иметь __new__ метод, а не обычный __init__,

Есть модули Python, которые поддерживают отсортированные списки, bisect а также heapq, Но я не понимаю, как они помогут вам с большой проблемой памяти.