Scheme - скорость выполнения кода

2

2

Не буду писать многабукаф - просто скажите, сколько (по времени в секундах) в Scheme выполняется данный кот:

(define (divs n)
    (define (go i a)
        (cond ((> (* i i) n) a)
              ((= (* i i) n) (+ 1 a))
              ((= 0 (modulo n i)) (go (+ 1 i) (+ 2 a)))
              (else (go (+ 1 i) a))))
    (go 1 0))
 
(define (task n k)
    (cond ((>= 500 (divs k)) (task (+ 1 n) (+ k n 1))) (else k)))
 
(display (task 1 1))

Я пробовал несколько онлайн вычисляторов, и время выполнения различается на порядки. Где-то указывают реализацию (chiken / guile), где-то нет. Здесь https://repl.it/languages/scheme какое-то неприличное время выполняется, здесь https://www.tutorialspoint.com/execute_scheme_online.php весьма неплохо (относительно остальных), на Ideone и Rextester промежуточные показатели... Я в растерянности - где правда?

Ссылка

←	Как получить позицию курсора из plasma_engine_mouse

как в базе mysql найти текст?

→

Показаны ответы на комментарий. Показать все комментарии.

Ответ на: комментарий от Puzan 20.10.2016 03:36:03 +00:00

Дело в том, что мне не нужна аутентичная стандартная в полной мере схема. Я просто написал три реализации своего схемоподобного по синтаксису и семантике языка, интерпретаторы. Но поскольку особой оптимизации не делал, скорость выполнения оставляет желать - например кот из стартового поста на паре реализаций выполняется 40 секунд и 3 минуты 50 секунд соответственно. Желая получить возможность убыстрить исполнение, я подумал, что чем самостоятельно пытаться курить JIT или статическую оптимизирующую компиляцию, проще будет попробовать транслировать котов на моем диалекте в какой-нибудь готовый промышленный язык с оптимизациями на борту. Попробовал в Java, но ниасилил победить стековерфлоу. Потом меня осенило, что если не брать спецвозможностей моего диалекта, определяемых платформой реализации, то он синтаксически и семантически похож на схему - почему бы не транслировать в какой-нибудь из ее диалектов? Поскольку локально ничего не стояло, полез в инет на онлайн-РЕПЛы проверять эффективность, удивился результатам и создал эту тему. В результате (спасибо осмысленно пишущим участникам) выбрал Racket (я на винде, измучен мышовыми гуями, да и скорость на примере одна из лучших), и сейчас с интересом узнаю, что можно не только учить мой диалект конвертировать кот в синтаксис схемы (обильно досыпая скобок при этом, что имхо не способствует читабельности и понимабельности), но и написать на Racket реализацию своего диалекта, т.к. в нем присутствуют бортовые возможности для этого - это приятный бонус к скорости, удобному гуевому РЕПЛу, хорошей документации и т.п.

Вот, вкратце, что я хотел сказать о моих целях и мотивации.

Ivana ★
(20.10.2016 11:23:28 +00:00) автор топика

Ответ на: комментарий от Ivana 20.10.2016 11:23:28 +00:00

Racket со многих сторон хорош. Накостылил на своем языке транслятор его же кода в Racket, альфа-версию, но вполне применимую. Например, после тривиальной доработки напильником получается вот такой ракетный кот, который вполне себе работает

#lang racket

(define (noelem x l) (cond ((null? l) #t) ((equal? x (car l)) #f) (else (noelem x (cdr l)))))
(define (take n l) (cond ((null? l) nil) ((> n 0) (cons (car l) (take (- n 1) (cdr l)))) (else nil)))
(define (drop n l) (cond ((null? l) nil) ((> n 0) (drop (- n 1) (cdr l))) (else l)))
(define nil '())

(begin (display "ЗАДАЧА - решение судоку, реализация поиска в глубину:") (display "\n"))
(define field (quote (0 0 9 3 0 1 8 0 0 0 0 0 0 0 0 0 3 0 2 0 0 0 7 0 0 0 9 1 0 0 2 0 9 0 0 4 0 0 4 0 8 0 2 0 0 8 0 0 7 0 6 0 0 1 9 0 0 0 1 0 0 0 5 0 2 0 0 0 0 0 7 0 0 0 5 6 0 2 4 0 0)))
(define (showField f) (define (go f) (cond ((null? f) "") (else (string-append (foldl (lambda (x a) (string-append a (number->string x) " ")) "" (take 9 f)) "\n" (go (drop 9 f)))))) (cond ((null? f) "Нет решений") (else (go f))))
(begin (display "Стартовое поле:") (display "\n")) (display (showField field))

(define (steps field)
  (define (step-vars i) (begin (define r (/ i 9)) (define c (modulo i 9)) (define rs0 (* 3 (/ r 3))) (define cs0 (* 3 (/ c 3)))) (define (squ-row n) (take 3 (drop (+ cs0 (* 9 (+ rs0 n))) field))) (define (sieve-nth l a) (cond ((null? l) a) (else (sieve-nth (drop 9 l) (cons (car l) a))))) (foldl (lambda (l a) (filter (lambda (x) (noelem x l)) a)) (quote (1 2 3 4 5 6 7 8 9)) (list (squ-row 0) (squ-row 1) (sieve-nth (drop c field) (squ-row 2)) (take 9 (drop (* 9 r) field)) nil)))

  (define (rep-by-ind i e l) (cond ((null? l) nil) ((= 0 i) (cons e (cdr l))) (else (cons (car l) (rep-by-ind (- i 1) e (cdr l))))))

  (define (go i min-i min-step-counts min-step-vars f)
    (cond ((null? f) (cond ((= min-step-counts 100) (cons field nil))
                           ((= min-step-counts 0) nil)
                           (else (map (lambda (v) (rep-by-ind min-i v field)) min-step-vars))))
          ((= 0 (car f)) (begin (define i-step-vars (step-vars i))
                                 (define i-step-counts (length i-step-vars))
                          (cond ((< i-step-counts min-step-counts)
                                 (go (+ i 1) i i-step-counts i-step-vars (cdr f)))
                                (else (go (+ i 1) min-i min-step-counts min-step-vars (cdr f))))))
          (else (go (+ i 1) min-i min-step-counts min-step-vars (cdr f)))))

  (go 0 0 100 0 field))

(define (solve-depth field)
  (define (go f) (define vars (steps f)) (cond ((noelem 0 f) f) ((null? vars) nil) (else (foldl (lambda (x a) (cond ((null? a) (go x)) (else a))) nil vars))))
  (go field))

(begin (display "Решение поиском в глубину:") (display "\n"))
(begin (display (showField (solve-depth field))) (display "\n"))

Конечно можно придраться, что одни define и никаких let, что (display «\n») а не (newline) и т.п. Но для экспресс-варианта имхо катит.

Ivana ★
(20.10.2016 21:51:09 +00:00) автор топика

Ответ на: комментарий от Ivana 20.10.2016 21:51:09 +00:00

Я лохЪ, / моего диалекта надо было заменить на quotient, теперь все работает правильно и даже поиск в ширину до кучи

(define (solve-wide field)
  (display "Количество анализируемых вариантов: ")
  (define (go vars)
    (display (string-append (number->string (length vars)) " "))
    (cond ((null? vars) nil)
          ((noelem 0 (car vars)) vars)
          (else (go (concat (map steps vars))))))
  (go (cons field nil)))

(begin (display "Поиск в ширину ....") (display "\n"))
(define solunions (solve-wide field))
(begin (display "\n") (display "Решения поиском в ширину:") (display "\n"))
(display (cond ((null? solunions) (string-append "Нет решений" "\n"))
               (else (foldl (lambda (x a) (string-append a (showField x) "\n")) "" solunions))))