Лабораторная работа №3

Дисциплина

Функциональное программирование

Выполнил

Лапин Алексей Александрович, P34102

Цель работы

Получить навыки работы с вводом/выводом, потоковой обработкой данных, командной строкой.

Требования

• обязательно должна быть реализована линейная интерполяция (отрезками, link);
• настройки алгоритма интерполяции и выводимых данных должны задаваться через аргументы командной строки:
  • какие алгоритмы использовать (в том числе два сразу);
  • частота дискретизации результирующих данных;
  • и т.п.;
• входные данные должны задаваться в текстовом формате на подобии ".csv" (к примеру x;y\n или x\ty\n) и подаваться на стандартный ввод, входные данные должны быть отсортированы по возрастанию x;
• выходные данные должны подаваться на стандартный вывод;
• программа должна работать в потоковом режиме (пример -- cat | grep 11), это значит, что при запуске программы она должна ожидать получения данных на стандартный ввод, и, по мере получения достаточного количества данных, должна выводить рассчитанные точки в стандартный вывод;

Приложение должно быть организовано следующим образом:

    +---------------------------+
    | обработка входного потока |
    +---------------------------+
            |
            | поток / список / последовательность точек
            v
    +-----------------------+      +------------------------------+
    | алгоритм интерполяции |<-----| генератор точек, для которых |
    +-----------------------+      | необходимо вычислить         |
            |                      | промежуточные значения       |
            |                      +------------------------------+
            |
            | поток / список / последовательность рассчитанных точек
            v
    +------------------------+
    | печать выходных данных |
    +------------------------+

Потоковый режим для алгоритмов, работающих с группой точек должен работать следующим образом:

o o o o o o . . x x x
  x x x . . o . . x x x
    x x x . . o . . x x x
      x x x . . o . . x x x
        x x x . . o . . x x x
          x x x . . o . . x x x
            x x x . . o o o o o o EOF

где:

• каждая строка -- окно данных, на основании которых производится расчёт алгоритма;
• строки сменяются по мере поступления в систему новых данных (старые данные удаляются из окна, новые -- добавляются);
• o -- рассчитанные данные, можно видеть:
  • большинство окон используется для расчёта всего одной точки, так как именно в "центре" результат наиболее точен;
  • первое и последнее окно используются для расчёта большого количества точек, так лучших данных для расчёта у нас не будет.
• . -- точки, задействованные в рассчете значения o.
• x -- точки, расчёт которых для "окон" не требуется.

Пример вычислений для шага 1.0 и функции sin(x):

Ввод первых двух точек (в данном примере X Y через пробел):
0 0.00
1.571 1

Вывод:
Линейная (идем от первой точки из введенных (0.00) с шагом 1, покрывая все введенные X (1.571 < 2)):
0.00    1.00    2.00
0.00    0.64    1.27

Ввод третьей точки:
3.142 0

Следующий вывод:
Линейная (идем от второй точки из введенных (1.571) с шагом 1, покрывая все введенные X (3.142 < 3.57)):
1.57    2.57    3.57
1.00    0.36    -0.27

Ввод четвертой точки:
4.712 -1

Следующий вывод:
Линейная (идем от третьей точки из введенных (3.142) с шагом 1, покрывая все введенные X (4.712 < 5.14)):
3.14    4.14    5.14
0.00    -0.64   -1.27

Лагранж (теперь количество введенных точек повзоляет его рассчитать, идем от первой точки (0.00) из введенных с шагом 1, покрывая все введенные X (4.712 < 5)):
0.00    1.00    2.00    3.00    4.00    5.00
0.00    0.97    0.84    0.12    -0.67   -1.03

Ввод пятой точки:
12.568  0

Следующий вывод:
Линейная (идем от четвертой точки из введенных (4.712) с шагом 1, покрывая все введенные X (12.568 < 12.71))):
4.71    5.71    6.71    7.71    8.71    9.71    10.71   11.71   12.71
-1.00   -0.87   -0.75   -0.62   -0.49   -0.36   -0.24   -0.11   0.02

Лагранж (идем от второй точки из введенных (1.571) с шагом 1, покрывая все введенные X (12.568 < 12.57))):
1.57    2.57    3.57    4.57    5.57    6.57    7.57    8.57    9.57    10.57   11.57   12.57
1.00    0.37    -0.28   -0.91   -1.49   -1.95   -2.26   -2.38   -2.25   -1.84   -1.11   0.00

И т.д.

Как видно из примера выше, окна для каждого метода двигаются по-разному. Для линейной окно начало сдвигаться уже при вводе третьей точки (т.к. для вычисления нужно всего две), в то время как для Лагранжа окно начало двигаться только когда была введена пятая точка (т.к. здесь для вычислений нужно больше точек).

Общие требования:

• программа должна быть реализована в функциональном стиле;
• ввод/вывод должен быть отделён от алгоритмов интерполяции;
• требуется использовать идиоматичный для технологии стиль программирования.

Ход работы

Структура проекта

├── README.md
├── src/
│   ├── core.clj
│   ├── input.clj
│   └── interpolation.clj
├── test/
│   └── interpolation_test.clj
│
├── .github/workflows/
│   └── clojure.yml
│
├── .gitingore 
├── tests.edn
└── deps.edn

Парсер аргументов командной строки.

Парсер аргументов командной строки реализован с помощью библиотеки clojure.tools.cli.

(def cli-options
  [["-a" "--algorithms ALGORITHMS" "Comma-separated list of interpolation algorithms (linear,lagrange)"
    :default []
    :parse-fn #(mapv str/lower-case (map str/trim (str/split % #",")))
    :validate [#(every? algorithms %) "Unknown algorithm specified"]]
   ["-s" "--step STEP" "Data sampling frequency"
    :parse-fn #(Double/parseDouble %)
    :validate [#(pos? %) "Step must be positive"]
    :default 1.0]
   ["-h" "--help"]])

В данном случае программа принимает на вход два аргумента:

• -a или --algorithms -- список алгоритмов, которые необходимо применить к входным данным;
• -s или --step -- шаг, с которым будут выводиться результаты.

Функция main

(defn -main [& args]
  (let [{:keys [algorithms step]} (parse-args args)]
    (try
      (let [points-seq (read-input-seq) 
            accumulated-points (reductions conj [] points-seq)]
        (doseq [points accumulated-points]
          (run-interpolation algorithms step points)))
      (catch Exception e
        (exit 1 (str "Error during interpolation: " (.getMessage e)))))))

Обработка входного потока.

(defn parse-point [input]
  (let [tokens (str/split input #"[,\t ;]+")]
    (if (str/blank? input) (do (println "Blank input received. Exiting.") (System/exit 0))
        (if (= (count tokens) 2)
          (let [[x y] tokens]
            (try
              (->Point (Double/parseDouble x) (Double/parseDouble y))
              (catch NumberFormatException e
                (throw (ex-info "Both coordinates must be valid numbers." {:input input} e)))))
          (throw (ex-info "Input must contain exactly two numerical values separated by comma, tab, space, or semicolon." {:input input}))))))


(defn read-input-seq
  "Lazily reads input lines from standard input and parses them into Point records."
  []
  (->> (line-seq (java.io.BufferedReader. *in*))
       (map str/trim)
       (map parse-point)
       (filter some?)))

Функция генерации точек, для которых будут вычисляться значения.

(defn generate-steps
  "Generates a sequence of steps from x-min to x-max with the specified step size."
  [x-min x-max step]
  (let [steps (take-while #(<= % x-max)
                           (iterate #(+ % step) x-min))
        last-step (+ (last steps) step)]
    (if (= (last steps) x-max)
      (vec steps)
      (conj (vec steps) last-step))))

Функция generate-steps генерирует последовательность значений x, с заданным шагом.

Алгоритмы интерполяции:

• Линейная интерполяция

(defn linear-interpolation
  "Performs linear interpolation between the last two points for a given x."
  [points x]
  (let [[p0 p1] (take-last 2 points)
        x0 (:x p0)
        x1 (:x p1)
        y0 (:y p0)
        y1 (:y p1)]
    (+ (* (- y1 y0) (/ (- x x0) (- x1 x0))) y0)))

• Интерполяция Лагранжа

(defn lagrange-basis
  "Calculates the Lagrange basis polynomial for a given point x."
  [points i x]
  (reduce
   (fn [acc j]
     (if (= i j)
       acc
       (/ (* acc (- x (:x (nth points j))))
          (- (:x (nth points i)) (:x (nth points j))))))
   1
   (range (count points))))

(defn lagrange-interpolation
  "Performs Lagrange interpolation between the last four points for a given x."
  [points x]
  (reduce
   (fn [acc i]
     (+ acc (* (lagrange-basis points i x) (:y (nth points i)))))
   0
   (range (count points))))

Вывод программы

> clojure -M -m core -a linear,lagrange
0 0
1.571 1
Linear interpolation result:
0.00    1.00    2.00
0.00    0.64    1.27
3.142 0
Linear interpolation result:
1.57    2.57    3.57
1.00    0.36    -0.27
4.712 -1
Linear interpolation result:
3.14    4.14    5.14
0.00    -0.64   -1.27
Lagrange interpolation result:
0.00    1.00    2.00    3.00    4.00    5.00
0.00    0.97    0.84    0.12    -0.67   -1.03
12.568  0
Linear interpolation result:
4.71    5.71    6.71    7.71    8.71    9.71    10.71   11.71   12.71
-1.00   -0.87   -0.75   -0.62   -0.49   -0.36   -0.24   -0.11   0.02
Lagrange interpolation result:
1.57    2.57    3.57    4.57    5.57    6.57    7.57    8.57    9.57    10.57   11.57  12.57
1.00    0.37    -0.28   -0.91   -1.49   -1.95   -2.26   -2.38   -2.25   -1.84   -1.11  0.00

Blank input received. Exiting.

> clojure -M -m core -a linear,lagrange -s 0.5
0 0
1 1
Linear interpolation result:
0.00    0.50    1.00
0.00    0.50    1.00
2 2
Linear interpolation result:
1.00    1.50    2.00
1.00    1.50    2.00
3 3
Linear interpolation result:
2.00    2.50    3.00
2.00    2.50    3.00
Lagrange interpolation result:
0.00    0.50    1.00    1.50    2.00    2.50    3.00
0.00    0.50    1.00    1.50    2.00    2.50    3.00
4 4
Linear interpolation result:
3.00    3.50    4.00
3.00    3.50    4.00
Lagrange interpolation result:
1.00    1.50    2.00    2.50    3.00    3.50    4.00
1.00    1.50    2.00    2.50    3.00    3.50    4.00

Blank input received. Exiting.

Заключение

В ходе выполнения лабораторной работы были достигнуты следующие результаты:

1. Реализована программа для интерполяции данных с поддержкой:

   • Линейной интерполяции
   • Интерполяции методом Лагранжа
   • Потоковой обработки входных данных
   • Настраиваемой частоты дискретизации

2. Получены практические навыки:

   • Работы с потоковым вводом/выводом в Clojure
   • Обработки аргументов командной строки
   • Реализации алгоритмов интерполяции в функциональном стиле

3. Программа полностью соответствует заданным требованиям и демонстрирует эффективное применение функционального подхода к решению поставленной задачи.