Производительность Haskell и C в функции linspace

Реализация функции 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");
}

Не обращайте внимания, что я принимаю абсолютные значения. Допустим, он не предназначен для использования с отрицательными значениями.

Публикации такого типа больше подходят для codereview.stackexchange.com, поскольку они требуют открытой обратной связи, а не решения конкретной проблемы.

Noughtmare 07.10.2023 17:35

Обратите внимание, что вы измеряете не выполнение функции linspace, а время выполнения всего процесса и всех его операций ввода-вывода.

tstanisl 07.10.2023 17:50

Это своего рода жестокая ирония в том, что вы позволяете программе C лениться (записывать результаты в стандартный вывод и забывать их), но требуете, чтобы программа Haskell была строгой (она должна материализовать весь список сразу, прежде чем она сможет что-либо сделать с ним). это).

amalloy 07.10.2023 17:59

Покажите эталон тоже. Как вы его скомпилировали, каким компилятором и т.д.

Thomas M. DuBuisson 07.10.2023 18:35

Создание списка путем рекурсивного добавления элемента, как в acC++ [el], неэффективно. Похоже, эту проблему можно решить с помощью понимания списка [ start + stepSize * fromIntegral i | i <- ... ], что проще, короче и эффективнее.

chi 07.10.2023 19:27
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
5
106
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Основная проблема с вашим кодом 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 просто безнадежны для такой работы.

EmErAJID 08.10.2023 08:06

Другие вопросы по теме