It works fine, but it is slow.

Could anybody help make this faster?

import itertools

from decorators import timer
from settings import MENU, CASH

class Cocktail(object):
    def __init__(self, group, name, sell, count=0):
        self.group = group
        self.name = name
        self.sell = sell
        self.count = count

class Check(object):
    def __init__(self, cash, menu=MENU):
        self.__cash = cash
        self.__cheapest_cocktail = 10000
        self.__menu = self.__read_menu(menu)
        self.__matrix = self.__create_matrix()
        self.correct = []

    def __read_menu(self, menu):
        result = []
        for group in menu:
            key = group.keys()[0]
            for cocktail in group[key]:
                if self.__cheapest_cocktail > cocktail['sell']:
                    self.__cheapest_cocktail = cocktail['sell']


        return result

    def __create_matrix(self):
        result = []
        max_count = self.__cash // self.__cheapest_cocktail
        for cocktail in self.__menu:
            row = []
            for i in range(0, max_count):

        return result

    def find_combinations(self):
        for check in itertools.product(*self.__matrix):
            if sum([(c.sell * c.count) for c in check]) == self.__cash:

check = Check(CASH)
check.__matrix size 80x25
  • 1
    \$\begingroup\$ Hello, could you please add some more information about what you are trying to achieve here? Thanks \$\endgroup\$
    – SylvainD
    Commented Jul 14, 2013 at 20:59
  • \$\begingroup\$ I try find all row combinations which sum elements equal any given number. \$\endgroup\$
    – lmasikl
    Commented Jul 14, 2013 at 21:01
  • \$\begingroup\$ What is check.__matrix size 80x25 after your code? Is it part of the code? Can you give a sample Input and output of your program so it can be easier to understand? \$\endgroup\$ Commented Jul 15, 2013 at 6:28
  • \$\begingroup\$ Probably not worth an answer but I think you should have a look at youtube.com/watch?v=o9pEzgHorH0 (I have no idea how many times I've posted a link to this video on this SE). \$\endgroup\$
    – SylvainD
    Commented Jul 15, 2013 at 6:56
  • \$\begingroup\$ I believe you are trying to solve the knapsack problem, here is an example: rosettacode.org/wiki/Knapsack_Problem/Python \$\endgroup\$
    – dnozay
    Commented Jul 15, 2013 at 7:02

1 Answer 1


Take a look at Python Performace Tips and search for list comprehension. As far as I can understand your code you can use it.

An example would be this function.

def __create_matrix(self):
    max_count = self.__cash // self.__cheapest_cocktail
    return [ [Cocktail(cocktail.group,cocktail.name,cocktail.sell,i)
         for i in xrange(0, max_count)] for cocktail in self._menu]

You don't need to create a list if you are not using it elsewhere. In the find_combinations function you can avoid the overhead of list creation because you are only interested in the sum of the elements.

def find_combinations(self):
    for check in itertools.product(*self.__matrix):
        if sum((c.sell * c.count) for c in check) == self.__cash:

I think there is a bug in your code. You are using a classCocktail but using cocktail in your code. I understand they are different but I think you have messed up C with c in your code in the __read_menu function. It is confusing whether or not you have messed it up.

That is all I can think of because I don't understand what the code is doing unless. Please edit your question to add sample input and output.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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