Miglioramento delle prestazioni del codice racket e errore durante il tentativo di compilazione dei byte

Question

Ho hackerato diversi frammenti di codice da varie fonti e creato un articolo crude implementation di un blog Wolfram a http://bit.ly/HWdUqK - per quelli che sono matematicamente inclini, è molto interessante!

Non sorprende che, dato che sono ancora un principiante su Racket, il codice impiega troppo tempo per calcolare i risultati (> 90 minuti contro 49 secondi per l'autore) e consuma molta memoria. Sospetto che sia tutta una questione di definizione (expListY) che deve essere rielaborata.

Anche se devo farlo funzionare in DrRacket, Inoltre sto avendo problemi di byte-compilare il sorgente, e ancora lavorando (Messaggio di errore: +: expects type <number> as 1st argument, given: #f; other arguments were: 1 -1)

Qualcuno vuole prendere una pugnalata a migliorare le prestazioni e efficienza? Mi scuso per il codice incomprensibile e la mancanza di commenti migliori sul codice.

PS: Devo tagliare e incollare il codice direttamente qui?

Answer 1

probabilmente simile alla soluzione di Soegaard, tranne questo rotola la propria "parser", quindi è autonomo. Produce l'elenco completo di 100 anni in un po 'meno di 6 secondi sulla mia macchina. C'è un sacco di trucchi che questo codice utilizza, ma non è qualcosa che si potrebbe definire "ottimizzato" in modo serio: sono sicuro che può essere reso molto più veloce con alcune memoization, attenzione per massimizzare la condivisione dell'albero ecc. Ecc. Ma per un dominio così piccolo non vale lo sforzo ... (Lo stesso vale per la qualità di questo codice ...)

BTW # 1, più di analisi, la soluzione originale (s) utilizzare eval che non lo fa rendere le cose più veloci ... Per cose come questa è sempre meglio scrivere manualmente il "valutatore". BTW # 2, questo non significa che Racket sia più veloce di Mathematica - Sono sicuro che la soluzione in quel post rende anche ridondanti cicli di CPU, e una soluzione simile sarebbe più veloce.

#lang racket 

(define (tuples list n) 
    (let loop ([n n]) 
    (if (zero? n) 
     '(()) 
     (for*/list ([y (in-list (loop (sub1 n)))] [x (in-list list)]) 
     (cons x y))))) 

(define precedence 
    (let ([t (make-hasheq)]) 
    (for ([ops '((#f) (+ -) (* /) (||))] [n (in-naturals)]) 
     (for ([op ops]) (hash-set! t op n))) 
    t)) 

(define (do op x y) 
    (case op 
    [(+) (+ x y)] [(-) (- x y)] [(*) (* x y)] [(/) (/ x y)] 
    [(||) (+ (* 10 x) y)])) 

(define (run ops nums) 
    (unless (= (add1 (length ops)) (length nums)) (error "poof")) 
    (let loop ([nums  (cddr nums)] 
      [ops  (cdr ops)] 
      [numstack (list (cadr nums) (car nums))] 
      [opstack (list (car ops))]) 
    (if (and (null? ops) (null? opstack)) 
     (car numstack) 
     (let ([op (and (pair? ops) (car ops))] 
      [topop (and (pair? opstack) (car opstack))]) 
     (if (> (hash-ref precedence op) 
       (hash-ref precedence topop)) 
      (loop (cdr nums) 
       (cdr ops) 
       (cons (car nums) numstack) 
       (cons op opstack)) 
      (loop nums 
       ops 
       (cons (do topop (cadr numstack) (car numstack)) 
         (cddr numstack)) 
       (cdr opstack))))))) 

(define (expr ops* nums*) 
    (define ops (map symbol->string ops*)) 
    (define nums (map number->string nums*)) 
    (string-append* (cons (car nums) (append-map list ops (cdr nums))))) 

(define nums (for/list ([i (in-range 10 0 -1)]) i)) 
(define year1 2012) 
(define nyears 100) 
(define year2 (+ year1 nyears)) 
(define years (make-vector nyears '())) 
(for ([ops (in-list (tuples '(+ - */||) 9))]) 
    (define r (run ops nums)) 
    (when (and (integer? r) (<= year1 r) (< r year2)) 
    (vector-set! years (- r year1) 
       (cons ops (vector-ref years (- r year1)))))) 

(for ([solutions (in-vector years)] [year (in-range year1 year2)]) 
    (if (pair? solutions) 
    (printf "~a = ~a~a\n" 
      year (expr (car solutions) nums) 
      (if (null? (cdr solutions)) 
       "" 
       (format " (~a more)" (length (cdr solutions))))) 
    (printf "~a: no combination!\n" year))) 

Answer 2

Di seguito è la mia implementazione. Ho ottimizzato una o due cose nel tuo codice, nel mio computer portatile ci vogliono circa 35 minuti per finire (sicuramente un miglioramento!) Ho scoperto che la valutazione delle espressioni è il vero killer delle prestazioni - se non fosse per le chiamate a la procedura to-expression, il programma terminerebbe tra meno di un minuto.

Immagino che nei linguaggi di programmazione che utilizzano nativamente la notazione infissa la valutazione sarebbe molto più veloce, ma in Schema il costo per l'analisi e quindi la valutazione di una stringa con un'espressione infissa è semplicemente troppo.

Forse qualcuno può indicare un sostituto adatto per il pacchetto soegaard/infix? oppure, in alternativa, un modo per valutare direttamente un elenco di espressioni infissi che tiene conto della precedenza degli operatori, ad esempio - dove & sta per concatenazione numerica e ha la precedenza più alta (ad esempio: 4 & 7 = 47) e gli altri operatori aritmetici (+, -, *, /) seguono la regole di precedenza usuali.

#lang at-exp racket 

(require (planet soegaard/infix) 
     (planet soegaard/infix/parser)) 

(define (product lst1 lst2) 
    (for*/list ([x (in-list lst1)] 
       [y (in-list lst2)]) 
    (cons x y))) 

(define (tuples lst n) 
    (if (zero? n) 
     '(()) 
     (product lst (tuples lst (sub1 n))))) 

(define (riffle numbers ops) 
    (if (null? ops) 
     (list (car numbers)) 
     (cons (car numbers) 
      (cons (car ops) 
        (riffle (cdr numbers) 
          (cdr ops)))))) 

(define (expression-string numbers optuple) 
    (apply string-append 
     (riffle numbers optuple))) 

(define (to-expression exp-str) 
    (eval 
    (parse-expression 
    #'here (open-input-string exp-str)))) 

(define (make-all-combinations numbers ops) 
    (let loop ((opts (tuples ops (sub1 (length numbers)))) 
      (acc '())) 
    (if (null? opts) 
     acc 
     (let ((exp-str (expression-string numbers (car opts)))) 
      (loop (cdr opts) 
       (cons (cons exp-str (to-expression exp-str)) acc)))))) 

(define (show-n-expressions all-combinations years) 
    (for-each (lambda (year) 
       (for-each (lambda (comb) 
          (when (= (cdr comb) year) 
          (printf "~s ~a~n" year (car comb)))) 
         all-combinations) 
       (printf "~n")) 
      years)) 

Usalo come questo per replicare i risultati in originale blog post:

(define numbers '("10" "9" "8" "7" "6" "5" "4" "3" "2" "1")) 
(define ops '("" "+" "-" "*" "/")) 
; beware: this takes around 35 minutes to finish in my laptop 
(define all-combinations (make-all-combinations numbers ops)) 
(show-n-expressions all-combinations 
        (build-list 5 (lambda (n) (+ n 2012)))) 

UPDATE:

ho snarfed analizzatore di espressioni di Eli Barzilay e inserito nel mio soluzione, ora il il pre-calcolo di tutte le combinazioni avviene in circa 5 secondi! La procedura show-n-expressions ha ancora bisogno di un po 'di lavoro per evitare di ripetere l'intera lista di combinazioni ogni volta, ma rimane come esercizio per il lettore. Ciò che importa è che ora i forzanti dei valori per tutte le possibili combinazioni di espressioni sono incredibilmente veloci.

#lang racket 

(define (tuples lst n) 
    (if (zero? n) 
     '(()) 
     (for*/list ((y (in-list (tuples lst (sub1 n)))) 
        (x (in-list lst))) 
     (cons x y)))) 

(define (riffle numbers ops) 
    (if (null? ops) 
     (list (car numbers)) 
     (cons (car numbers) 
      (cons (car ops) 
        (riffle (cdr numbers) 
          (cdr ops)))))) 

(define (expression-string numbers optuple) 
    (string-append* 
    (map (lambda (x) 
      (cond ((eq? x '&) "") 
       ((symbol? x) (symbol->string x)) 
       ((number? x) (number->string x)))) 
     (riffle numbers optuple)))) 

(define eval-ops 
    (let ((precedence (make-hasheq 
        '((& . 3) (/ . 2) (* . 2) 
         (- . 1) (+ . 1) (#f . 0)))) 
     (apply-op (lambda (op x y) 
         (case op 
         ((+) (+ x y)) ((-) (- x y)) 
         ((*) (* x y)) ((/) (/ x y)) 
         ((&) (+ (* 10 x) y)))))) 
    (lambda (nums ops) 
     (let loop ((nums  (cddr nums)) 
       (ops  (cdr ops)) 
       (numstack (list (cadr nums) (car nums))) 
       (opstack (list (car ops)))) 
     (if (and (null? ops) (null? opstack)) 
      (car numstack) 
      (let ((op (and (pair? ops) (car ops))) 
        (topop (and (pair? opstack) (car opstack)))) 
       (if (> (hash-ref precedence op) 
        (hash-ref precedence topop)) 
        (loop (cdr nums) 
         (cdr ops) 
         (cons (car nums) numstack) 
         (cons op opstack)) 
        (loop nums 
         ops 
         (cons (apply-op topop (cadr numstack) (car numstack)) 
           (cddr numstack)) 
         (cdr opstack))))))))) 

(define (make-all-combinations numbers ops) 
    (foldl (lambda (optuple tail) 
      (cons (cons (eval-ops numbers optuple) optuple) tail)) 
     empty (tuples ops (sub1 (length numbers))))) 

(define (show-n-expressions all-combinations numbers years) 
    (for-each (lambda (year) 
       (for-each (lambda (comb) 
          (when (= (car comb) year) 
          (printf "~s ~a~n" 
            year 
            (expression-string numbers (cdr comb))))) 
         all-combinations) 
       (printf "~n")) 
      years)) 

usare in questo modo:

(define numbers '(10 9 8 7 6 5 4 3 2 1)) 
(define ops '(& + - * /)) 
; this is very fast now! 
(define all-combinations (make-all-combinations numbers ops)) 
(show-n-expressions all-combinations numbers 
        (build-list 5 (lambda (n) (+ n 2012)))) 

Answer 3

questa non è una risposta completa, ma penso che sia un'alternativa alla biblioteca Óscar López sta chiedendo. sfortunatamente è in clojure, ma speriamo sia abbastanza chiaro ...

(def default-priorities 
    {'+ 1, '- 1, '* 2, '/ 2, '& 3}) 

(defn- extend-tree [tree priorities operator value] 
    (if (seq? tree) 
    (let [[op left right] tree 
      [old new] (map priorities [op operator])] 
     (if (> new old) 
     (list op left (extend-tree right priorities operator value)) 
     (list operator tree value))) 
    (list operator tree value))) 

(defn priority-tree 
    ([operators values] (priority-tree operators values default-priorities)) 
    ([operators values priorities] (priority-tree operators values priorities nil)) 
    ([operators values priorities tree] 
    (if-let [operators (seq operators)] 
     (if tree 
     (recur 
      (rest operators) (rest values) priorities 
      (extend-tree tree priorities (first operators) (first values))) 
     (let [[v1 v2 & values] values] 
      (recur (rest operators) values priorities (list (first operators) v1 v2)))) 
     tree))) 

; [] [+ & *] [1 2 3 4] 1+23*4 
; [+ 1 2] [& *] [3 4] - initial tree 
; [+ 1 [& 2 3]] [*] [4] - binds more strongly than + so replace right-most node 
; [+ 1 [* [& 2 3] 4]] [] [] - descend until do not bind more tightly, and extend 

(println (priority-tree ['+ '& '*] [1 2 3 4])) ; 1+23*4 
(println (priority-tree ['& '- '* '+ '&] [1 2 3 4 5 6])) ; 12 - 3*4 + 56 

l'output è:

(+ 1 (* (& 2 3) 4)) 
(+ (- (& 1 2) (* 3 4)) (& 5 6)) 

[aggiornamento] aggiungendo la seguente

(defn & [a b] (+ b (* 10 a))) 

(defn all-combinations [tokens length] 
    (if (> length 0) 
    (for [token tokens 
      smaller (all-combinations tokens (dec length))] 
     (cons token smaller)) 
    [[]])) 

(defn all-expressions [operators digits] 
    (map #(priority-tree % digits) 
    (all-combinations operators (dec (count digits))))) 

(defn all-solutions [target operators digits] 
    (doseq [expression 
      (filter #(= (eval %) target) 
      (all-expressions operators digits))] 
    (println expression))) 

(all-solutions 2012 ['+ '- '* '/ '&] (range 10 0 -1)) 

risolve il problema, ma è lento - 28 minuti per completare. questo è su un computer portatile piacevole, abbastanza recente (i7-2640M).

(+ (- (+ 10 (* 9 (& 8 7))) (& 6 5)) (* 4 (& (& 3 2) 1))) 
(+ (- (+ (+ (* (* 10 9) 8) 7) 6) 5) (* 4 (& (& 3 2) 1))) 
(- (- (+ (- (& 10 9) (* 8 7)) (* (& (& 6 5) 4) 3)) 2) 1) 

(ho stampato solo 2012 - vedere il codice sopra - ma avrebbe valutato l'intera sequenza).

quindi, sfortunatamente, questo in realtà non risponde alla domanda, dal momento che non è più veloce del codice di Óscar López. Immagino che il prossimo passo sarebbe quello di mettere un po 'di intelligenza nella valutazione e quindi risparmiare un po' di tempo. ma cosa?

[aggiornamento 2] dopo aver letto gli altri posti qui i sostituito eval con

(defn my-eval [expr] 
    (if (seq? expr) 
    (let [[op left right] expr] 
     (case op 
     + (+ (my-eval left) (my-eval right)) 
     - (- (my-eval left) (my-eval right)) 
     * (* (my-eval left) (my-eval right)) 
     /(/ (my-eval left) (my-eval right)) 
     & (& (my-eval left) (my-eval right)))) 
    expr)) 

e il tempo di esecuzione scende a 45 secondi. ancora non eccezionale, ma è un'analisi/valutazione molto inefficiente.

[aggiornamento 3] per completezza, il seguente è un'implementazione dell'algoritmo manovra-yard (un semplice che è sempre rimasto-associativa) e eval associato, butit riduce solo il tempo di 35s.

(defn shunting-yard 
    ([operators values] (shunting-yard operators values default-priorities)) 
    ([operators values priorities] 
    (let [[value & values] values] 
     (shunting-yard operators values priorities nil (list value)))) 
    ([operators values priorities stack-ops stack-vals] 
; (println operators values stack-ops stack-vals) 
    (if-let [[new & short-operators] operators] 
     (let [[value & short-values] values] 
     (if-let [[old & short-stack-ops] stack-ops] 
      (if (> (priorities new) (priorities old)) 
      (recur short-operators short-values priorities (cons new stack-ops) (cons value stack-vals)) 
      (recur operators values priorities short-stack-ops (cons old stack-vals))) 
      (recur short-operators short-values priorities (list new) (cons value stack-vals)))) 
     (concat (reverse stack-vals) stack-ops)))) 

(defn stack-eval 
    ([stack] (stack-eval (rest stack) (list (first stack)))) 
    ([stack values] 
    (if-let [[op & stack] stack] 
     (let [[right left & tail] values] 
     (case op 
      + (recur stack (cons (+ left right) tail)) 
      - (recur stack (cons (- left right) tail)) 
      * (recur stack (cons (* left right) tail)) 
     /(recur stack (cons (/ left right) tail)) 
      & (recur stack (cons (& left right) tail)) 
      (recur stack (cons op values)))) 
     (first values)))) 

Answer 4

Come sottolinea Óscar, il problema è che soegaard/infix è lento per questo tipo di problema.

ho trovato un parser manovra-yard standard per le espressioni infissa su GitHub e ha scritto il seguente programma in Racket:

#lang racket 
(require "infix-calc.scm") 

(define operators '("*" "/" "+" "-" "")) 
(time 
(for*/list ([o1 (in-list operators)] 
      [o2 (in-list operators)] 
      [o3 (in-list operators)] 
      [o4 (in-list operators)] 
      [o5 (in-list operators)] 
      [o6 (in-list operators)] 
      [o7 (in-list operators)] 
      [o8 (in-list operators)] 
      [o9 (in-list operators)] 
      [expr (in-value 
        (apply string-append 
         (list "1" o1 "2" o2 "3" o3 "4" o4 "5" o5 "6" o6 "7" o7 "8" o8 "9" o9 "10")))] 
      #:when (= (first (calc expr)) 2012)) 
expr)) 

dopo poco meno di 3 minuti i risultati sono:

Welcome to DrRacket, version 5.2.900.2--2012-03-29(8c22c6c/a) [3m]. 
Language: racket; memory limit: 128 MB. 
cpu time: 144768 real time: 148818 gc time: 25252 
'("1*2*3+4*567*8/9-10" 
    "1*2+34*56+7+89+10" 
    "1*23+45*6*7+89+10" 
    "1+2+3/4*5*67*8+9-10" 
    "1+2+3+4*567*8/9-10" 
    "1+2+34*56+7+8+9*10" 
    "1+23+45*6*7+8+9*10" 
    "1-2+345*6-7*8+9-10" 
    "12*34*5+6+7*8-9*10" 
    "12*34*5+6-7-8-9-10" 
    "1234+5-6+789-10") 

Il parser di infisso è stato scritto da Andrew Levenson. Il parser e il codice di cui sopra può essere trovato qui:

https://github.com/soegaard/Scheme-Infix-Calculator

Answer 5

Interessante! Dovevo provarlo, è in Python, spero non ti dispiaccia. Viene eseguito in circa 28 secondi, PyPy 1.8, Core 2 Duo 1,4

from __future__ import division 
from math import log 
from operator import add, sub, mul 
div = lambda a, b: float(a)/float(b) 

years = set(range(2012, 2113)) 

none = lambda a, b: a * 10 ** (int(log(b, 10)) + 1) + b 
priority = {none: 3, mul: 2, div: 2, add: 1, sub: 1} 
symbols = {none: '', mul: '*', div: '/', add: '+', sub: '-', None: ''} 

def evaluate(numbers, operators): 
    ns, ops = [], [] 
    for n, op in zip(numbers, operators): 
     while ops and (op is None or priority[ops[-1]] >= priority[op]): 
      last_n = ns.pop() 
      last_op = ops.pop() 
      n = last_op(last_n, n) 
     ns.append(n) 
     ops.append(op) 
    return n 

def display(numbers, operators): 
    return ''.join([ 
     i for n, op in zip(numbers, operators) for i in (str(n), symbols[op])]) 

def expressions(years): 
    numbers = 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 
    operators = none, add, sub, mul, div 
    pools = [operators] * (len(numbers) - 1) + [[None]] 
    result = [[]] 
    for pool in pools: 
     result = [x + [y] for x in result for y in pool] 
    for ops in result: 
     expression = evaluate(numbers, ops) 
     if expression in years: 
      yield '%d = %s' % (expression, display(numbers, ops)) 

for year in sorted(expressions(years)): 
    print year