need help with memory optimization

[jnthn]

Hello all.

This is my first post, so if this question is not appropriate for this forum please let me know and I will remove it. If it remains, formatting help would be appreciated.

The following code produces the triangular array, T(n,k), of partitions of n into k positive parts, 1<=k<=n:

from math import *
n = 10
#We need an array of size 2n, because the triangle is complete only up to nth row. 
m = 2*n
tri = []
halfn = int(ceil(float(m)/2.0))

#Initialize array to zeros (so that we know no completed row contains an error).
for i in range(0,m):
  tri.append([0 for k in range(i+1)])

#Initialize first two rows.
tri[0][0] = 1
tri[1][0] = 1
tri[1][1] = 1
#Fill in the triangle by cumulatively adding the elements of the previous 
#row and placing the result diagonally (parallel to hypotenuse). Complete
#the nth row by appending the "tail" of the previous row.   
for i in range(2,halfn):
  #Reset sum for each new row.
  sums = 0
  #The list of values of previous row.
  prev = tri[i-1]
  row = i
  #Place summands diagonally...
  for col in range(0,len(prev)):
    sums += prev[col]
    tri[row][col] = sums
    row +=  1
    col += 1
  #Now append the "tail" of the previous row to complete this row.
  for k in range(tri[i][1], len(prev) + 1):
    tri[i][k] = prev[k-1]

#change n to m to print entire triangle.
for i in range(0,n):
  print(("%d" % (i+1), tri[i])) 

Currently, about half of the allocated memory is wasted space. For example, with n = 5, after execution the triangle looks like this:

[1]
[1, 1]
[1, 1, 1]
[1, 2, 1, 1]
[1, 2, 2, 1, 1]
[0, 3, 3, 0, 0, 0]
[0, 0, 4, 0, 0, 0, 0]
[0, 0, 0, 5, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Rows 1-5 are complete and rows 6-10, clearly, are not. To confirm the first 5 rows are correct, see https://oeis.org/A008284.

What I hope to do is (1) flatten the triangular array into a linear array, and then (2) eliminate the wasted memory (the zeros) via proper array indexing. (2) is the where this gets confusing.

Is this of interest to anyone?

[jnthn]

I have accomplished step 1. My code now looks like this:

def binomialn2(n):
  return (n*(n+1))/2

n = 11

m = n*2
arr = [0 for i in range(binomialn2(m)-1)]
arr[:2] = [1,1,1]
for i in range(1,(m/2) ):
  currStartIndx = binomialn2(i)
  prevStartIndx = binomialn2(i-1)
  sums = 0
  r = i
  for c in range(currStartIndx - prevStartIndx):
    sums += arr[prevStartIndx + c]
    arr[binomialn2(r) + c] = sums
    r+=1
  for k in range(arr[binomialn2(i)+1] , binomialn2(i) - binomialn2(i-1)  +1):
    arr[currStartIndx + k] = arr[prevStartIndx + k - 1]

for i in range(1,m/2+1):
  print(arr[binomialn2(i-1):binomialn2(i)])

Now for the tough bit..indexing hell.

[Larz60+]

How about something like run length encoding:
It works well when there are multiple repetitions of a number, but
poorly if a lot of changes. This code done on python 3.6.3
If you have python  version < 3.6.1 you will need to change print statements

This can be made much more efficient (code wise), but to show the concept:

t = [[(1,1)],
    [(1,2)],
    [(1,3)],
    [(1,1),(2,1),(1,2)],
    [(1,1),(2,2),(1,2)],
    [(0,1),(3,2),(0,3)],
    [(0,2),(4,1), (0,4)],
    [(0,3),(5,1), (0,4)],
    [(0,9)],
    [(0,10)]]

for item in t:
    buff = '['
    for a, b in item:
        for x in range(b):
            buff = f'{buff},{a}'
    print(f'{buff}]')

results:

Output:
[1,]
[1,1,]
[1,1,1,]
[1,2,1,1,]
[1,2,2,1,1,]
[0,3,3,0,0,0,]
[0,0,4,0,0,0,0,]
[0,0,0,5,0,0,0,0,]
[0,0,0,0,0,0,0,0,0,]
[0,0,0,0,0,0,0,0,0,0,]

[jnthn]

Hi larz,

I am not familiar with run lenth encoding, but I get what your code does. My question is how would this help eliminate the zeros? With zeros eliminated and row 5 complete, the list "arr" would look like:

[1,1,1,1,1,1,1,2,1,1,1,2,2,1,1,3,3,4,5]

To complete row 6, single inserts (of sums) are now needed before the first 3, before the 4, and before the 5, followed by two appends after the 5. Then an insert of length three (the tail from the previous row) is needed after the second 3. The result would be arr = [1,1,1,1,1,1,1,2,1,1,1,2,2,1,1,1,3,3,2,1,1,3,5,4,5,5,6,7] and row 6 = 1,3,3,2,1,1.

[Larz60+]

It works well when there are multiple repetitions of a number, but
poorly if a lot of changes

each tuple is the number followed by the number of occurrences. This is not the best compression algorithm,
but is simple, and works well when there is a lot of compression.

example, to express 50 zeroes, the tuple is (0, 50) certainly much smaller than 50 zeroes

[jnthn]

I finally accomplished step 2 and it has reduced memory usage by nearly half.

from math import *
def binom(n):
  return (n*(n+1))/2
n = 10
arr = [1,1,1]
for i in range(2,n+1):
  currStartIndx = binom(i-1) 
  prevStartIndx = binom(i-2) 
  prevLen = currStartIndx - prevStartIndx
  tailInsPos = binom(i-1) + int((i-2)/2)+1
  sumInsPos = currStartIndx
  sums = 0
  for k in range(prevLen):
    sums += arr[prevStartIndx + k]
    arr.insert(sumInsPos, sums)
    sumInsPos +=  int(floor((i-k)/2))
  tail = arr[currStartIndx-int(floor((i+1)/2)):currStartIndx]
  for d in reversed(tail):
    arr.insert(tailInsPos ,d)

for i in range(1,n+1):
  print("%d: %s" % (i, arr[binom(i-1):binom(i)]))
#print((n,binom(n),len(arr)))
print("P(%d)=%d" % (n, sum(arr[binom(n-1):binom(n)])))
print(arr)

Output:
1: [1] 
2: [1, 1] 
3: [1, 1, 1] 
4: [1, 2, 1, 1] 
5: [1, 2, 2, 1, 1] 
6: [1, 3, 3, 2, 1, 1] 
7: [1, 3, 4, 3, 2, 1, 1] 
8: [1, 4, 5, 5, 3, 2, 1, 1] 
9: [1, 4, 7, 6, 5, 3, 2, 1, 1] 
10: [1, 5, 8, 9, 7, 5, 3, 2, 1, 1] 
P(10)=42 
[1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 3, 4, 3, 2, 1, 1, 1, 4, 5, 5, 3, 2, 1, 1, 1, 4, 7, 6, 5, 3, 2, 1, 1, 1, 5, 8, 9, 7, 5, 3, 2, 1, 1, 5, 10, 11, 10, 12, 15, 13, 11, 18, 18, 14, 23, 20, 15, 26, 21, 28, 22, 29, 30, 1, 1]

The final optimization will be to reduce 'arr' to just rows n-1, n, plus every element after row n, so arr above would become (something like) [1, 4, 7, 6, 5, 3, 2, 1, 1, 1, 5, 8, 9, 7, 5, 3, 2, 1, 1, 5, 10, 11, 10, 12, 15, 13, 11, 18, 18, 14, 23, 20, 15, 26, 21, 28, 22, 29, 30, 1, 1], reducing memory from 2*binomial(n+1,2) to ~4n.

[Larz60+]

Great!