Is the numpy array and python list optimized for dynamic growth?

Question

I did a lot of time, requiring me to use the list .append() function, as well as the numpy.append() function for numpy arrays. I noticed that both of them grow very slowly when the sizes of arrays are large.

I need an array that grows dynamically for sizes of about 1 million elements. I can implement this myself, just as std::vector runs in C ++ by adding a buffer length (fallback length) that is not accessible from the outside, But do I need to reinvent the wheel? I suppose this should be implemented somewhere. So my question is: does such a thing already exist in Python?

What I mean: Is there an array type in Python that can dynamically grow with O(C) time complexity most of the time?

Answer 1

Both use a base array. Instead, you can use collections.deque , which is designed to specifically add and remove items from both ends using O (1) complexity

Answer 2

The memory of numpy arrays is well documented and much discussed here. The layout of the list layout was also discussed, although it usually just contrasts with numpy.

The numpy array uses a fixed size data buffer. Growth requires creating a new array and copying data to it. np.concatenate does this in compiled code. np.append , as well as all the stack functions, use concatenate .

The list has, as I understand it, an adjacent data buffer containing pointers to objects where in the memeory. Python supports some freespace in this buffer, so adding with list.append relatively quick and easy. But when freespace is full, it must create a new buffer and pointers to copies. I can see where it can get expensive with big lists.

Thus, the pointer for each element will be stored in the list, as well as the element itself (for example, float) in a different place in memory. In contrast, an array of floats stores the floats themselves as contiguous bytes in their buffer. (Dtype object arrays are more like lists).

The recommended way to create an array iteratively is to create a list using append and create the array once at the end. Repeating np.append or np.concatenate relatively expensive.

deque . I do not know how it stores its data. The docs say that it can add items at the beginning as easily as at the end, but random access is slower than for a list. This means that it stores data in some sort of linked list, so finding an nth element requires n-1 links to go through it. Thus, there is a trade-off between growth rate and access rate.

Adding items to the top of the list requires creating a new list of pointers with new (s) at the beginning. Therefore, adding and removing items from the very beginning of a regular list is much more expensive than at the end.

Recommended software is outside the scope of SO. Others may make suggestions, but do not be surprised if it closes.

File formats such as HDF5 exist for large data sets. They adapt to growth with features such as "chunking". And there are all kinds of database packages.