Размер списка в Python и объём оперативной памяти

#python #python_internals

При исполнении следующего кода    

n = 10 ** 9
alist = [0] * n


Компьютер начинает работать очень медленно (похоже из-за нехватки оперативной памяти?).
Если я правильно понял, в этом случае список создаётся и вмещается в память, но занимает
такое её количество, что всё начинает "тормозить". При этом, например, если размер
списка равен 10 ** 10, то сразу выдаётся MemoryError. Получается, что пайтон не может
вместить список такого размера в оперативную память (её физически не хватает) или стоят
какие-то ограничения на размер списка?  

Хотелось бы разобраться, почему так происходит в этих двух случаях. Также хотел узнать,
как лучше защититься от зависаний вследствие нехватки оперативной памяти (каждый раз
заранее прикидывать, какой объём памяти будет занимать список,  написать какой-нибудь
код, где будет проверяться это дело или ещё как-то?).

Обновление

Списки такого размера мне понадобились при нахождении всех простых чисел меньше n
с помощью решета Эратосфена. Я начал с n = 100 и постепенно увеличивал размер списка.
Вплоть до  10 ** 8 всё работало, а потом начались неприятные тормоза. Соответственно,
хотел узнать как можно защититься (от себя) в таких случаях. Может есть какие-нибудь
рекомендации по максимальному размеру списка в процентах от объёма оперативной памяти,
чтобы не возникало таких зависаний?
    

Ответы

Ответ 1

[0] * n список в CPython требует примерно n * <размер указателя>  байтов (можно посмотреть
на реализации функций list_repeat(), PyList_New(n), PyMem_Malloc(), чтобы увидеть случаи
когда MemoryError сразу выбрасывается без попытки выделения памяти -- на 32-битной
платформе эти пределы достаточно низкие: n = 536870911 (((2**32 - 1) >> 1) // 4), на
64-битной платформе маловероятно что эти условия сработают -- другими словами: вы можете
создавать списки настолько большими насколько у вас памяти хватит -- практически ограничений нет.

Защита простая: узнайте сколько у вас на компьютере памяти и не пытайтесь  выделить
больше этого кол-ва.

По конкретной задаче: можно уменьшить потребление памяти в 4-8 раз, если использовать
array, numpy.array вместо списка. Можно ещё снизить, если предварительно исключить
маленькие простые числа (wheel-optimizations), cм. Fastest way to list all primes below
N. Можно ещё gmpy2 использовать (до 16 раз меньше памяти), см. Speed up bitstring/bit
operations in Python?

Для n более 10**9 может иметь смысл использовать решето Аткина, которое требует 
N1/2+o(1) бит памяти, вместо решета Эратосфена O(N1/2(log log N)/log N)).

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

Если нужны бо́ льшие числа, то можно использовать алгоритмы, которые работают посегментно
(позволяют как верхную так и нижнюю границу указать), например, pyprimesieve.


Ответ 2

для списка символов более точно размер списка указан в вопросе
если коротко, то зависит еще и от разрядности машины.
Более того список требует на свое "поддержание" на каждые элемент больше памяти,
чем сами хранимые данные. Для каждого элемента от 40 до 79 байта плюс к длине элемента.
Так что лучше использовать массивы array или numpy.


Ответ 3

Можно попробовать использовать другой алгоритма поиска простых чисел. К примеру http://python-dao.rpisarev.org.ua/2015/08/finding-prime-numbers-in-given-interval.html