How to speed up numpy.append

user_13688286 0
Viewed 738

I have a function that generates a numpy array given an index and i want to have a 2d array of these arrays but when i do a simple for loop it gets stuck

A = np.zeros(0)
for i in range(1000):
    np.append(A, getArray(i))

why does this result in infinite loop? it ran for very long and it never finished? the function getArray returns a very big array of 500000 elements (it is an image)

time-complexity numpy python
2 Answers

Edit: See below answer on this post, it's better!

I have run into this problem before. The issue is that np.append() takes O(n+m) time where n is the size of the first array and m is the size of the second. This means that every time you call np.append(), it gets slower and slower. It can be shown by a simple runtime analysis that the runtime of this function is O(n*k^2) where n is the size of the output from getArray() and k is the amount of looping you're doing, in this case 1000.

You can get around this problem and speed up incredibly by breaking the problem of merging down logarithmically. The essential problem here is that the first getArray() has to be accounted for 999 times in the runtime, and the second one 998, and so forth. This is incredibly slow as you have observed. The target would be to have each array contribute a small number of merges. You can do this by having a function that asks for the first half of the items, and merges it with the second half. And that first half gets the first and second quarters, and so on. Like this:

def get_range(lo, hi):
    if lo == hi:
        return getArray(lo)
    mid = int((lo+hi)/2)
    return np.append(get_range(lo, mid), get_range(mid+1, hi))

With this function, each return from getArray only contributes log(k) times to the overall process, so the runtime here is O(n k log(k)), which will be much faster in this case, and far more scaleable.

user_136743510

Use list append to collect a list of all the arrays, and create the final array with just one call:

A = np.array([getArray(i) for i in range(1000)])

or

alist = []
for i in range(1000):
     alist.append(getArray(i))
A = np.array(alist)

List append operates in-place and is more efficient. There's no array copying.

np.append is just a stupid cover for np.concatenate. concatenate (and the various stack functions) take a list of arrays. Take advantage of that. Using any of these repeatedly in an iteration is inefficient.

user_9019250
Related