2
\$\begingroup\$

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']

                result.append(Cocktail(
                    key,
                    cocktail['name'],
                    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):
                row.append(Cocktail(
                    cocktail.group,
                    cocktail.name,
                    cocktail.sell,
                    i
                ))

            result.append(row)
        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:
                self.correct.append(check)


check = Check(CASH)
check.find_combinations()
check.__matrix size 80x25
\$\endgroup\$
  • 1
    \$\begingroup\$ Hello, could you please add some more information about what you are trying to achieve here? Thanks \$\endgroup\$ – Josay Jul 14 '13 at 20:59
  • \$\begingroup\$ I try find all row combinations which sum elements equal any given number. \$\endgroup\$ – lmasikl Jul 14 '13 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\$ – Aseem Bansal Jul 15 '13 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\$ – Josay Jul 15 '13 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 Jul 15 '13 at 7:02
2
\$\begingroup\$

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:
            self.correct.append(check)

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.

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