CODEWITHSUNDEEP
arraysperformanceincrement
user1502381
user1502381

Reputation: 145

Incrementing in a list efficiently

I have a list:

foo = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Currently, I increment a known number of consecutive indices by a given value:

def increment(index, length, some_value, a_list):
    for i in range(index, index+length):
        a_list[i] += some_value
    return a_list
foo = increment(2,3,4,foo) 
# [0, 0, 4, 4, 4, 0, 0, 0, 0, 0]

However, the problem is that I would be doing this over a range of 50-100 "length" and would be doing this millions of times. So, my looping would pose a considerable problem to computational time (I believe). Is there a way to add a given value to all indices within a given range without having to loop through the given indices?

Upvotes: 0

Views: 49

Answers (2)

Hermann Döppes
Hermann Döppes

Reputation: 1373

Simon Tatham wrote something about "Cumulative Frequency Tables": http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumulative.html This would apparently get you log times:

def increment(index, length, some_value, a_frequency_table):
    // increment "frequency" of (index) by some_value
    // decrement "frequency" of (index+length-1) by some_value

He also links C-code on the bottom of the page. If I understood your question right, it should be possible to adopt.

Upvotes: 1

ejc
ejc

Reputation: 343

Given your requirements, it looks to me as though you doing this correctly in regards to performance. The only thing I can see to improve performance is very miniscule... I wouldn't bother returning the array, as it is unnecessary. Beyond that, everything looks sound.

def increment(index, length, some_value, a_list):
for i in range(index, index+length):
    a_list[i] += some_value

increment(2,3,4,foo) 
# [0, 0, 4, 4, 4, 0, 0, 0, 0, 0]

Upvotes: 0

Related Questions