Несколько алгоритмов на трех языках программирования
Возьмём несколько простых задач и посмотрим, как с ними справляются якобы умерший lisp и современные python и ruby. Сравнивать будем скорость работы, а также компактность и читаемость кода. Тестируем на компьютере с процессором Intel Core i3 2.93 GHz и памятью 14 ГБ. Используем интерпретаторы Lisp SBCL 2.3.2, Python 3.12.4, Ruby 3.3.3. Автор сразу хочет заметить: он не пытался придумать или найти самые эффективные алгоритмы; целью являлось именно сравнение работы одинаковых алгоритмов на разных языках. Вот что получилось.
Действительные числа
Вычислить расстояние между двумя точками A(3,7) и B(-1,5) на плоскости.
Как известно, расстояние между двумя точками A(xa,ya) и B(xb,yb) вычисляется по формуле
Lisp:
;; distance.lisp
;; расстояние между двумя точками на плоскости
; для улучшения читаемости переопределим функцию возведения в степень expt
(defmacro ^ (val power)
`(expt ,val ,power))
(defun distance ()
(let ((a (list :x 3 :y 7))
(b (list :x -1 :y 5)))
(sqrt (+ (^ (- (getf b :x) (getf a :x)) 2)
(^ (- (getf b :y) (getf a :y)) 2)))))Координаты точек A и B представлены в виде списков с ключами, что делает удобным их извлечение из списков с помощью функции getf. Далее переменным a и b присваиваются значения и вычисляется расстояние.
Результат: 4.472136
Python:
# distance.py
# расстояние между двумя точками на плоскости
import math
def distance():
a = {'x': 3, 'y': 7}
b = {'x': -1, 'y': 5}
return math.sqrt((b['x'] - a['x'])**2 + (b['y'] - a['y'])**2)
print (distance())Результат: 4.47213595499958
В первой строке программы импортируется математическая библиотека, чтобы стала доступной функция извлечения квадратного корня sqrt. Координаты точек A и B – хэши с символьными ключами ‘x’ и ‘y’, что позволяет извлекать значения по этим ключам.
Ruby:
# distance.rb
# расстояние между двумя точками на плоскости
def distance
a, b = {x: 3, y: 7}, {x: -1, y: 5}
Math.sqrt((b[:x] - a[:x])**2 + (b[:y] - a[:y])**2)
end
puts distanceРезультат: 4.47213595499958
Для координат используются хэши с символьными ключами. В первой строке функции переменным a и b присваиваются значения, во второй вычисляется расстояние.
На взгляд автора, после применения макроса самый читаемый код получился на Лиспе. Точность вывода у Лиспа меньше, но это только вывод. Внутреннее представление числа обеспечивает достаточную точность.
Большие целые числа
Напишем программу, печатающую сумму первых n членов начинающейся с единицы геометрической прогрессии со знаменателем q (2).
Решение основано на использовании известной формулы для суммы геометрической прогрессии:
При q = 2 и n = 64 получим знаменитое «шахматное» число 18446744073709551615.
Lisp:
(defun sum-g (n q)
(/ (- (expt q n) 1) (- q 1)))Python:
def sum_g (n, q):
return (q**n - 1) // (q -1)
print (sum_g (64, 2))Ruby:
def sum_g (n, q)
(q**n - 1) / (q -1)
end
print (sum_g 64, 2)Все три системы работают с большими целыми числами. Самый компактный и выразительный код - у старика Лиспа.
Большие массивы
Сформируем массив простых чисел по алгоритму Эратосфена для n = 10 млн чисел. Алгоритм («Решето Эратосфена») следующий: формируем массив с числами от 2 до n. Затем удаляем из этого массива все числа, кратные сначала первому числу массива, кроме самого числа, затем второму и т. д. до конца массива. Таким образом, в массиве останутся только числа, кратные самим себе и единице. Алгоритм частично взят из (2).
Lisp:
; создаем массив a с числами от 2 до n
(setf a (make-array (1+ n)))
(setf (aref a 0) nil)
(setf (aref a 1) nil)
(loop for i from 2 to n do
(setf (aref a i) i))
; удаляем из него все составные числа
(do ((i 2 (1+ i)))
(( > i (floor (sqrt n))))
(when (not (aref a i))
(go end))
(setf j (* i i))
(loop while (<= j n) do
(setf (aref a j) nil)
(setf j (+ i j)))
end)
(setf a (remove nil a))
a)В Лиспе в цикле do нет некоторых возможностей, поэтому для продолжения цикла приходится применить переход на метку.
Время работы – 6 сек
Python:
import array, math
def primes (n):
a = [None, None]
for i in range(2,n+1):
a.append(i)
for i in range(2, int(math.sqrt(n))+1):
if not a[i]:
continue
j = i*i
while j <= n:
a[j] = None
j += i
a = [i for i in a if i] # удалим None
print (a)
primes (10000000)Время работы - 7 сек
Ruby:
n = Integer(ARGV[0])
sieve = [nil, nil]
(2..n).each {|i| sieve << i}
for i in 2 .. Math.sqrt(n)
next if !sieve[i]
(i*i).step(n,i) { |j| sieve[j]=nil}
end
p sieve.compact Время работы: 5 сек.
Производительность систем примерно одинаковая, но по выразительности и компактности кода с большим отрывом лидирует Руби. Можно сказать, код на Руби здесь выглядит просто изящно.
Рекурсия
Будем считать сороковое число Фибоначчи по формуле:
F(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2)
Lisp:
(defun fib (n)
(cond ((< n 2) n)
(t(+ (fib (- n 1)) (fib (- n 2)))))) Время расчета 5 сек
Python:
def fib (n):
return n if n < 2 else fib(n-1) + fib(n-2) Время расчета 39 сек.
Ruby:
def fib (n)
n < 2? n : fib(n-1) + fib(n-2)
end
def fib (n)
n < 2? n : fib(n-1) + fib(n-2)
endВремя 18 сек.
В этом рекурсивном алгоритме самым быстрым оказался Lisp; Ruby на уровне середнячка, а Python безнадежно отстает. Код одинаково компактен и читается хорошо на всех трех системах.
Резюмируя наше небольшое исследование, можно сказать, что все три системы имеют право на существование, но по мнению автора, Руби по таким параметрам, как компактность, читаемость кода, скорость работы, немного опережает соперников. Lisp практически от него не отстает, Python же оказался на почетном третьем месте.
Литература:
Симдянов И. В. Самоучитель Ruby. — СПб.: БХВ-Петербург, 2020
Е. А. Роганов, Н. А. Роганова Программирование на языке Ruby. - МГИУ, Москва, 2008
Комментарии (13)
aelaa
30.09.2024 11:25Вопросов к автору осталось очень много...
Руби или Ruby?
Какой Ruby (стандартный/mRuby/JRuby/IronRuby/экзотика)? Какая версия? На какой платформе?Какой Python (CPython/PyPy/Jython/экзотика)? Какая версия? На какой платформе?Какой Lisp (тут я даже перечислять не буду)? Какая версия? На какой платформе?
Если уж сравниваете производительность - будьте добры полную информацию об используемом окружении.(UPD - информация появилась, претензия снимается)Это еще закрывая глаза на особенности реализации структур данных в каждом. В Ruby в первом примере можно было бы массив вместо хэша взять например (и скорее всего это ближе по реализации к лисповому варианту), результат будет отличаться.
Можно сказать, код на Руби здесь выглядит просто изящно
Закроем глаза на странную реализацию заполнения массива (все-таки была цель сравнить с аналогом на лиспе), но полторы страницы исправлений для 8 строчек кода от Rubocop`а (линтер для Ruby) намекают, что не такой уж он и изящный. После него (и с парой мелких исправлений) выглядит куда читабельнее:
n = ARGV[0].to_i sieve = [nil, nil] + (2..n).to_a (2..Math.sqrt(n)).each do |i| next if sieve[i].nil? (i * i).step(n, i) { |j| sieve[j] = nil } end p sieve.compact
vsting
30.09.2024 11:25Можно еще чуть-чуть подсахорить пронумерованным параметром "_1":
(i * i).step(n, i) { sieve[_1] = nil }
mikleh
30.09.2024 11:25+8>>На взгляд автора, после применения макроса самый читаемый код получился на Лиспе.
Субъективность автора переходит все мыслимые границы. Любые стековые нотациии не могут быть более читаемыми для homo sapiens чем естественный порядок записи математических действий. Тысячи лет развития математики тому доказательство.
Andrey_Solomatin
30.09.2024 11:25Резюмируя наше небольшое исследование, можно сказать, что все три системы имеют право на существование
В этом исследовании нет смысла. Эти параметры ничего не решают.
Внешние библиотеки решают. В Питоне с большими данными, как в примере, никто не работает. В основном используют сторонние библиотеки.
atues
30.09.2024 11:25+3Отвлекаясь от некоторых справедливых замечаний, высказанных в комментариях, мне стало приятно оттого, что ламповый lisp вполне на высоте. Конечно, можно критиковать автора и за выбор алгоритмов, и за их реализацию. Но это, как мне кажется, далеко не главное в статье. Спасибо, порадовали старика
saratoga8
30.09.2024 11:25Спасибо за статью
Заголовок статьи не говорит на основе чего сравниваются языки. Судя по содержанию, для сравнения используются только мат. вычисления. Возникает вопрос - почему именно они?
Beholder
30.09.2024 11:25По нынешним временам тут особенно хвалиться нечем.
Kotlin:
fun sqr(x: Double) = x * x fun distance(a: Point2D, b: Point2D): Double = sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)) fun sumG(q: Long, n: Int): BigInteger { val bq = q.toBigInteger() return (bq.pow(n) - BigInteger.ONE) / (bq - BigInteger.ONE) } fun fib(n: Int): BigInteger = if (n < 2) BigInteger.ONE else fib(n - 1) + fib(n - 2) // Среднее время fib(40): Python = 15s, JVM = 2s fun intSqrt(n: Int) = sqrt(n.toFloat()).toInt() fun primes(n: Int): BitSet { val bits = BitSet(n + 1).also { it.set(1, n + 1) } for (i in 2 .. intSqrt(n)) { if (!bits[i]) { continue } for (j in i * i .. n step i) { bits.clear(j) } } return bits } // Среднее время primes(1_000_000): Python = 200ms, JVM = 5ms
AcckiyGerman
30.09.2024 11:25+1Автору спасибо за исследование, но позволю себе немного критики:
1. Польская нотация
действительно красива для коротких формул. Но начиная от среднего размера от скобочек LISP рябит в глазах. Впрочем для сложных формул лучше MATLAB использовать, ибо матформулы почти на все языки программирования переводятся некрасиво.Вот, кстати, решето Эрастрофена в Матлаб:
clear, clc a = 1:10000000; for i = 2:length(a); % пробегаем по числам начиная с 2 if a(i)~=0 % если i-й элемент не обнулен a(2*i:i:end) = 0; % обнуляем каждый i-й элементы end end a(a==0) = [] % удаляем нули и отображем результатПо-моему очень красиво.
2. Знай свой инструмент
Автор использует устаревший 2-й питон да и тот плохо знает:в питоне тоже можно объявлять несколько переменных в одной строке:
a, b = {x: 3, y: 7}, {x: -1, y: 5}Решето Эрастрофена это же множество, а множества встроены в Python:
def primes(n): sieve = set(range(2, n+1)) while sieve: # пока в решете есть числа prime = min(sieve) # выбираем минимальное (всегда будет простым в нашем алгоритме) print(prime, end = "\t") sieve -= set(range(prime, n+1, prime)) # выкидываем кратные текущему простомуИ алгоритм занимает 4 строки вместо 11.
даже без множеств код автора можно значительно сократить, например
a = [None, None] + list(range(2, n+1))вместо
a = [None, None] for i in range(2,n+1): a.append(i)и так далее.
Вывод
Lisp конечно красив, Ruby тоже супер, но выразительность Python не уступает этим двоим.
IisNuINu
30.09.2024 11:25А вы можете сравнить сколько времени работает ваш алгоритм с использованием множеств, и алгоритм автора?! На тех же самых 10 миллионах значений.
IisNuINu
30.09.2024 11:25+1Не знаю как в других языках, а в Лиспе давно придумали Структуры, поэтому пользоваться списками, как бы имитируя структуры, не правильно, они там есть, пользуйтесь. Поэтому первую функцию на Лиспе я бы написал так:
(defstruct point x y) (defun distance (a b) (sqrt (+ (expt (- (point-x b) (point-x a)) 2) (expt (- (point-y b) (point-y a)) 2))))Если брать более экзотичные лиспы, например Script-fu из GIMP, то этот же код я бы смог написать в 3 различных синтаксисах, тоже с применением структур, так же как в лисп:
(struct point (x y)) (define-m (distance0 a b) (sqrt (+ (expt (- (point-x b) (point-x a)) 2) (expt (- (point-y b) (point-y a)) 2)))) (distance0 (point! 3 7) (point! -1 5)) ;;4,472135955.0с применением dot синтаксиса
(define-m (distance1 a b) (with-stru (a point b point) (sqrt (+ (expt (- b.x a.x) 2) (expt (- b.y a.y) 2))))) (distance1 (point! 3 7) (point! -1 5)) ;;4,472135955.0с применением макроса и дот синтаксиса.
(define-macro (^2- . param) `(expt (- ,@param) 2)) (define-m (distance2 a b) (with-stru (a point b point) (sqrt (+ (^2- b.x a.x) (^2- b.y a.y))))) (distance2 (point! 3 7) (point! -1 5)) ;;4,472135955.0
IisNuINu
30.09.2024 11:25На мой взгляд можно подкорректировать Лисп код, в функции решета эратосфена. Например, мне кажется что переход там совершенно не нужен. Для написания этой функции я использую два макроса:
(defmacro while (test &body body) `(do () ((not ,test)) ,@body)) (defmacro for ((var start stop) &body body) (let ((gstop (gensym))) `(do ((,var ,start (1+ ,var)) (,gstop ,stop)) ((> ,var ,gstop)) ,@body))) ;;из книги OnLisp Пола Грэма.и собственно код:
(defun eratosfen (n) (let ((a (make-array (1+ n)))) (setf (aref a 0) nil) (setf (aref a 1) nil) (for (i 2 n) (setf (aref a i) i)) (for (i 2 (floor (sqrt n))) (unless (not (aref a i)) (let ((j (* i i))) (while (<= j n) (setf (aref a j) nil) (setf j (+ j i)))))) (remove nil a))) (eratosfen 10) ;;#(2 3 5 7)собственно и его можно улучшить. Если изменить макрос for, так чтобы он принимал шаг цикла, например так:
(defmacro for ((var start stop . step) &body body) (let ((gstop (gensym)) (step (if (null step) 1 (car step)))) `(do ((,var ,start (+ ,var ,step)) (,gstop ,stop)) ((> ,var ,gstop)) ,@body)))теперь можно написать более изящный код:
(defun eratosfen (n) (let ((a (make-array (1+ n)))) (setf (aref a 0) nil) (setf (aref a 1) nil) (for (i 2 n) (setf (aref a i) i)) (for (i 2 (floor (sqrt n))) (unless (not (aref a i)) (for (j (* i i) n i) (setf (aref a j) nil)))) (remove nil a)))И на мой взгляд этот код не уступит по краткости и ясности ни котлину, ни руби, ни питону.
IisNuINu
30.09.2024 11:25+1А хотите я вам покажу Лисп МАГИЮ!?! Вы такого нигде не видели, это точно! В предыдущем посте я привёл весьма изящный код, и каждому лисперу он понятен, но вот постоянные остылки (aref a i) для люде незнакомых с лиспом режут глаз, им гораздо привычнее a[i]. Но такого в лиспе небывает! Я вам покжу код, который это сможет сделать!
(defun eratosfen2 (n) (let ((a (make-array (1+ n)))) (with-arr (setf a[0] nil) (setf a[1] nil) (for (i 2 n) (setf a[i] i)) (for (i 2 (floor (sqrt n))) (unless (not a[i]) (for (j (* i i) n i) (setf a[j] nil)))) (remove nil a))))да ну скажете, это не будет работать. А вот смотрите макрос и вспомогательные функции:
(defmacro with-arr (&body body) (let ((new-body (tree-expr-replace-aref body))) `(progn ,@new-body) )) (defun tree-expr-replace-aref (expr) (let ((fd '())) (cond ((null expr) '()) ((and (symbolp expr) (progn (setf fd (split-arrayindex-symbol expr)) ;;(prn "fd: " fd "\n") fd)) ;;(list (field-def-name-get fd) (field-def-var fd))) (list 'aref (tree-expr-replace-aref (car fd)) (cdr fd))) ((listp expr) ;;(prn "TR-REPL: find set!: " fd "\n") (cons (tree-expr-replace-aref (car expr)) (tree-expr-replace-aref (cdr expr)))) (t expr)))) (defun split-arrayindex-symbol (symb) (let* ((str (symbol-name symb)) (len (length str)) (last (1- len))) (if (and (> len 3) (char= (char str last) #\])) (let ((pos (string-at-end str #\[))) (format nil "pos: ~A~%" pos) (if (and pos (> pos 0) (< pos last)) (cons (read-from-string str nil nil :start 0 :end pos) (read-from-string str nil nil :start (+ pos 1) :end last)) nil)) nil))) (defun string-at-end (str ch) (let ((last-ind (- (length str) 1))) (do ((i last-ind (- i 1))) ((or (< i 0) (char= (char str i) ch)) (if (< i 0) nil i)))))И ВСЁ! синтаксис который я изобрёл и показал выше будет рабоать! Я ведь уже показывал фокус с дот синтаксисом, и никто не обратил внимания на него, а ведь такого синтаксиса НЕТ! я его сам придумал и реализовал. И этот синтаксис я придумал и реализовал. И ВЫ СМОЖЕТЕ!
kamaz1
"У меня для вас посылка, но я вам ее не отдам" (c)
Лисп же позволяет вывести число с большей точностью, раз хранит его с большей, позволяет же? А то можно и до "4" сократить, зачем цифрами голову забивать.
После первых двух примеров, я удивлен почему не лисп назван самым простым и изящным. Python и Ruby вобще не читаемы же, покажите эти куски кода любому программисту, и он ничего в питоне и руби не поймет в отличии от лиспа.