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

Узнай цену своей работы

Формулировка задачи:

Началось все с одной несложной задачки - Каково первое треугольное число, у которого более пятисот делителей? Я написал наивный алгоритм на Haskell, он выполнялся полторы секунды. Ограничил типы целых до Int - время выполнения снизилось до 0.3 сек - столько же, сколько аналогичный алгоритм на C#, реализованный через циклы. Потом я буквально перевел этот алгоритм на свой Liscript (реализация на Java), рекурсивный эвалюатор считает 40 секунд, итеративный - почти 4 минуты. Понятно - интерпретация без особых оптимизаций, в итеративном варианте еще и с велосипедным стеком вместо системного. Стало мне немного грустно, и захотелось попытаться ускорить безобразие . Радикальным методом - через компиляцию (трансляцию) кода Liscript в код на каком-нибудь другом языке. И я внезапно вспомнил, что вдохновлялся SICP-ом и вообще по семантике мой диалект во многом похож на Scheme, и будет достаточно несложно сделать трансляцию и сравнить время выполнения. Досыпав вдвое больше скобок в свой исходный код я получил работающий аналог:
;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))
И был удивлен тем, что в онлайн IDE этот код не укладывается в максимальные 5 секунд. Сколько он считает, я так и не узнал, потому что не ставил себе локально Scheme. Расчет укладывается в 5 секунд при снижении параметра с 500 до 150, но при таком значении и мой интерпретатор быстро считает В связи с чем возникает много вопросов. Может я неоптимально с точки зрения Scheme написал код алгоритма? И он медленно выполняется из-за этого? Да, у меня 2 раза умножение вместо локальной переменной, но не думаю, что это так критично. Или Scheme сам по себе небыстрый? Если так, тогда имхо не имеет смысла писать транслятор в него. Или попробовать Racket - они вроде семантически похожи? Или другой какой-нибудь функциональный диалект Lisp-1 с мутабельным окружением?
UPD chiken реализация считает заметно быстрее guile, хотя при параметре 500 также не укладывается в 5 секунд, хотя укладывается при 300.
UPD продолжаю ничего не понимать. Здесь https://repl.it/languages/scheme 150 считает десятки секунд, а здесь https://www.tutorialspoint.com/execute_scheme_online.php 500 несколько секунд... Там что в одних местах компиляторы а в других интерпретаторы?
Воистину. В самом тормозном из найденных онлайн-вариантов написано
BiwaScheme Interpreter version 0.6.4 Copyright (C) 2007-2014 Yutaka HARA and the BiwaScheme team
Собственно, тогда вопрос - если готов скачать и локально поиграться, то что посоветуете?

Решение задачи: «Scheme - скорость выполнения кода»

textual
Листинг программы
Язык: racket, with debugging; memory limit: 128 MB.
76576500
cpu time: 3682 real time: 3684 gc time: 15

Язык: racket [выбранный]; memory limit: 128 MB.
76576500
cpu time: 764 real time: 780 gc time: 0

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 4.071 из 5