Главная

Сравним ruby, lisp и python

2024-09-30 в 11:15, admin, рубрики: python, ruby, большие целые числа, рекурсия, решето Эратосфена

Несколько алгоритмов на трех языках программирования

Возьмём несколько простых задач и посмотрим, как с ними справляются якобы умерший 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(x_a,y_a) и B(x_b,y_b) вычисляется по формуле

$sqrt{(x_a-x_b)^2+(y_a-y_b)^2}$

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).
Решение основано на использовании известной формулы для суммы геометрической прогрессии:

$S=frac{q^n - 1}{q - 1}$

При 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 же оказался на почетном третьем месте.

Литература: