Jun-27-2018, 07:59 AM
Hi everyone,
I have to build a complex code that will sort different boxes to different places. To simplify everything I did a recursive function that sorts numbers from smallest to biggest. The problem it that it becomes incredibly slow as soon as I have more than 20 numbers.
Here the basic code:
First, I would like to understand why it becomes so slower, second I wanted to know if you have any hint to speed it up...
Thanks!!!
Just for you to run the time comparison (with 19 is pretty fast):
I have to build a complex code that will sort different boxes to different places. To simplify everything I did a recursive function that sorts numbers from smallest to biggest. The problem it that it becomes incredibly slow as soon as I have more than 20 numbers.
Here the basic code:
def trynumber1(a,x): # I stop the function when the list is finished if len(a) == 0: return x # I loop trough all elements to find the right one for item in a: # if an element is ok I go on with the next one if item > x[-1]: c = list(x) c.append(item) b = list(a) b.remove(item) funziona = trynumber1(b,c) if funziona != 0: return funziona # if no possible solution was found (duplicates) return 0 a = list of numbers x = new list sorted (by calling the function the first time x = [0]I searched for memoize functions and since it was not possible to do it with lists I found a method to convert the arguments passed to the function in a string (json), here is my new code:
# standard copy-pasted memorize function def memoize(f): memo = {} def helper(x): if x not in memo: memo[x] = f(x) return memo[x] return helper # a is a list of positive number to sort # x is the sorted list (first time x=[0]) @memoize def trynumber(together): # I stop the function when the list is finished together = json.loads(together) a = together[0] x = together[1] if len(a) == 0: return x # I loop trough all elements to find the right one for item in a: # if an element is ok I go on with the next one if item > x[-1]: c = list(x) c.append(item) b = list(a) b.remove(item) funziona = trynumber(json.dumps([b,c])) if funziona != 0: return funziona # if no possible solution was found (duplicates) return 0 now arguments passed are joint into a string: c = trynumber(json.dumps([a,x]))Guess it... It becomes ten times slower!
First, I would like to understand why it becomes so slower, second I wanted to know if you have any hint to speed it up...
Thanks!!!
Just for you to run the time comparison (with 19 is pretty fast):
from random import randrange import time import json def randoma(): a = [] while len(a) < 19: x = randrange(1,100) if x not in a: #or x in a: a.append(x) return a trials = 2 for i in range(0,trials): x = [0] a = randoma() startingtime = time.clock() c = trynumber(json.dumps([a,x])) finishtime = time.clock() print("elapsed mean time with memo:",(finishtime-startingtime)/trials) if c != 0: print(c) else: print("No solution found") startingtime = time.clock() c = trynumber1(a,x) finishtime = time.clock() print("elapsed mean time without memo:",(finishtime-startingtime)/trials) if c != 0: print(c) else: print("No solution found")