mardi 22 décembre 2020

If function to speed time of calculation

i am following dynamic programming tutorial. It is a code for checking if a subset of strings is able to form the main string

A side from memoization, It is mentioned that the following if statement helps fasten the calculation, that if a single branch of calculation is true, it will return True and not calculating the rest of the branch.

if canConstruct(remainder_string,words,memo):
       memo[target_string] = True

However, I have randomly modified the code without the if function and still get the same results and same "speed"

When I print the remainder_string during the loop. both the code looks the same.

Please help explain is there any actual difference between Code A and Code B?

# Code A
def canConstruct(target_string,words,memo=None):
  
  if memo == None: memo = dict()
  
  if target_string in memo:
    return memo[target_string]

  if target_string == "": return True

  for word in words:
    if target_string.startswith(word):
      remainder_string = target_string[len(word):]
      print(remainder_string)
      if canConstruct(remainder_string,words,memo): # This is added to make calculation faster
        memo[target_string] = True
        return memo[target_string]
   memo[target_string] = False
   return False
  
print(canConstruct('ccccccccccccccccccccccccccccccf',['c','cc','cccc','ccccc','ccccccccc','ccccccccccccccccc','d']))

Code A loop

# Code B
def canConstruct(target_string,words,memo=None):
  
  if memo == None: memo = dict()
  
  if target_string in memo:
    return memo[target_string]

  if target_string == "": return True

  for word in words:
    if target_string.startswith(word):
      remainder_string = target_string[len(word):]
      print(remainder_string)
      memo[target_string] = canConstruct(remainder_string,words)
      return memo[target_string]
  return False
  
print(canConstruct('ccccccccccccccccccccccccccccccf',['c','cc','cccc','ccccc','ccccccccc','ccccccccccccccccc','d']))

Code B loop

Aucun commentaire:

Enregistrer un commentaire