List manipulation code optimization with Python
Question: I have a simple code to group and calculate content of the list. I'm concerned
of the time it takes to complete the job. With less than 100 items it is fast
enough, but several hundreds items make my Mac to scream. And I have up to
10000 items on a list from real world data. So I need to know, how it is
possible to optimize this code:

    
    
    v = [1,2,3,4,5,6,7,8,9,10]
    v1 = v[:5]
    l = len(v1)
    a = [sum(v1[x:y]) for y in range(l+1) for x in range(y)]
    d = {x:a.count(x) for x in a}
    

So on _v_ there is a list of integers. Digit can be from 1 to 4000. List
length on example is 10, but as stated above, it will go go to 10000. _v1_ is
just a split list to work with a smaller test data.

_a_ gets every item as a single instance AND all preceding items as instances:

    
    
    [1, 3, 2, 6, 5, 3, 10, 9, 7, 4, 15, 14, 12, 9, 5]
    

_d_ groups all items and counts them as a key value pair dictionary:

    
    
    {1: 1, 2: 1, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 9: 2, 10: 1, 12: 1, 14: 1, 15: 1}
    

It seems that calculating _a_ already becomes very heavy after 100+ items.
With 500 items on _a_ I get 276813 instances for _d_. So when there will be
10000 items on a list, I'm expecting up to 5559333 items to be on _d_ and
maybe 100 times more on _a_.

**UPDATE**

Based on comments and answers below there is some improvement done via
implementation below:

    
    
    def t5(v1):
        l = len(v1)
        d = {}
        for x in range(0, l):
           s = sum(v1[x:])
           if s in d:
              d[s] += 1
           else:
              d[s] = 1
           for y in range(1, l-x):
               s -= v1[-y]
               if s in d:
                   d[s] += 1
               else:
                   d[s] = 1
        return d
    

I have no idea, how to use numpy and/or numba for more optimization. Maybe
good for different separate question...


Answer: You are continually re-calculating sums for slices you already calculated
before (each `sum()` call a redundant loop), plus you are creating loads of
new list objects by slicing all the time.

You can use dynamic programming to calculate the sums instead, walking from
the end of your input list; you only need to add the 'current' value to the
sums for the next value in your list:

    
    
    # v1 is the input list, l is len(v1)
    sums = [0] * (l * (l + 1) // 2)
    for x in range(l - 1, -1, -1):
        for y in range(x, l):
             i = (y * (y + 1) // 2) + x
             sums[i] += v1[x] + (sums[i + 1] if x < y else 0)
    

This adds up already calculated sums for partial subsequences to the next
longer subsequence, avoiding a whole inner loop. This takes O(N^2) time,
rather than your O(N^3) approach (where `sum()` loops over each subslice up to
N elements long).

It translates `x` and `y` coordinates into your final 'triangle' to avoid
having to create a larger matrix (or a dictionary, which would have additional
memory and hashing overhead).

That's because you calculate slices between any two points in the list; if you
take a matrix where the axis are the start and end indices _included_ in each
slice, you can number the final list like this:

    
    
       0  1  2  3  4
    
    0  0  1  3  6 10 
    
    1     2  4  7 11
    
    2        5  8 12
    
    3           9 13
    
    4             14
    

(blank spaces are reverse slices, duplicates, not used in the output). For
each row and column, you can calculate the output index by counting how many
values fit in the triangle before that column plus the row number, or `((col *
col + 1) // 2) + row)`.

The dynamic programming approach adds the sum for already produced slices for
later values (the row below the indices) to the `v1` value for the current
row:

    
    
    v1     0  1  2  3  4
    
    1 > 0  1  3  6 10 15
              ^  ^  ^  ^  
    2 > 1     2  5  9 14
                 ^  ^  ^
    3 > 2        3  7 12
                    ^  ^
    4 > 3           4  9
                       ^ 
    5 > 4              5
    

So the value at row 2, column 4 is `v1[2]` plus the already calculated sum for
row 3, column 4, or in this case, `2 + 12`. There is only ever an already
calculated sum for those elements where the row index is smaller than the
column index; at position (3, 3) there is no calculated sum at (4, 3).

Next problem is that your `list.count()` traverses your _whole_ list of sums
to count how often one number appears. Thus, your `{x:a.count(x) for x in a}`
expression creates a O(N^2) double loop; it'll take quadratic time to process
all counts.

Use a [`Counter()`
object](https://docs.python.org/2/library/collections.html#collections.Counter)
to produce that dictionary instead (a `Counter` is a subclass of `dict`):

    
    
    from collections import Counter
    
    d = Counter(sums)
    

A `Counter()` goes through all your elements just _once_ to count the values;
it simply keeps counters for each value it has seen so far as it iterates.

