Разработка на коленке

"тут должна быть красивая цитата о программировании"

Умножение матриц на OCaml (с модулями)

2016-08-19 01:53

У меня новое развлечение - курс Нейронные сети. Сейчас у меня ликбез по линейной алгебре, а конкретно - умножение матриц. В одном уроке нужно было перемножить матрицы, что мне показалось неплохой возможностью написать кусок кода на OCaml.

Задача

Перемножить матрицы

    [1 0 0 0]   [1  2  3]   [3 0 0]
2 * [0 1 0 0] * [5  6  7] * [0 3 0] =
    [0 0 1 0]   [9 10 11]   [0 0 3]
    [0 0 0 1]   [4  8 12]

Решение

В этот раз мне хотелось сделать отдельный модуль с сигнатурой и без конкретных типов в сигнатурах.

matrix.mli

open Core.Std

type t

val of_list: int list list -> t

val of_array: int array array -> t

val mult_to_matrix: t -> t -> t

val mult_to_int: t -> int -> t

val to_string: t -> string

matrix.ml

open Core.Std


type t = int array array


let of_array a =
    Array.map a ~f: Array.copy


let of_list lst =
    List.to_array (List.map lst ~f: List.to_array)


let mult_to_matrix m1 m2 =
    let dimx = Array.length m1 in
    let dimy = Array.length m2.(0) in

    let vector_length = Array.length m2 in
    let mult_lines line_number column_number =
        List.range 0 vector_length
        |> List.map ~f:(fun k -> m1.(line_number).(k) * m2.(k).(column_number))
        |> List.reduce ~f:(+)
        |> Option.value ~default:0
    in

    let product = Array.make_matrix ~dimx ~dimy 0 in
    for i = 0 to dimx - 1 do
        for j = 0 to dimy - 1 do
            product.(i).(j) <- mult_lines i j
        done;
    done;

    product


let mult_to_int matrix multiplier =
    matrix |> Array.map ~f:(fun line -> Array.map line ~f:(fun i -> i * multiplier))


let to_string matrix =
    Array.map matrix ~f:(fun line ->
        Array.map line ~f:Int.to_string |> String.concat_array ~sep:", "
    ) |> String.concat_array ~sep: "; "

product.ml

open Core.Std


let () =
    let a = Matrix.of_array [|
        [|1; 0; 0; 0|];
        [|0; 1; 0; 0|];
        [|0; 0; 1; 0|];
        [|0; 0; 0; 1|];
    |] in
    let b = Matrix.of_list [
        [1; 2;  3];
        [5; 6;  7];
        [9; 10; 11];
        [4; 8;  12]
    ] in
    let c = Matrix.of_list [
        [3; 0; 0];
        [0; 3; 0];
        [0; 0; 3];
    ] in

    Matrix.mult_to_int (Matrix.mult_to_matrix (Matrix.mult_to_matrix a b) c) 2
    |> Matrix.to_string
    |> printf "%s\n"

Заключение

Результат прошёл проверку задания, хотя решить задачу вручную на листе бумаги было бы гораздо быстрее, потому что достаточно было из третьей матрицы сделать единичную, а потом умножить матрицу b на 6. Но сейчас мне важно практиковаться в разработке на OCaml.

Записи процесса разработки в этот раз не будет, во-первых, разработка была не в один присест, а во-вторых, ничего интересного там нет.

Быстрая сортировка (quicksort) на OCaml

2016-08-08 18:02

Дошёл черёд до реализации быстрой сортировки на OCaml, пока я слушаю курс по алгоритмам (Algorithmic Toolbox). Поскольку основная цель - практика программирования на OCaml, то этот раз я не стал заниматься разработкой partion с ручным перемещением элементов списка, а заменил её двумя вызовами List.filter. Код для тестирования взял из сортировки слиянием, а функцию генерации тестовых данных сделал как в сортировке подсчётом, чтобы в список входили отрицательные числа.

Исходный код:

open Core.Std


let rec quicksort lst =
    let open List in
    match lst with
    | [] | [_] -> lst
    | hd :: tl ->
            let left = quicksort (filter tl (fun i -> i <= hd)) in
            let right = quicksort (filter tl (fun i -> i > hd)) in
            concat [left; [hd]; right]


let rec create_test_data = function
    | 0 -> []
    | size -> (Random.int 100) - 50 :: create_test_data (size - 1)


let render color text =
    sprintf "\027[38;5;%dm%s\027[0m\n" color text


let render_success data qs_sorted sorted =
    let color = 2 in
    let message = "Ok" in
    if List.length data < 20 then
        [
            message;
            "Data: " ^ (List.to_string data ~f:string_of_int);
            "Quicksort: " ^ (List.to_string qs_sorted ~f:string_of_int);
            "List sort: " ^ (List.to_string sorted ~f:string_of_int);
        ] |> List.map ~f:(fun str -> render color str) |> String.concat ~sep:""
    else
        render color (message ^ " size: " ^ (string_of_int (List.length data)))


let render_error data qs_sorted sorted =
    let color = 1 in
    let message = "Error"in
    [
        message;
        "Data: " ^ (List.to_string data ~f:string_of_int);
        "Quicksort: " ^ (List.to_string qs_sorted ~f:string_of_int);
        "List sort: " ^ (List.to_string sorted ~f:string_of_int);
    ] |> List.map ~f:(fun str -> render color str) |> String.concat ~sep:""



let rec test size =
    let data = create_test_data size in
    let qs_sorted = quicksort data in
    let sorted = List.sort data ~cmp:compare in
    match compare sorted qs_sorted with
    | 0 -> (
        printf "%s%!" (render_success data qs_sorted sorted);
        if size > 0 then
            test (size - 1)
    )
    | _ -> printf "%s%!" (render_error data qs_sorted sorted)


let () =
    printf "Let's begin\n";
    test 1000

Quicksort3

Ещё сделал quicksort3, где список разбивается на три части. С практической точки зрения этот код скорее бесполезен, но для тренировки разработки на OCaml подойдёт.

open Core.Std


let rec quicksort3 lst =
    let open List in
    match lst with
    | [] | [_] -> lst
    | hd :: _ ->
        match map [(<); (=); (>)] (fun f -> filter lst (fun i -> f i hd)) with
        | [l; c; r] -> concat [quicksort3 l; c; quicksort3 r]
        | _ -> assert false

Сортировка подсчётом на OCaml и на Python 3

2016-08-04 22:20

Сортировку подсчётом решил сделать и на Python и на OCaml. Просто было интересно, записать процесс работы и посмотреть потом со стороны.

Python

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

В записи между 3:36 и 5:36 пауза, мне нужно было отойти от комьютера, поэтому там экран статичен.

А ещё заметил, что из-за того, что пишу этот код сразу на двух языках, то немного путаюсь. Например, попытался вставить в питоновском коде else if, вместо elif.

Полный исходник:

#!/usr/bin/env python
# -*- coding: utf-8 -*-


import random


def counting_sort(data, min_number, max_number):
    n = max_number - min_number + 1  # [0, n]
    counters = [0] * n

    for v in data:
        counters[v - min_number] += 1

    result = []
    for v, count in enumerate(counters):
        result.extend([v + min_number] * count)

    return result


def create_test_data(size):
    min_number = random.randint(-10, 10)
    max_number = random.randint(min_number + 1, 15)
    data = [random.randint(min_number, max_number) for _ in range(size)]
    return data, min_number, max_number


def main():
    for size in range(10):
        data, min_number, max_number = create_test_data(size)
        sorted_by_counting_sort = counting_sort(data, min_number, max_number)
        sorted_by_sorted = sorted(data)
        if sorted_by_counting_sort != sorted_by_sorted:
            print('Error!')
            print('Test data:     {}'.format(data))
            print('Counting sort: {}'.format(sorted_by_counting_sort))
            print('Sorted:        {}'.format(sorted_by_sorted))
            break
        elif size < 15:
            print('Ok for size {}'.format(size))
            print('Test data:     {}'.format(data))
            print('Counting sort: {}'.format(sorted_by_counting_sort))
            print()
    else:
        print('Ok!')


if __name__ == '__main__':
    main()

OCaml

Потом была очередь разработки алгоритма на OCaml. Здесь я решил, что не честно ждать от фукнции генерации тестовых данных, чтобы она возвращала минимальный и максимальный элементы. Поэтому поиск этих элементов вынес в саму функцию сортировки подсчётом. Таким образом должно было получиться O(3*n), то есть O(n).

Попытка записать и загрузить процесс разработки закончилась ошибкой:

~ Upload failed: Sorry, your asciicast is too big.
~ Retry later by running: asciinema upload ./tmp9e2k0bwd-asciinema.json

Поэтому просто исходник:

open Core.Std


let counting_sort = function
    | [] -> []
    | data -> (
        let min_elt = match List.min_elt data compare with
        | Some i -> i
        | None -> assert false
        in
        let max_elt = match List.max_elt data compare with
        | Some i -> i
        | None -> assert false
        in
        let n = max_elt - min_elt + 1 in
        let counters = Array.create n 0 in

        let rec count = function
        | [] -> ()
        | h :: tl -> (
            counters.(h - min_elt) <- (counters.(h - min_elt) + 1);
            count tl;
        )
        in

        count data;

        Array.foldi counters ~init:[] ~f:(fun i accum v -> accum @ Array.to_list (Array.create v (i + min_elt)))
    )


let rec create_test_data = function
    | 0 -> []
    | size -> (Random.int 10) - 5 :: create_test_data (size - 1)


let () =
    for i = 0 to 10 do
        let data = create_test_data i in
        let sorted_by_count = counting_sort data in
        let sorted_by_std = List.sort data ~cmp:compare in
        if sorted_by_count <> sorted_by_std then
            (
                printf "Error\n";
                data |> List.to_string ~f:string_of_int |> printf "Data: %s\n";
                sorted_by_count |> List.to_string ~f:string_of_int |> printf "Count: %s\n";
                sorted_by_std |> List.to_string ~f:string_of_int |> printf "Std: %s\n\n";
            )
        else
            (
                printf "Ok\n";
                data |> List.to_string ~f:string_of_int |> printf "Data:  %s\n";
                sorted_by_count |> List.to_string ~f:string_of_int |> printf "Count: %s\n";
                sorted_by_std |> List.to_string ~f:string_of_int |> printf "Std:   %s\n\n";
            )
    done

Заключение

Программировать на OCaml мне по-прежнему сложно. Жаль, что запись не сохранилась. Её большой размер обусловлен постоянными переключенями между vim и utop, где я смотрел сигнатуры функций и писал простой тестовый код.

Ещё я понял, что тестирующий код лучше помещять в рекурсивную функцию (с хвостовой рекурсией), если нужно прерывать тест после нахождения ошибки, так как в OCaml нет break, чтобы прервать выполнение цикла.

Сортировка слиянием на OCaml (с хвостовой рекурсией)

2016-08-03 18:57

Продолжаю слушать курс по алгоритмам на coursera. В этот раз в лекции объяснялся принцип работы сортировки слиянием. Мне, как обычно, стало интересно, как я смогу реализовать этот алгоритм на OCaml.

В этот раз условия такие:

  • на вход и выход - списки
  • своя сортировка в функциональном стиле
  • постараться использовать хвостовую рекурсию там, где получится
  • проверочная функция - List.sort
  • подсветка сообщений об ошибках

Используя стандартную функцию, как проверочную я мог заняться разработкой тестового кода. Вообще-то, я мог взять тесты из реализации сортировки выбором, но моя цель - как можно больше практиковаться в программировании на OCaml, поэтому для меня лучше каждый раз заново писать код, пытаясь сделать его лучше, чем прошлый раз.

В этот раз я записал процесс разработки в asciinema.org. Процесс разработки занял около 40 минут, и это при том, что я уже знал, что хочу написать. Ещё я довольно долго пытался объединить две операции в блок if .. then внутри функции тестирования, чтобы продолжать тесты только если не было ошибки, но так и не вспомнил, как это сделать, поэтому переписал кусок кода на match .. with

Полный исходник выглядит так:

open Core.Std


let merge_sort list =
    let rec merge accum a b =
        match a, b with
        | ([], []) -> accum
        | ([], h :: tl) -> List.rev accum @ b
        | (h :: tl, []) -> List.rev accum @ a
        | (h :: tl, h' :: tl') -> (
            match compare h h' with
            | -1 -> merge (h :: accum) tl b
            | _ -> merge (h' :: accum) a tl'
        )
    in

    let rec sort list =
        let length = List.length list in
        match length with
        | 0 | 1 -> list
        | _ -> (
            let m = length / 2 in
            let a', b' = List.split_n list m in
            merge [] (sort a') (sort b')
        )
    in

    sort list


let create_test_data = function
    | 0 -> []
    | size -> List.init size ~f:(fun i -> Random.int 10)


let render color text =
    sprintf "\027[38;5;%dm%s\027[0m\n" color text


let render_success test_data sorted_by_merge sorted_by_std =
    let color = 2 in
    let message = "Ok" in
    if List.length test_data < 20 then
        [
            message;
            "Test data: " ^ (List.to_string test_data ~f:string_of_int);
            "Merge sort: " ^ (List.to_string sorted_by_merge ~f:string_of_int);
            "List sort: " ^ (List.to_string sorted_by_std ~f:string_of_int);
        ] |> List.map ~f:(fun str -> render color str) |> String.concat ~sep:""
    else
        render color message


let render_error test_data sorted_by_merge sorted_by_std =
    let color = 1 in
    let message = "Error"in
    [
        message;
        "Test data: " ^ (List.to_string test_data ~f:string_of_int);
        "Merge sort: " ^ (List.to_string sorted_by_merge ~f:string_of_int);
        "List sort: " ^ (List.to_string sorted_by_std ~f:string_of_int);
    ] |> List.map ~f:(fun str -> render color str) |> String.concat ~sep:""


let rec test size =
    let test_data = create_test_data size in
    let sorted_by_merge = merge_sort test_data in
    let sorted_by_std = List.sort test_data ~cmp:compare in

    match compare sorted_by_merge sorted_by_std with
    | 0 -> (
        printf "%s%!" (render_success test_data sorted_by_merge sorted_by_std);
        if size > 0 then
            test (size - 1)
    )
    | _ -> printf "%s%!" (render_error test_data sorted_by_merge sorted_by_std)


let () =
    printf "wait...\n%!";
    test 1000

Сортировка выбором на OCaml

2016-07-31 19:56
Selection sort on OCaml

В очередной лекции упоминалась сортировка выбором, и я решил сделать её реалзизацию в функциональном стиле на OCaml, насколько это вообще возможно.

В этот раз у меня были такие цели:

  • написать проверочный код в чисто императивном стиле;
  • написать вариант со списками и с рекурсией, пусть и не хвостовой.

В этот раз решение без разделения на разные программы и передачу данных через stdin и stdout.

Итак, первый и самый простой вариант - императивный:

let imp_sel_sort lst =
    let data = List.to_array lst in
    let last_index = Array.length data - 1 in
    for i = 0 to last_index do
        let ind = ref i in
        for j = (i + 1) to last_index do
            if data.(j) < data.(!ind) then
                ind := j;
        done;
        if !ind <> i then
            Array.swap data i !ind;
    done;
    Array.to_list data

Тут всё, как в описании алгоритма. Ищем минимальный элемент и ставим его в очередную позицию. Для поиска индекса использовал изменяемое значение let ind = ref i in.

Следующая реализация - сортировка списка с рекурсией и разбором списка до элементарных значений.

let fun_sel_sort lst =
    let rec find_min = function
        | [] -> assert false
        | [hd] -> (hd, [])
        | hd :: tl -> (
            let hd', tl' = find_min tl in
            if hd < hd' then
                hd, hd' :: tl'
            else
                hd', hd :: tl'
        )
    in

    let rec sort _lst =
        let m, rest = find_min _lst in
        match rest with
        | [] -> [m]
        | _ -> m :: sort rest
    in

    match lst with
    | [] | [_] -> lst
    | lst -> sort lst

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

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

let imp_rec_sel_sort lst =
    let data = List.to_array lst in
    let last_index = Array.length data - 1 in
    for i = 0 to last_index do
        let min_index =
            let rec find imin current =
                if current > last_index then
                    imin
                else begin
                    let imin = match compare data.(imin) data.(current) with
                    | 1 -> current
                    | _ -> imin
                    in

                    if current = last_index then
                        imin
                    else
                        find imin (current + 1)
                end
            in

            find i (i + 1)
        in
        if min_index <> i then
            Array.swap data i min_index;
    done;
    Array.to_list data

Для запуска всех этих функций мне потребовался небольшой тестовый код, который позволил мне проверить, что всё работает так, как я ожидал:

let list2str x = x |> List.to_string ~f:string_of_int


let () =

   (* Код для первоначальной проверки работоспособности *)
   imp_sel_sort [3; 4; 8; 1; 2]
       |> list2str
       |> printf "%s\n";

   fun_sel_sort [3; 4; 8; 1; 2]
       |> list2str
       |> printf "%s\n";

   imp_rec_sel_sort [3; 4; 8; 1; 2]
       |> list2str
       |> printf "%s\n";

Полный листинг программы с тестом и выводом ошибок:

open Core.Std


let fun_sel_sort lst =
    let rec find_min = function
        | [] -> assert false
        | [hd] -> (hd, [])
        | hd :: tl -> (
            let hd', tl' = find_min tl in
            if hd < hd' then
                hd, hd' :: tl'
            else
                hd', hd :: tl'
        )
    in

    let rec sort _lst =
        let m, rest = find_min _lst in
        match rest with
        | [] -> [m]
        | _ -> m :: sort rest
    in

    match lst with
    | [] | [_] -> lst
    | lst -> sort lst


let imp_sel_sort lst =
    let data = List.to_array lst in
    let last_index = Array.length data - 1 in
    for i = 0 to last_index do
        let ind = ref i in
        for j = (i + 1) to last_index do
            if data.(j) < data.(!ind) then
                ind := j;
        done;
        if !ind <> i then
            Array.swap data i !ind;
    done;
    Array.to_list data


let imp_rec_sel_sort lst =
    let data = List.to_array lst in
    let last_index = Array.length data - 1 in
    for i = 0 to last_index do
        let min_index =
            let rec find imin current =
                if current > last_index then
                    imin
                else begin
                    let imin = match compare data.(imin) data.(current) with
                    | 1 -> current
                    | _ -> imin
                    in

                    if current = last_index then
                        imin
                    else
                        find imin (current + 1)
                end
            in

            find i (i + 1)
        in
        if min_index <> i then
            Array.swap data i min_index;
    done;
    Array.to_list data


let list2str x = x |> List.to_string ~f:string_of_int


let rec test deep =
    let render_error lst =
        [
            "Error!";
            "Origin: " ^ (lst |> list2str);
            "Imperative: " ^ (lst |> imp_sel_sort |> list2str);
            "Functional: " ^ (lst |> fun_sel_sort |> list2str);
            "Imperative with recursion: " ^ (lst |> imp_rec_sel_sort |> list2str);
        ]
    in

    let rec create_random_list num =
        match num with
        | 0 -> []
        | _ -> Random.int 10:: create_random_list (num - 1)
    in

    let random_list = create_random_list deep in
    let imp_sorted = imp_sel_sort random_list in
    if imp_sorted <> (fun_sel_sort random_list) || imp_sorted <> (imp_rec_sel_sort random_list) then
        random_list |> render_error |> List.fold ~init:"" ~f:(fun accum s -> accum ^ s ^ "\n")
    else if deep > 0 then
        test (deep - 1)
    else
        "Ok"


let () =
    (*
    (* Код для первоначальной проверки работоспособности *)
    imp_sel_sort [3; 4; 8; 1; 2]
        |> list2str
        |> printf "%s\n";

    fun_sel_sort [3; 4; 8; 1; 2]
        |> list2str
        |> printf "%s\n";

    imp_rec_sel_sort [3; 4; 8; 1; 2]
        |> list2str
        |> printf "%s\n";
    *)

    test 100 |> printf "%s"

Заключение

Практической ценности у fun_sel_sort и imp_rec_sel_sort нет. Я их написал просто в качестве упражнения. Это похоже на code golf, когда пытаются решить задачу, использовав при написании кода наименьшее количество символов. Так и здесь, это просто разминка для мозгов.