0
\$\begingroup\$

My goal is to code the knapsack problem algorithm. The problem is that a knapsack has a given weight limit, W. I have a collection of items which have a given weight and value in a file that looks like:

# test.txt
1234  4456
4321  7654
...   ...

Where value is the first column, and weight is the second. My algorithm seeks to maximize the value of items in the knapsack while staying at or beneath the weight limit W. This is what I've come up with so far:

import numpy as np
#reading the data:
values = []
weights = []
test = []
with open("test.txt") as file:
  for line in file:
    value, weight = line.split(" ")
    values.append(int(value))
    weights.append(int(weight.replace("\n","")))


W = values.pop(0)
weights
size = weights.pop(0) +1
weights = [0] + weights
values = [0] + values


#Knapsack Algorithm:


hash_table = {}
for x in range(0,W +1):
  hash_table[(0,x)] = 0

for i in range(1,size):
  for x in range(0,W +1):
    if weights[i] > x:
      hash_table[(i,x)] = hash_table[i - 1,x]
    else:
      hash_table[(i,x)] = max(hash_table[i - 1,x],hash_table[i - 1,x - weights[i]] + values[i])

My idea is to use a "hash table" as a part of a dynamic programming technique in order to speed up my code. But I have tried to run it on a big input file and I am out of RAM (and it works very slowly).

Can you review my code and give me some hints how can I speed up my program?

\$\endgroup\$
  • 1
    \$\begingroup\$ in addition to the link to Wikipedia could you provide a brief description of the algorithm. Links sometimes get broken. \$\endgroup\$ – pacmaninbw Oct 15 at 18:55
  • \$\begingroup\$ You run out of RAM? With Python? What version are you running? How big is your file and how big is your RAM? Something smells fishy here. While your code is inefficient, you shouldn't be running out of RAM with it... \$\endgroup\$ – Mast Oct 16 at 17:54
  • \$\begingroup\$ @Mast the file is relatively large, but it's really the implementation of the algorithm. The best thing OP can do is look at some of the better space-efficiency algorithms. It's not impossible to run out of memory with python, and benchmarking OP's code, I see about 64GB memory usage before the interpreter crashes \$\endgroup\$ – C.Nivs Oct 16 at 23:08
3
\$\begingroup\$

Part of the reason you're running out of memory is that you are allocating all of your items into memory twice. Once in the two lists weights and values, and once again in hash_table.

Looking at your program, I don't see a need for you to keep your weights and values allocated as you do. You iterate through them one at a time in your outer for loop. What I'd do is make use of a generator and wrap the file reading in a function:

def read_file():
    with open('knapsack.txt') as fh:

        # these value names are a bit more descriptive, and
        # you can use a next() call on this generator
        # to extract these values
        WEIGHT, SIZE = map(int, next(fh).strip().split())
        yield WEIGHT, SIZE

        for line in fh:
            yield map(int, line.strip().split())

This way you can do tuple unpacking in a for loop:

iterator = read_file()
# here's that next call I mentioned
WEIGHT, SIZE = next(iterator)

# iterate over the remaining values
for weight, value in iterator:
    # do something

This will keep copies of your values from proliferating throughout the execution of your program when you really don't need them.

I'd also look into enumerate, since you need the index for part of your hash_table keys, but you also need the weight and value as well. This eliminate repeated lookups that slow down your code:

for i, (w, v) in enumerate(read_file(), start=1):
    for x in range(WEIGHT + 1):
        ...

To show the effect:

# repeated index lookup
python -m timeit -s 'x = list(range(1, 10000))' 'for i in range(len(x)): a = x[i] + 2'
500 loops, best of 5: 792 usec per loop

# no repeated index lookup
python -m timeit -s 'x = list(range(1, 10000))' 'for i, j in enumerate(x): a = j + 2'
500 loops, best of 5: 536 usec per loop

It doesn't appear that you really need the leading 0 0 row on weights and columns, either, since you start the index at 1, skipping it. Avoiding the addition of lists here cuts down on overhead, and you can specify enumerate to start at a given value with the start kwarg as I've done above.

The goal here should be to iterate over a collection as little as possible, so a refactored version might look like:

def read_file():
    with open('knapsack.txt') as fh:

        # these value names are a bit more descriptive, and
        # you can use a next() call on this generator
        # to extract these values
        WEIGHT, SIZE = map(int, next(fh).strip().split())
        yield WEIGHT, SIZE

        for line in fh:
            yield map(int, line.strip().split())


iterator = read_file()
WEIGHT, SIZE = next(iterator)
hash_table = {(0, i): 0 for i in range(WEIGHT + 1)}

for i, (w, v) in enumerate(iterator, start=1):
    for j in range(WEIGHT + 1):
        if w > j:
            hash_table[(i, j)] = hash_table[(i - 1, j)]
        else:
            hash_table[(i, j)] = max(
                hash_table[(i - 1, j)],
                hash_table[(i - 1, j - w)] + v
            )

This doesn't avoid all of the memory issues, however. You are dealing with a relatively large file and housing that in a dictionary will lead to heavy memory usage. As noted in the Wikipedia article, the solution you have implemented will have a worst-case space complexity of O(nW), which for this file is approximately O(n * 2000000)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.