List manipulation code optimization with Python

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 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.

Something like

[sum(v1[x:y]) for y in range(l+1) for x in range(y)]

seems problematic to me for a couple of reasons:

1. it considers each substring of v1, of which there are 1+2+3+...+n for a list of length n, i.e. the number of substrings grows proportional to the square of the length.
2. it creates a slice for each substring, and each slice is a copy.
3. it sums each slice even though there is clearly a lot of overlap between the slices (e.g. if you know the sum of the first four numbers, you should really only need a single extra addition to get the sum of the first five numbers instead of summing the first five from scratch).

I suspect there's not much you can do about 1, but you can be more clever about tackling the other two items: it may be faster to utilise the fact that the sum of the slice [i:j] is the just the sum of the slice [i:j-1] (i.e. the slice starting at the same position, but one element shorter) and the element at position j-1 (i.e. the interval [j-1:j]). This means each sum can be defined as a sum of two previously computed sums.

I.e. instead of

a = [sum(v1[x:y]) for y in range(l+1) for x in range(y)]

try using

sums = {(i,i+1): x for i, x in enumerate(v1)}
for intervalLen in range(2, l + 1):
    for i in range(l - intervalLen + 1):
        j = i + intervalLen
        sums[(i,j)] = sums[(i,j-1)] + sums[(j-1,j)]
a = sums.values()

This uses a little sums dictionary of memoisation: it maps tuples denoting the intervals (e.g. (0,1)) to the sum of that interval. The dictionary is initialised with the trivial sums for intervals of length 1 and then updated for longer intervals. Each step makes use of previously computed sums.

You might reduce the cost of of the summing with an approach similar to this:

cache = defaultdict(defaultdict(dict))

def my_sum(v, x, y):
    if y - x == 1:
        return v[x]
    if not y in cache[v][x]:
        mid = (x + y) / 2
        cache[v][x][y] = my_sum(v, x, mid) + my_sum(v, mid, y)
    return cache[v][x][y]

then:

a = [my_sum(v1, x, y) for y in range(l+1) for x in range(y)]

might be faster...

You can also try this:

In [75]: v = [1,2,3,4,5,6,7,8,9,10, 9, 2, 1]

In [76]: r = {}

In [77]: for x in v: r[x] = r.setdefault(x,0) + 1

In [78]: r
Out[78]: {1: 2, 2: 2, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 2, 10: 1}

In [79]: def func():
   ....:     r = {}
   ....:     for x in v: r[x] = r.setdefault(x,0) + 1
   ....:     return r
   ....: 
In [80]: def func1():
   ....:     return Counter(v)
   ....: 
In [81]: %timeit -q -o func()
Out [81]: <TimeitResult : 100000 loops, best of 3: 2.25 µs per loop>

In [82]: %timeit -q -o func1()
Out [82]: <TimeitResult : 100000 loops, best of 3: 4.17 µs per loop>

so using it, i am getting the final results as:

# t is len of v1
r = {} 
for i, x in enumerate(v1):
    for y in range(i, t):
        r[(i, y)] = r.setdefault((i, y), 0) + x
        for z in range(0, i):
            r[(z, y)] = r.setdefault((z, y), 0) + x
r1 = {}
for x in r.values():
    r1[x] = r1.setdefault(x, 0) + 1
print(r1)

Result:

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