The increment of the first n elements of the list under the condition

Question

I have a list like

l = [10, 20, 30, 40, 50, 60] 

I need to increase the first elements of the n list specified by the condition. The condition is list independent. For example, if n = 3 , the list l should look like this:

 l = [11, 21, 31, 40, 50, 60] 

I understand that I can do this with a for loop for each list item. But I need to do such an operation about 150 million times. So, I am looking for a faster method for this. Any help is much appreciated. thanks in advance

Answer 1

You can create a simple data structure at the top of the list that stores the start and end range of each increment operation. The start will be 0 in your case, so you can just save the end.

This way, you don’t really have to navigate the list to enlarge it, but you only save that you performed increments on ranges, for example, from {0 to 2} and {from 0 to 3}. In addition, you can also map some operations so that if several operations increase to the same index, you only need to save one record.

In the worst case, this solution is O(q + gx qlogq + n) , where g is the number of get operations, q is the number of updates, and n is the length of the list. Since we can have no more than n different ends for intervals, this reduces to O(q + nlogn + n) = O(q + nlogn) . A naive solution using an update for each request would be O(q * l ), where l (request length) can be up to size n, giving O(q * n) . Therefore, we can expect this solution to be better if q > log n .

The following is an example of a working python:

 def RangeStructure(object): def __init__(self, l): self.ranges = collections.defaultdict(int) self.l = l def incToPosition(self, k): self.ranges[k] += 1 def get(self): res = self.l sorted_keys = sorted(self.ranges) last = len(sorted_keys) - 1 to_add = 0 while last >= 0: start = 0 if last < 1 else sorted_keys[last - 1] end = sorted_keys[last] to_add += self.ranges[end] for i in range(start, end): res[i] += to_add last -= 1 return res rs = RangeStructure([10, 20, 30, 40, 50, 60]) rs.incToPosition(2) rs.incToPosition(2) rs.incToPosition(3) rs.incToPosition(4) print rs.get() 

And the explanation:

• after the ranges of operations will contain (start, end, Inc.) tuples of the form (0, 2, 2), (0, 3, 1), (0, 4, 1); they will be represented in the dict as {2: 2, 3: 1, 4: 1}, since the beginning is always 1 and can be omitted

• during the get operation, we guarantee that we will only work with one element of the list once; we sort the ranges in ascending order of their endpoint and move them in reverse order, updating the contained list items and the sum ( to_add ) added to subsequent ranges

Prints as expected:

 [14, 24, 32, 41, 50, 60] 

Answer 2

Here's the aggregation operation in NumPy:

 initial_array = # whatever your l is, but as a NumPy array increments = numpy.zeros_like(initial_array) ... # every time you want to increment the first n elements if n: increments[n-1] += 1 ... # to apply the increments initial_array += increments[::-1].cumsum()[::-1] 

This is O(ops + len(initial_array)) , where ops is the number of increment operations. If you are not doing a small number of increments in a very small part of the list, this should be much faster. Unlike a naive implementation, it does not allow you to retrieve element values ​​until increments are applied; if you need to do this, you may need a solution based on the BST or BST structure to track the increments.

Answer 3

m - the number of requests, n - a list to increase the length, the idea of ​​the O (n + m) algorithm:
since you only need to increase from the beginning to some k-th element, you will get ranges of increments. Let our increment be a pair (accurate to position, increment by). Example:
(1, 2) - increment of positions 0 and 1 by 2
If we are trying to calculate the value at position k, then we must add increments that have positions greater than or equal to k to the current value at position k. How can we quickly calculate the sum of increments that have positions greater than or equal to k? We can start calculating the values ​​from the back of the list, and then remember the sum of the increments.
Proof of concept:

 # list to increment a = [1, 2, 5, 1, 6] # (up to and including k-th index, increment by value) queries = [(1, 2), (0, 10), (3, 11), (4, 3)] # decribed algorithm implementation increments = [0]*len(a) for position, inc in queries: increments[position] += inc got = list(a) increments_sum = 0 for i in xrange(len(increments) -1, -1, -1): increments_sum += increments[i] got[i] += increments_sum # verify that solution is correct using slow but correct algorithm expected = list(a) for position, inc in queries: for i in xrange(position + 1): expected[i] += inc print 'Expected: ', expected print 'Got: ', got 

output:

 Expected: [27, 18, 19, 15, 9] Got: [27, 18, 19, 15, 9] 

Answer 4

You can use list comprehension and add the remaining list.

 [x + 1 for x in a[:n]]+a[n:]