CODEWITHSUNDEEP
pythonalgorithm
leet
leet

Reputation: 961

Fast way to increment an array with a given number

Suppose I have a very huge array and I want to increment every element in the array by a given number. Is there a way to do this without iterating over all the elements?

I do not want to do the obvious iteration over all elements:

x = [ a + inc for a in x ]

Upvotes: 5

Views: 6480

Answers (5)

Peter Cordes
Peter Cordes

Reputation: 364583

Oops, this is the same as Wolph's answer, but he only considers addition.

Keep track of all the scalar operations to be done to every array element, and do them on the fly as elements are accessed, or next time you do something non-scalar that touches every element.

You could implement a wrapper class that lets you add and multiply arrays by scalars, and just tracked the scalars to combine multiple operations into one. Code reading the array would go through a wrapper that did the mx+b operation.

Upvotes: 0

DeepSpace
DeepSpace

Reputation: 81644

One of the fastests ways I know is by using Numpy:

from time import clock
li = range(500000)
start = clock()
li = [i+5 for i in li]
print "Time taken = %.5f" % (clock() - start)
>> Time taken = 0.06355

VS

from time import clock
import numpy as np
li = range(500000)
li = np.array(li)
start = clock()
li += 5
print "Time taken = %.5f" % (clock() - start)
>> Time taken = 0.00055

Note that I'm not timing the creation of the list itself and the creation of the Numpy array.

Upvotes: 6

Wolph
Wolph

Reputation: 80031

No way to modify all numbers without looping over all of them. But you can wrap the collection with something that increments the number upon access.

>>> class OffsetCollection(object):
...     def __init__(self, collection, offset):
...         self.collection = collection
...         self.offset = offset
...     def __getitem__(self, key):
...         return self.collection[key] + self.offset
...
>>> a = [1 ,3, 6, 7, 9, 0, 2]
>>> b = OffsetCollection(a, 5)
>>> a[3]
7
>>> b[3]
12

When using numpy it might do it with a lighter operation. Assuming you use 8 bits integer on a 64 bits number it would be possible to simply add the offset to every 8 bits of the 64 bits (so 8 numbers at a time) with 1 simple addition.

Upvotes: 2

Luka Rahne
Luka Rahne

Reputation: 10457

I am not sure if that is want you want, but.

There is constant time operation for this and is called generators so

y = ( a + inc for a in x )

And now y is lazy generator. You can construct whole bunch of stuff this way in constant time.

What will take time, is "reconstructing" this back in list, but complexity can be reduced based on how many elements from beginning you take out.

Upvotes: -1

Christian Ternus
Christian Ternus

Reputation: 8492

There's no magic way to update every number in an array without ... updating every number in the array. You can phrase it differently if you really hate iterators for some reason:

x = map(lambda i: i + 1, x)

Upvotes: 0

Related Questions