Mi considererei un programmatore Python intermedio. Una delle mie recenti sfide è stata la creazione di un elenco di tutte le possibili soluzioni a un dato Countdown problema. Senza entrare troppo nel dettaglio, ho affrontato il problema attraverso:
-
prima genera un elenco di tutte le possibili disposizioni di Number-Operator usando RPN
-
e poi bruteforcing tutti i possibili numeri / operatori di permutazioni per tutte le possibili disposizioni, registrando i pattern che mi danno la risposta.
L'elenco completo del codice è più avanti.
Sono consapevole che questo è del tutto inefficiente e il mio programma ha una scala di 5-10 minuti da completare.
Mi sono imbattuto in un approccio alternativo qui , che utilizza ricorsione e generatori e termina in modo considerevolmente più veloce - nella scala di 30 secondi. Il mio livello di comprensione di Python non mi consente di leggere semplicemente il codice che ho trovato e di comprendere appieno le sfumature.
Capisco che crea ricorsivamente espressioni ramificate con tutte le possibili permutazioni e le valuta fino a quando non viene raggiunto il risultato corretto, che è essenzialmente un'altra espressione di ciò che sto facendo. Io non capisco perché quel codice è in ordine di grandezza più veloce del mio.
Per quanto riguarda le operazioni, il codice più veloce fa la scala di 5 milioni di tentativi, il mio fa 15 milioni di tentativi, ma ciò non corrisponde ancora alla differenza di tempo di esecuzione.
La mia domanda: sarei molto grato per un puntatore su cosa esattamente sull'approccio di classe / ricorsione lo rende molto più efficiente del mio approccio piuttosto ingenuo a fondamentalmente lo stesso metodo.
Dopo aver armeggiato con lo spegnimento di vari moduli nel ciclo annidato, penso di averlo ristretto. Penso, piuttosto deludente, che la parte più lenta sia il modo in cui valuto per le espressioni RPN.
Che cosa ho fatto:
-
Sostituita la riga
result = RPN_eval(...)conresult = [0]. Questo completa il programma in meno di 9 secondi. -
Ho quindi ripristinato la linea per chiamare la funzione RPN_eval (...). Invece, mi sono liberato della generazione della stringa
attempte l'ho sostituita con una2 2 +fissa - questa versione è terminata in meno di 69 secondi ... -
Infine, il fixing di
attemptsu2 2 + 2 +ha aumentato il tempo di esecuzione a 120 secondi.
Estrapolando (approssimativamente) questo risultato secondo il quale ogni numero aggiuntivo e l'operatore nell'espressione aumentano il tempo del programma di un fattore di circa 1,7 - Ricevo un tempo di esecuzione totale di 10-11 minuti, che è ciò che il mio programma mostra in condizioni normali.
La mia nuova domanda: Pertanto, qual è la parte della funzione RPN_eval che sembra essere così scomoda e lenta? Farà più ricerche e formalizzerà questa in una domanda separata, non pertinente qui come tale
Penso di essere su qualcosa - sto provando a convertire dinamicamente le espressioni del pattern RPN in una (orrenda) funzione lambda, che posso quindi alimentare le singole permutazioni numeriche e ottenere risultati, senza dover rifare la funzione lambda fino al prossimo entra in gioco. Aggiungerà il codice qui una volta che coopererà ...
Elenco dei miei codici:
import itertools as it
import random
import time
operators = ["+", "-", "/", "*"]
count = 0
def RPN_eval(expression, answer): #a standard stack approach to evaluating RPN expressions
explist = expression.split(" ")
explist.pop(-1)
stack = []
for char in explist:
if not char in operators:
stack.append(int(char))
else:
if char == "+":
num1 = stack.pop()
num2 = stack.pop()
if num1 > num2:
return[-1]
result = num1 + num2
stack.append(result)
if char == "-":
num1 = stack.pop()
num2 = stack.pop()
result = -num1 + num2
stack.append(result)
if char == "*":
num1 = stack.pop()
num2 = stack.pop()
if num1 > num2:
return [-1]
result = num1 * num2
stack.append(result)
if char == "/":
divisor = stack.pop()
divident = stack.pop()
try:
result = divident / divisor
except:
return [-1]
stack.append(result)
if result<=0 or result != int(result):
return [-1]
return stack
################### This part runs once and generates 37 possible RPN patterns for 6 numbers and 5 operators
def generate_patterns(number_of_numbers):
#generates RPN patterns in the form NNoNNoo where N is number and o is operator
patterns = ["N "]
for pattern1 in patterns:
for pattern2 in patterns:
new_pattern = pattern1 + pattern2 + "o "
if new_pattern.count("N")<=number_of_numbers and new_pattern not in patterns:
patterns.append(new_pattern)
return patterns
#######################################
######### Slowest part of program ################
def calculate_solutions(numbers, answer):
global count
patterns = generate_patterns(len(numbers)) #RPN symbolic patterns for a given number pool, runs once, takes less than 1 second
random.shuffle(patterns) #not necessary, but yields answers to look at faster on average
print(patterns)
solutions = [] #this list will store answer strings of good solutions. This particular input produces 56 answers.
for pattern in patterns:
nn = pattern.count("N") #counts the number of numbers in a symbolic pattern to produce corresponding number group permutations
no = pattern.count("o") #same for operators
numpermut = it.permutations(numbers,nn) #all possible permutations of input numbers, is an itertools.permutations object, not a list. Takes 0 seconds to define.
print(pattern)
for np in numpermut:
oppermut = it.product(["+","-","*","/"],repeat=no) #all possible permutations of operator order for a given pattern, itertools object, not a list. Takes 0 seconds to define
for op in oppermut:
attempt = ""
ni = 0
oi = 0
for sym in pattern:
if "N" in sym:
attempt+=str(np[ni])+" " #replace Ns in pattern with corresponding numbers from permutations
ni+=1
if "o" in sym:
attempt+=str(op[oi])+" " #replace os in pattern with corresponding operators from permutations
oi+=1
count+=1
result = RPN_eval(attempt, answer) #evaluate attempt
if result[0] == answer:
solutions.append(attempt) #if correct, append to list
print(solutions)
return solutions
#####################################
solns = calculate_solutions([50 , 8 , 3 , 7 , 2 , 10],556)
print(len(solns), count)
E l'elenco dei codici più veloce:
class InvalidExpressionError(ValueError):
pass
subtract = lambda x,y: x-y
def add(x,y):
if x<=y: return x+y
raise InvalidExpressionError
def multiply(x,y):
if x<=y or x==1 or y==1: return x*y
raise InvalidExpressionError
def divide(x,y):
if not y or x%y or y==1:
raise InvalidExpressionError
return x/y
count = 0
add.display_string = '+'
multiply.display_string = '*'
subtract.display_string = '-'
divide.display_string = '/'
standard_operators = [ add, subtract, multiply, divide ]
class Expression(object): pass
class TerminalExpression(Expression):
def __init__(self,value,remaining_sources):
self.value = value
self.remaining_sources = remaining_sources
def __str__(self):
return str(self.value)
def __repr__(self):
return str(self.value)
class BranchedExpression(Expression):
def __init__(self,operator,lhs,rhs,remaining_sources):
self.operator = operator
self.lhs = lhs
self.rhs = rhs
self.value = operator(lhs.value,rhs.value)
self.remaining_sources = remaining_sources
def __str__(self):
return '('+str(self.lhs)+self.operator.display_string+str(self.rhs)+')'
def __repr__(self):
return self.__str__()
def ValidExpressions(sources,operators=standard_operators,minimal_remaining_sources=0):
global count
for value, i in zip(sources,range(len(sources))):
yield TerminalExpression(value=value, remaining_sources=sources[:i]+sources[i+1:])
if len(sources)>=2+minimal_remaining_sources:
for lhs in ValidExpressions(sources,operators,minimal_remaining_sources+1):
for rhs in ValidExpressions(lhs.remaining_sources, operators, minimal_remaining_sources):
for f in operators:
try:
count+=1
yield BranchedExpression(operator=f, lhs=lhs, rhs=rhs, remaining_sources=rhs.remaining_sources)
except InvalidExpressionError: pass
def TargetExpressions(target,sources,operators=standard_operators):
for expression in ValidExpressions(sources,operators):
if expression.value==target:
yield expression
def FindFirstTarget(target,sources,operators=standard_operators):
for expression in ValidExpressions(sources,operators):
if expression.value==target:
return expression
raise (IndexError, "No matching expressions found")
if __name__=='__main__':
import time
start_time = time.time()
target_expressions = list(TargetExpressions(556,[50,8,3,7,2,10]))
#target_expressions.sort(lambda x,y:len(str(x))-len(str(y)))
print ("Found",len(target_expressions),"solutions, minimal string length was:")
print (target_expressions[0],'=',target_expressions[0].value)
print()
print ("Took",time.time()-start_time,"seconds.")
print(target_expressions)
print(count)