Python "Memory Error." / Saving Memory

Question

I've made a program that takes a list of numbers and outputs the "triples." A triple is represented by x/y/z and x>=y>=z

For some reason, when executing my code, I'm getting a "memory error." I'm not sure why this is happening or how to solve it. I can only assume that it has something to do with managing memory incorrectly or making my program more efficiently.

This is lengthy, but I can't leave anything out because I have no Idea what the problem is.

So two questions... How do I fix this "memory error." And how can I make this program more efficient? (It's terribly slow as is.)

Program Output: [[6, 3, 1], [6, 2, 2], [6, 2, 1], [6, 1, 1], [5, 1, 1], [4, 2, 2], [4, 2, 1], [4, 1, 1], [3, 1, 1], [2, 2, 1], [2, 1, 1]] 11

l = [1,1,2,2,3,4,5,6]

def answer(l):
    l.sort()
    l.reverse()
    triples = []
    final = []
    for first_main_counter in range(len(l)):
        main_testing_number = l[first_main_counter]
        divisors = []
        divisors = [x for x in l if main_testing_number % x == 0]
        del divisors[0]
        for second_main_counter in range(len(divisors)):
            second_main_testing_number = divisors[second_main_counter]
            divisors2 = []
            divisors2 = [x for x in divisors if second_main_testing_number % x == 0]
            del divisors2[0]
            for x in range(len(divisors2)):
                triples.append([l[first_main_counter],divisors[second_main_counter],divisors2[x]])

    seen = set()
    for item in triples:
        t = tuple(item)
        if t not in seen:
            final.append(item)
            seen.add(t)
    print(final)
    print(len(final))


answer(l)

What does x/y/z mean? From your code I'm guessing you intend / to mean "divides". Also, you wrote z>=y>=z. Did you mean z>=y>=x? — BrenBarn
– BrenBarn, Commented Dec 26, 2016 at 7:23
You should show the output you expect for your sample input. — BrenBarn
– BrenBarn, Commented Dec 26, 2016 at 7:28

BrenBarn · Accepted Answer · 2016-12-26 09:09:24Z

3

If I understand you correctly, you can do that much, much more simply:

>>> {(x, y, z) for x, y, z in itertools.combinations(l, 3) if z % y == 0 and y % x == 0}
 {(1, 1, 2),
 (1, 1, 3),
 (1, 1, 4),
 (1, 1, 5),
 (1, 1, 6),
 (1, 2, 2),
 (1, 2, 4),
 (1, 2, 6),
 (1, 3, 6),
 (2, 2, 4),
 (2, 2, 6)}

That's it. As long as your list is sorted, itertools.combinations will only return triples in ascending order. (If your list isn't sorted, just sort it first. If you want them in the other order, reverse-sort it and switch the direction of the divisibility checks.) You don't need to do all the laborious divisor checking you're doing. Just check every combination and see if it satisifies "x divides y" and "y divides z".

If you care more about speed, here is a version that is comparable in speed to your original, but much more readable:

def anotherWay(stuff):
    result = set()
    for ix, x in enumerate(stuff):
        for iy, y in enumerate(stuff[ix+1:], ix+1):
            if y % x:
                continue
            for z in stuff[iy+1:]:
                if z % y:
                    continue
                result.add((x, y, z))
    return result

(This again assumes the list is in ascending order, and returns results where z >= y >= x, which is what you asked for in your question, but not what your code actually does.)

edited Dec 26, 2016 at 9:09

answered Dec 26, 2016 at 7:35

BrenBarn

253k39 gold badges421 silver badges392 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Will Over a year ago

Wow. That's a ton easier than what I did lol. I'm also assuming the execution time is better as well? Would this solve my memory problem?

BrenBarn Over a year ago

@Will: Try it and see. If your list grows large, it may well take a long time, since the number of possible combinations grows explosively. But it shouldn't use too much memory, since itertools.combinations will only generate one combination at a time and not hold them all in memory at once.

Will Over a year ago

Ok thank you! And one last thing! How would I then count how many triples it outputs? I feel silly for asking this

BrenBarn Over a year ago

@Will: The result is a set. If you assign the result to a variable (with triples = {...}) you can just do len(triples) to see how many there are.

Will Over a year ago

Thank you so much!

|

Collectives™ on Stack Overflow

Python "Memory Error." / Saving Memory

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related