Реализация функции linspace, которая принимает в качестве аргументов Start, End и, при необходимости, Steps и выводит список равномерно распределенных (числовых) значений, где первым элементом является Start, а последним — End. Длина результирующего списка равна (Шаги + 1). Это похоже на MATLAB linspace.
Одна реализация на Haskell, другая на C. Угадайте, кто в миллиард раз быстрее. Нужна помощь в понимании того, что не так с кодом Haskell.
Обновление для людей, которые интересовались актуальной информацией.
Чтобы скомпилировать C: gcc -o linspace linspace.c
gcc: 12.2.0
Чтобы скомпилировать Haskell: ghc -O2 -o linspace linspace.hs
хх: 9.0.2
Для сравнения используйте shtime linspace 0 10 100000. Мои результаты следующие.
С (тест 1):
real 0m0.187s
user 0m0.076s
sys 0m0.012s
С (тест 2):
real 0m0.132s
user 0m0.068s
sys 0m0.010s
Всего два теста на C, потому что результат стабильно находится в пределах этих двух.
Хаскелл:
*takes forever*
Хаскелл-код.
{-# LANGUAGE BangPatterns #-}
import System.Environment
linspace :: Fractional a => a -> a -> Maybe Int -> [a]
linspace start end maybe = linspace' [] 0
where
stepCount =
case maybe of
Just i
| i > 0 -> i
| otherwise -> errorWithoutStackTrace "Number of steps must be > 0"
Nothing -> 100
stepSize = abs $ (end - start) / (fromIntegral stepCount)
linspace' !acc n
| n > stepCount = acc
| otherwise =
let !el = start + stepSize * (fromIntegral n)
in linspace' (acC++ [el]) (n + 1)
main = do
argv <- getArgs
let argc = length argv
if argc /= 2 && argc /= 3
then errorWithoutStackTrace "linspace <start> <end> [steps]"
else return ()
let start = read $ argv !! 0 :: Double
end = read $ argv !! 1 :: Double
steps =
if argc == 3
then Just $ read (argv !! 2) :: Maybe Int
else Nothing
putStrLn . show $ linspace start end steps
Код С.
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <math.h>
int
main (int argc, char **argv) {
if (argc != 3 && argc != 4) {
fprintf(stderr, "Usage: linspace <start> <end> [steps]\n");
return EXIT_FAILURE;
}
errno = 0;
double start, end;
int steps;
start = strtod(argv[1], NULL);
if (errno) {
perror(argv[1]);
return EXIT_FAILURE;
}
errno = 0;
end = strtod(argv[2], NULL);
if (errno) {
perror(argv[2]);
return EXIT_FAILURE;
}
errno = 0;
if (argc == 4) {
steps = (int) strtol(argv[3], NULL, 10);
if (errno) {
perror(argv[3]);
return EXIT_FAILURE;
} else if (steps <= 0) {
fprintf(stderr, "Number of steps must be > 0\n");
return EXIT_FAILURE;
}
} else
steps = 100;
double stepSize;
stepSize = fabs((start - end) / steps);
double *vals;
vals = malloc(sizeof(double) * (steps + 1));
for (int i = 0; i <= steps; i++) {
vals[i] = start + stepSize * i;
}
printf("[");
for (int i = 0; i <= steps; i++) {
if (i == steps)
printf("%f", vals[i]);
else
printf("%f, ", vals[i]);
}
printf("]\n");
}
Не обращайте внимания, что я принимаю абсолютные значения. Допустим, он не предназначен для использования с отрицательными значениями.
Обратите внимание, что вы измеряете не выполнение функции linspace, а время выполнения всего процесса и всех его операций ввода-вывода.
Это своего рода жестокая ирония в том, что вы позволяете программе C лениться (записывать результаты в стандартный вывод и забывать их), но требуете, чтобы программа Haskell была строгой (она должна материализовать весь список сразу, прежде чем она сможет что-либо сделать с ним). это).
Покажите эталон тоже. Как вы его скомпилировали, каким компилятором и т.д.
Создание списка путем рекурсивного добавления элемента, как в acC++ [el], неэффективно. Похоже, эту проблему можно решить с помощью понимания списка [ start + stepSize * fromIntegral i | i <- ... ], что проще, короче и эффективнее.





Основная проблема с вашим кодом Haskell заключается в следующем:
linspace' !acc n
| n > stepCount = acc
| otherwise =
let !el = start + stepSize * (fromIntegral n)
in linspace' (acC++ [el]) (n + 1)
Это O(n^2) алгоритм построения списка, поскольку каждое acC++ [e1] выражение требует прохождения всего acc списка, прежде чем синглтон [e1] можно будет добавить в конец.
Если вы удалите определение linspace' и замените первую строку linspace на:
linspace start end maybe = [start + fromIntegral n * stepSize | n <- [0..stepCount]]
вы обнаружите, что полученная программа на Haskell немного более конкурентоспособна по сравнению с версией C, возможно, примерно в 5 раз медленнее вместо миллиарда.
У меня это в 3-3,5 раза медленнее. Пытался сделать динамическое распределение массива на C, но на скорость это почти не повлияло. Я думаю, что списки Haskell просто безнадежны для такой работы.
Публикации такого типа больше подходят для codereview.stackexchange.com, поскольку они требуют открытой обратной связи, а не решения конкретной проблемы.