Эффективный массив Python с 100 миллионами нулей?
Что эффективный путь состоит в том, чтобы инициализировать и элементы доступа большого массива в Python?
Я хочу создать массив в Python с 100 миллионами записей, неподписанных 4-байтовых целых чисел, инициализированных для обнуления. Я хочу быстрый доступ к массиву, предпочтительно с непрерывной памятью.
Странно, массивы NumPy, кажется, работают очень медленный. Есть ли альтернативы, которые я могу попробовать?
Существует array.array модуль, но я не вижу метод для эффективного выделения блока 100 миллионов записей.
Ответы на комментарии:
- Я не могу использовать разреженный массив. Это будет слишком медленно для этого алгоритма, потому что массив становится плотным очень быстро.
- Я знаю, что Python интерпретируется, но конечно существует способ сделать быстрые операции над массивом?
- Я сделал некоторое профилирование, и я добираюсь о 160K доступах к массиву (поиск или обновление элемента индексом) в секунду с NumPy. Это кажется очень медленным.
9 ответов
Рассмотрим это путь. При использовании new появляется новый объект. Период. У вас есть функция, которая ищет существующего пользователя и возвращает его при обнаружении. Лучше всего выразить это статической функцией класса, такой как User:: findUser (). Это также можно расширить при выводе классов из базового класса.
Я сделал некоторое профилирование, и результаты совершенно противоречивы. Для простых операций доступа к массиву numpy и array.array в 10 раз медленнее собственных массивов Python .
Обратить внимание, что для доступа множества, я делаю операции формы:
a[i] += 1
Профили:
[0] * 20000000
- Доступ: 2.3M / секунда
- Инициализация: 0,8 s
numpy.zeros (формируют = (20000000), dtype=numpy.int32)
- Доступ: инициализация 160K/sec
- : 0,2 s
array.array ('L', [0] * 20000000)
- Доступ: инициализация 175K/sec
- : 2,0 s
array.array ('L', (0, поскольку я в диапазоне (20000000)))
- Доступ: 175K/sec, по-видимому, основанный на профиле для другой инициализации array.array
- : 6,7 s
Напомню, как работают целые числа Python: если вы выделяете список, говоря
a = [0] * K
, вам понадобится память для списка ( sizeof (PyListObject) + K * sizeof (PyObject *) ) и память для единственного целочисленного объекта 0 . Пока числа в списке остаются ниже магического числа V , которое Python использует для кэширования, все в порядке, потому что они являются общими, т.е. любое имя, указывающее на число n
>>> i = 0
>>> j = 0
>>> while i is j:
... i += 1
... j += 1
>>> i # on my system!
257
Это означает, что как только счетчики превысят это число, вам потребуется память sizeof (PyListObject) + K * sizeof (PyObject *) + d * sizeof (PyIntObject) , где d V (== 256) . В 64-битной системе sizeof (PyIntObject) == 24 и sizeof (PyObject *) == 8 , то есть потребление памяти в худшем случае составляет 3 200 000 000 байт.
При использовании numpy.ndarray или array.array потребление памяти остается постоянным после инициализации, но вы платите за объекты оболочки, которые создаются прозрачно, как сказал Томас Воутерс. Вероятно, вам следует подумать о преобразовании кода обновления (который получает доступ и увеличивает позиции в массиве) в код C, используя Cython или scipy.weave .
Попробуйте следующее:
x = [0] * 100000000
На моем компьютере выполняется всего несколько секунд, а доступ почти мгновенный.
Маловероятно, что вы найдете что-то быстрее, чем массив numpy . Реализация самого массива столь же эффективна, как, например, в C (и в основном такая же, как array.array , только с большей полезностью).
Если вы хотите ускорить процесс код, вам придется сделать это, сделав именно это. Несмотря на то, что массив реализован эффективно, доступ к нему из кода Python имеет определенные накладные расходы; например, при индексации массива получаются целочисленные объекты, которые необходимо создавать «на лету». numpy предлагает ряд операций, эффективно реализованных на C, но не видя фактического кода, который работает не так хорошо, как вы хотите, трудно делать какие-либо конкретные предложения.
В дополнение к другим отличным решениям есть еще один способ - использовать dict вместо массива (существующие элементы не равны нулю, в противном случае они нуль). Время поиска - O (1).
Вы также можете проверить, находится ли ваше приложение в ОЗУ, а не выгружать его. Это всего лишь 381 МБ, но система может не выдавать вам все это по какой-то причине.
Однако есть также несколько действительно быстрых разреженных матриц ( SciPy и ndsparse ). Они выполняются на низкоуровневом языке C и тоже могут быть хорошими.
Я бы просто создал ваш собственный тип данных, который не инициализирует ЛЮБЫЕ значения.
Если вы хотите прочитать позицию индекса, которая НЕ была инициализирована, вы возвращаете нули. Тем не менее, не инициализируйте никакого хранилища.
Если вы хотите прочитать позицию индекса, которая была инициализирована, просто верните значение.
Если вы хотите записать в индексную позицию, которая НЕ была инициализирована, инициализируйте ее и сохраните входные данные.
NumPy - подходящий инструмент для большой однородный массив фиксированного размера. Доступ к отдельным элементам чего-либо в Python не будет таким быстрым, хотя операции с целым массивом часто могут выполняться со скоростью, аналогичной C или Fortran. Если вам нужно быстро выполнять операции с миллионами и миллионами элементов по отдельности, вы можете получить от Python лишь ограниченное количество возможностей.
Какой алгоритм вы реализуете? Откуда вы знаете, что использование разреженных массивов слишком медленно, если вы не пробовали это делать? Что вы имеете в виду под «эффективным»? Вам нужна быстрая инициализация? Это узкое место вашего кода?
Для быстрого создания используйте модуль массива.
Использование модуля массива в ~5 раз быстрее для создания, но примерно в два раза медленнее для доступа к элементам по сравнению с обычным списком:
# Create array
python -m timeit -s "from array import array" "a = array('I', '\x00'
* 100000000)"
10 loops, best of 3: 204 msec per loop
# Access array
python -m timeit -s "from array import array; a = array('I', '\x00'
* 100000000)" "a[4975563]"
10000000 loops, best of 3: 0.0902 usec per loop
# Create list
python -m timeit "a = [0] * 100000000"
10 loops, best of 3: 949 msec per loop
# Access list
python -m timeit -s "a = [0] * 100000000" "a[4975563]"
10000000 loops, best of 3: 0.0417 usec per loop
Synapse - это хорошая многоплатформенная сетевая библиотека. Открытый исходный код и очень простой в использовании.
http://www.ararat.cz/synapse/doku.php/download
-121--4690780-Разве безопасность больше не является заданием для операционной системы?
Я имею в виду, создать пользователя с ограниченным доступом к файлам и т.д. Тогда пусть виртуальная машина будет запущена только с этими правами.
Или, может быть, я говорю ерунду. Я не сысадмин и не эксперт по безопасности, но я обычно делаю вещи с инструментами, которые сделаны для этого.
-121--4269027- Если вы не можете векторизировать вычисления, Python/Numpy будет медленным. Функция Numpy работает быстро, поскольку векторизованные вычисления выполняются на более низком уровне, чем Python. Основные функции numpy написаны на языке C или Fortran. Следовательно, sum (a) не является петлей питона с множеством доступов, это единственный вызов низкого уровня C.
Демонстрационная страница производительности Numpy Python содержит хороший пример с различными опциями. Вы можете легко получить увеличение в 100 раз, используя более низкий уровень компилированного языка, Cython, или используя векторизованные функции, если это возможно. Эта запись в блоге , которая показывает 43-кратное увеличение использования Cython для numpy usecase.