Python Forum
Thread Rating:
  • 1 Vote(s) - 2 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Speed up recursive function
#1
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:


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")
Reply
#2
(Jun-27-2018, 07:59 AM)SimuzDarkuz Wrote: To simplify everything I did a recursive function that sorts numbers from smallest to biggest.
why? what's wrong with list.sort() method or sorted() function?
If you can't explain it to a six year old, you don't understand it yourself, Albert Einstein
How to Ask Questions The Smart Way: link and another link
Create MCV example
Debug small programs

Reply
#3
(Jun-27-2018, 08:26 AM)buran Wrote:
(Jun-27-2018, 07:59 AM)SimuzDarkuz Wrote: To simplify everything I did a recursive function that sorts numbers from smallest to biggest.
why? what's wrong with list.sort() method or sorted() function?

Well, actually I will have to combine elements that are compatible or incompatible together in different boxes.

The problem is that item A can be compatible with item B and item C can be compatible to B but not to A...

I have to combine 4 items pro box in order to get all boxes full but only with compatible items.

To simplify the problem I did the sorting exercise, after that I will then substitute the 'if>than' with the compatibility check.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  with open context inside of a recursive function billykid999 1 549 May-23-2023, 02:37 AM
Last Post: deanhystad
  Why recursive function consumes more of processing time than loops? M83Linux 9 4,128 May-20-2021, 01:52 PM
Last Post: DeaD_EyE
  Combine Two Recursive Functions To Create One Recursive Selection Sort Function Jeremy7 12 7,192 Jan-17-2021, 03:02 AM
Last Post: Jeremy7
  Execution of Another Recursive Function muzikman 5 2,947 Dec-04-2020, 08:13 PM
Last Post: snippsat
  Don't Understand Recursive Function muzikman 9 3,575 Dec-03-2020, 05:10 PM
Last Post: muzikman
  list call problem in generator function using iteration and recursive calls postta 1 1,862 Oct-24-2020, 09:33 PM
Last Post: bowlofred
  Recursive function returns None, when True is expected akar 0 3,352 Sep-07-2020, 07:58 PM
Last Post: akar
  factorial using recursive function spalisetty06 12 3,948 Aug-25-2020, 03:16 PM
Last Post: spalisetty06
  Recursive Function sridhar 7 2,733 Jul-14-2020, 07:53 PM
Last Post: deanhystad
  Nested Recursive Function not Returning Etotheitau 2 2,217 May-09-2020, 06:09 PM
Last Post: Etotheitau

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020