0

My below code uses more than 300000 KB using about(30000 input element) and there is a limit per memory usage(256 MB), so is there any way to optimize it?

import itertools
def get_subsets(arr,m) :
    return list(itertools.combinations(arr,m))
def _9(string) :
    count =0
    for i in range(len(string)-1 , -1 ,-1) :
        if string[i] != '9' :
            break
        count += 1
    return count
if __name__ == "__main__" :
    length = int(input())
    arr = [int(x) for x in input().strip().split()]
    pairs = get_subsets(arr,2)
    max_9 = [_9(str(x[0]+x[1])) for x in pairs]
    max_9_0 = max(max_9)  
    print(max_9_0,max_9.count(max_9_0))

The problem is: Let's define the quality of the price as the number of nines at its end (the number of rightmost digits that are equal to 9). For example, numbers 2999 and 123912391999 both have the quality 3, while number 952 has quality 0.

There are n products with distinct prices t1, t2, ..., tn.

You're going to buy exactly two products (they must be different). Please find the maximum possible quality of the total price of two chosen products. Also, find the number of ways to choose two different products and get that maximum possible quality of the total price.

martineau
  • 119,623
  • 25
  • 170
  • 301
mohammed awni
  • 158
  • 1
  • 13
  • 1
    You could start by not materializing your combinations iterator... – juanpa.arrivillaga Oct 18 '17 at 22:09
  • 1
    Why are you building so many lists when iterators work fine? – user2357112 Oct 18 '17 at 22:10
  • @user2357112 ok i will change lists with iterators. – mohammed awni Oct 18 '17 at 22:20
  • 1
    Try changing the `get_subsets()` function to `return itertools.combinations(arr,m)` which will return a (relatively small) generator of the different combinations rather than an actual `list` containing of all of them. – martineau Oct 18 '17 at 23:02
  • @martineau using your solution the memory usage problem is solved . But another problem appeared TIME_LIMIT_EXCEEDED . I will try to optimize the code to solve TIME_LIMIT_EXCEEDED problem . – mohammed awni Oct 18 '17 at 23:30
  • 1
    Python itself doesn't have a time limit on how long a script is allowed to run, so it must be whatever else you're using to run the code that's producing that error. Regardless, you may need to now figure-out how to optimize your code to run faster given that it now isn't using too much memory. Another thing to consider would be using a completely different algorithm—yours seems like a very "brute force" approach. – martineau Oct 18 '17 at 23:37
  • 1
    Profiling your script may help seeing where it's spending most of its time—to know where to spend your own time optimizing. See [**_How can you profile a script?_**](https://stackoverflow.com/questions/582336/how-can-you-profile-a-script) – martineau Oct 18 '17 at 23:40

1 Answers1

1

One way might be instead of using lists. Use generators. They are iterable too. See: http://letstalkdata.com/2015/05/how-to-use-python-generators-to-save-memory/

LFMekz
  • 593
  • 8
  • 10