Is there a way that uses less memory in python to do this

Question

I am using or-tools to solve an optimization problem. I have many constraints that I am storing in a list. Unfortunately, that takes a lot of memory space.

constraints_list = []
for i in range(rows):
    constraints_list.append([0] * (4 * i) + [1, 1, 1, 1] + [0] * ((rows * (columns - 1)) -  ((columns - 1) * (i + 1))))

rows is in the order of hundreds of thousands, and columns is five. Is there a better way to do this?

Answer 1

The first thing that comes into my head is using compression of some sort. i.e. only storing essential parts of your constraints in the array needed to reproduce the entire constraint. For example:

[0] * (4 * i)

This is not needed fully. You can simply store i and you will know that the first 4 * 1 elements in this array will be 0s. Similarly,

+[1, 1, 1, 1]

Is not needed, as you already know that after the first 4 * i elements, the next four will be 1s. Again

+[0] * ((rows * (columns - 1)) - ((columns - 1) * (i + 1))))

Is also unnecessary. you can simply store the value x = ((rows * (columns - 1)) - ((columns - 1) * (i + 1))) and you know that the last x elements will be 0s as well.

Overall, this is what your code will look like:

constraints_list = []
for i in range(rows):
    x = (rows * (columns - 1)) - (columns - 1) * (i + 1)
    new_constraint = [i, x]
    constraints_list.append(new_constraint)

Notice that decompression of each new_constraint is still constant and finding an element at each index is also fairly easy even with this compressed version. Also, notice that the only variable in (rows * (columns - 1)) - (columns - 1) * (i + 1) is i+1. So instead of saying x = (rows * (columns - 1)) - (columns - 1) * (i + 1), only x = i+1 is strictly necessary, although it will probably be easier to not compress it this much.

Edit: I realised that in your specific constraints_list, there is absolutely no need to actually store any storage whatsoever. You can simply have a build_constraint function that takes i, rows, and columns as arguments. One example could be:

def build_constraint(i, rows, columns):
    return [0] * (4 * i) + [1, 1, 1, 1] + [0] * ((rows * (columns - 1)) -  ((columns - 1) * (i + 1)))

However, i do realise that this can be quite inconvenient depending on your specific purpose however it is one option. It also is not particularly slow in building the constraint.