CODEWITHSUNDEEP
pythonpython-3.xalgorithmoptimization
alpacinohead
alpacinohead

Reputation: 67

This code is too inefficient, how can I increase memory and execution efficiency?

I'm trying to complete the following challenge: https://app.codesignal.com/challenge/ZGBMLJXrFfomwYiPs. I have written code that appears to work, however, it is so inefficient that it fails the test (too long to execute and uses too much memory). Are there any ways I can make this more efficient? I'm quite new to building efficient scripts. Someone mentioned "map()" can be used in lieu of "for i in range(1, n)". Thank you Xero Smith and others for the suggestions of optimising it this far:

from functools import reduce
from operator import mul
from itertools import combinations

# Starting from the maximum, we can divide our bag combinations to see the total number of integer factors                                                                                    

def prime_factors(n):
    p = 2
    dct = {}
    while n != 1:
        if n % p:
            p += 1
        else:
            dct[p] = dct.get(p, 0) + 1
            n = n//p
    return dct


def number_of_factors(n):
    return reduce(mul, (i+1 for i in prime_factors(n).values()), 1)


def kinderLevon(bags):
    candies = list()
    for x in (combinations(bags, i) for i in range(1, len(bags)+1)):
        for j in x:
            candies.append(sum(j))
    satisfied_kids = [number_of_factors(i) for i in candies]
    return candies[satisfied_kids.index(max(satisfied_kids))]

Any help would be greatly appreciated.

Thanks,

Aaron

Upvotes: 2

Views: 155

Answers (3)

Xero Smith
Xero Smith

Reputation: 2076

First things first, combinations are iterable. This means you do not have to convert them into lists before you iterate over them; infact it is terribly inefficient to do so.

Next thing that can be improved significantly is your factors procedure. Currently it is linear. We can do better. We can get the number of factors of an integer N via the following algorithm:

  1. get the prime factorisation of Nsuch that N = p1^n1 * p2^n2 * ...
  2. the number of factors of N is (1+n1) * (1+n2) * ...

see https://www.wikihow.com/Find-How-Many-Factors-Are-in-a-Number for details.

Something else, your current solution has a lot of variables and computations that are not used. Get rid of them.

With these, we get the following which should work:

from functools import reduce
from operator import mul
from itertools import combinations

# Starting from the maximum, we can divide our bag combinations to see the total number of integer factors                                                                                    

def prime_factors(n):
    p = 2
    dct = {}
    while n != 1:
        if n % p:
            p += 1
        else:
            dct[p] = dct.get(p, 0) + 1
            n = n//p
    return dct


def number_of_factors(n):
    return reduce(mul, (i+1 for i in prime_factors(n).values()), 1)


def kinderLevon(bags):
    candies = list()
    for x in (combinations(bags, i) for i in range(1, len(bags)+1)):
        for j in x:
            candies.append(sum(j))
    satisfied_kids = [number_of_factors(i) for i in candies]
    return candies[satisfied_kids.index(max(satisfied_kids))]

Upvotes: 1

TDk
TDk

Reputation: 1059

Following my comment, I can already identify a memory & complexity improvement. In your factors function since you only need the number of factors, you could only count them instead of storing them.

def factors(n):
    k = 2
    for i in range(2, n//2 +1):
        if n % i == 0:
            k += 1
    return k

EDIT: as suggested in the comments stop the counter earlier.

This actually reduces time complexity for huge numbers, but not really for smaller ones.

This is a much better improvement than the one using list comprehensions (that still allocates memory)

Moreover, it is pointless to allocate your combinations list twice. You're doing 

x = list(combinations(bags, i));
for j in list(x):
    ...

The first line you convert a tuple (returned by combinations) into a list, hence duplicating the data. The second line list(x) re-allocates a copy of the list, taking even more memory! There you should really just write:

for j in combination(bags, i):
    ...

As a matter of syntax, please don't use semicolons ; in Python !

Upvotes: 2

Louis Saglio
Louis Saglio

Reputation: 1148

Use list comprehensions. The factors function can be transformed like this :

def factors(n):
    return len([i for i in range(1, n + 1) if n % i == 0])

Upvotes: 1

Related Questions