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

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

Жадный алгоритм на OCaml 2 - загрузка рюкзака

2016-07-22 13:55

Продолжаю слушать курс Algorithmic Toolbox.

Прослушал блок про оптимальную загрузку рюкзака жадным алгоритмом, и начал писать код для поиска оптимальной загрузки рюкзака (Fractional Knapsack).

Условия:

  • Ввод и вывод данных через терминал.
  • Результат поиска - максимальная стоимость продуктов в рюкзаке.
  • Тестирующий код - отдельный процесс.

Часть 1 - первая реализация

Поиск максимальной стоимости сделал на OCaml. Ввод данных идёт в stdin в таком виде:

вместительность_рюкзака количество_продуктов [общая_цена вес]*

  7 3 20 4 14 2 18 3
let find_solution capacity items =
    let rec _solve free_capacity sorted_items =
        match sorted_items with
        | [] -> 0.0
        | (price, weight) :: tl ->
            if weight <= free_capacity then
                price +. (_solve (free_capacity -. weight) tl)
            else
                price /. weight *. free_capacity
    in

    List.sort (fun (p1, w1) (p2, w2) -> compare (p2 /. w2) (p1 /. w1)) items
        |> _solve capacity


let () =
    let knapsack_capacity = Scanf.scanf " %f" (fun x -> x) in

    let number_of_items =  Scanf.scanf " %d" (fun x -> x) in

    (* [(price, weight)] *)
    let rec scan_pairs = function
        | 0 -> []
        | n -> Scanf.scanf " %f %f" (fun a b -> (a, b)) :: scan_pairs (n - 1)
    in
    let items = scan_pairs number_of_items in

    find_solution knapsack_capacity items |> string_of_float |> print_endline;

Проверку решения сделал на Python. Алгоритм поиска максимальной стоимости рюкзака в этом случае сделал итеративным, а не рекурсивным, как в случае с OCaml.

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

'Тест для проверки корректности решения загрузки рюкзака порграммой на OCaml.'

import random

from subprocess import check_output


def solve(capacity, pairs):
    pairs = sorted(pairs, key=lambda x: x[0] / x[1], reverse=True)

    value = 0
    while capacity and pairs:
        (price, weight), *pairs = pairs
        if capacity < weight:
            value += (price / weight) * capacity
            capacity = 0
        else:
            value += price
            capacity -= weight

    return value


def main():
    random.seed(1)

    for number_of_pairs in range(15):
        capacity = random.randint(3, 30)

        pairs = [(random.randint(1, 20), random.randint(1, 20))
                 for _ in range(number_of_pairs)]

        test_data = '{capacity} {number_of_pairs} {pairs}'.format(
            capacity=capacity, number_of_pairs=number_of_pairs,
            pairs=' '.join(['{} {}'.format(*i) for i in pairs])
        )

        ocaml_result = check_output(
            './fractional_knapsack.ml.byte', input=bytes(test_data, 'utf-8'))

        py_result = solve(capacity, pairs)

        print(float(ocaml_result) == py_result,
              '[p {}, o {}]'.format(py_result, ocaml_result),
              test_data)


if __name__ == '__main__':
    main()

И результат:

True [p 0, o b'0.\n'] 7 0
True [p 3, o b'3.\n'] 21 1 3 9
False [p 7.384615384615385, o b'7.38461538462\n'] 6 2 16 15 16 13
True [p 36, o b'36.\n'] 28 3 7 4 16 1 13 14
True [p 39.6, o b'39.6\n'] 22 4 1 15 9 8 19 4 11 1
True [p 1.6, o b'1.6\n'] 3 5 1 18 1 13 7 14 1 17 8 15
False [p 40.77777777777778, o b'40.7777777778\n'] 18 6 18 8 12 8 8 15 10 1 14 18 4 6
False [p 27.647058823529413, o b'27.6470588235\n'] 23 7 10 4 11 17 14 17 7 10 10 19 16 17 13 19
False [p 50.05882352941177, o b'50.0588235294\n'] 30 8 2 16 8 13 14 6 12 18 12 3 15 17 4 6 17 13
False [p 62.333333333333336, o b'62.3333333333\n'] 14 9 16 1 16 2 10 20 19 19 13 6 6 17 8 1 7 18 18 8
False [p 33.583333333333336, o b'33.5833333333\n'] 15 10 17 12 19 12 15 9 18 20 1 13 17 5 17 18 7 14 2 16 12 19
True [p 55.0, o b'55.\n'] 20 11 7 17 14 16 12 14 12 1 18 18 20 20 11 15 20 1 8 6 18 19 6 3
True [p 83.2, o b'83.2\n'] 28 12 18 9 2 3 3 1 15 1 9 8 9 4 20 6 12 10 3 6 6 9 17 6 9 10
True [p 64.0, o b'64.\n'] 17 13 11 16 16 4 1 10 13 11 14 7 9 4 9 17 7 20 14 1 8 1 13 5 2 6 15 17
True [p 61.0, o b'61.\n'] 24 14 14 18 8 17 15 8 17 1 13 19 11 14 2 10 5 7 2 10 3 3 10 10 6 14 19 9 5 1

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

Часть 2 - доработки

Полученное решение меня не устраивало по нескольким пунктам:

  • нет хвостовой рекурсии в коде на OCaml;
  • нет округления в проверке равенства результатов;
  • вывод всех тестовых данных в коде на Python, в то время как мне нужно было видеть только ошибки.

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

let find_solution capacity items =
    let rec _solve free_capacity value sorted_items =
        match sorted_items with
        | [] -> value
        | (price, weight) :: tl ->
            if weight <= free_capacity then
                _solve (free_capacity -. weight) (value +. price) tl
            else
                value +. price /. weight *. free_capacity
    in

    List.sort (fun (p1, w1) (p2, w2) -> compare (p2 /. w2) (p1 /. w1)) items
        |> _solve capacity 0.0

let () =
    let knapsack_capacity = Scanf.scanf " %f" (fun x -> x) in

    let number_of_items =  Scanf.scanf " %d" (fun x -> x) in

    (* [(price, weight)] *)
    let rec scan_pairs = function
        | 0 -> []
        | n -> Scanf.scanf " %f %f" (fun a b -> (a, b)) :: scan_pairs (n - 1)
    in
    let items = scan_pairs number_of_items in

    find_solution knapsack_capacity items |> string_of_float |> print_endline;

Потом настал черёд тестового скрипта на Python. Я прикинул, что трёх знаков после запятой мне хватит для точности сравнения.

import random

from subprocess import check_output


def solve(capacity, pairs):
    pairs = sorted(pairs, key=lambda x: x[0] / x[1], reverse=True)

    value = 0
    while capacity and pairs:
        (price, weight), *pairs = pairs
        if capacity < weight:
            value += (price / weight) * capacity
            capacity = 0
        else:
            value += price
            capacity -= weight

    return value


def main():
    random.seed(1)

    for number_of_pairs in range(1000):
        capacity = random.randint(3, 30)

        pairs = [(random.randint(1, 20), random.randint(1, 20))
                 for _ in range(number_of_pairs)]

        test_data = '{capacity} {number_of_pairs} {pairs}'.format(
            capacity=capacity, number_of_pairs=number_of_pairs,
            pairs=' '.join(['{} {}'.format(*i) for i in pairs])
        )

        ocaml_result = check_output(
            './fractional_knapsack.ml.byte', input=bytes(test_data, 'utf-8'))
        ocaml_result = float(ocaml_result)

        py_result = solve(capacity, pairs)

        precise = 3
        ocaml_result = round(ocaml_result, precise)
        py_result = round(py_result, precise)

        assert ocaml_result == py_result, ('[p {}, o {}] {}'.format(
            py_result, ocaml_result, test_data))

    print('Все тесты пройдены.')


if __name__ == '__main__':
    main()

Запущенный скрипт показал нужное "Все тесты пройдены.".

Жадный алгоритм на OCaml

2016-07-20 13:12

Записался слушателем курса Algorithmic Toolbox (бесплатно халявный вариант).

Сегодня утром слушал про жадный алгоритм для поиска групп детей, у которых разница в возрасте не должна превышать год. Поскольку халявщикам нельзя отправлять свои решения, а платить за этот курс я не планирую, то написал свой жадный алгоритм на OCaml, вместо предлагаемых в курсе питона и С++.

Условия под которые писался этот код:

  • данные вводятся из терминала;
  • возраст даётся в месяцах, чтобы не возиться с преобразованием и обойтись одной функцией ввода;
  • рекурсия должна быть хвостовой.
let scan_int () = Scanf.scanf " %d" (fun x -> x)


let rec scan_ages = function (* Возраст в месяцах *)
    | 0 -> []
    | n -> scan_int () :: scan_ages (n - 1)


let print_groups lst =
    print_endline "Groups: ";

    List.iter (fun sub_list ->
        sub_list |> List.map string_of_int
                 |> String.concat " "
                 |> print_endline
    ) lst


let find_groups lst =
    let max_diff = 12 in
    let rec _find lst first group total =
        match lst with
        | [] -> (
            match group with
            | [] -> total
            | _ -> group :: total)
        | hd :: tl -> (
            match compare (hd - first) max_diff with
            | 0 | -1 -> _find tl first (hd :: group) total
            | 1 -> _find tl hd [hd] (group :: total)
            | _ -> invalid_arg "Wrong answer from compare!")
    in

    match List.sort compare lst with
    | [] -> []
    | hd :: tl -> _find tl hd [hd] []


let () =
    scan_int () |> scan_ages
                |> List.sort compare
                |> find_groups
                |> print_groups;

Тестирование

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

let make_test () =
    let rec gen n =
        match compare n 0 with
        | 0 | 1 -> (Random.int 115) + 6 :: gen (n - 1) (* Возраст от 6 месяцев до 10 лет *)
        | _ -> []
    in
    gen ((Random.int 100) + 1) (* От одного до 100 детей в группе *)

Помимо тестовых данных нужна функция проверки равенства двух списков групп:

let compare_groups g1 g2 =
    let sorted lst =
        List.map (List.sort compare) lst |> List.sort compare
    in
    let even = match compare (List.length g1) (List.length g2) with
    | 0 -> sorted(g1) = sorted(g2)
    | _ -> false
    in
    even

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

let greedy_iter lst =
    let sorted_lst = List.sort compare lst in
    let groups = ref [] in
    let i = ref 0 in
    while !i < List.length sorted_lst do
        let first = List.nth sorted_lst !i in
        let group = ref [first] in
        i := !i + 1;
        while !i < List.length sorted_lst && compare 12 ((List.nth sorted_lst !i) - first) >= 0 do
            group := (List.nth sorted_lst !i) :: !group;
            i := !i +1;
        done;
        groups := !group :: !groups
    done;
    !groups

И код запуска теста

let test () =
    for i = 0 to 50 do
        let ages = make_test () in
        let g1 = greedy_iter ages in
        let g2 = find_groups ages in
        if compare_groups g1 g2 then
            print_endline "Ok"
        else begin
            print_endline "Error";
            print_endline "Ages: ";
            ages |> List.map string_of_int |> String.concat " " |> print_endline;
            print_endline "Imperative:";
            print_groups g1;
            print_endline "----";
            print_endline "Functional:";
            print_groups g2;
            print_endline "";
        end
    done


let () =
    test();

Работа обеих реализаций оказалась одинаковой.

Заключение

Писать код на OCaml становится всё проще. Эта реализация алгоритма наверняка содержит недостатки, которые можно убрать, но сейчас в этом нет смысла. Мне нужно нарабатывать практику работы с языком.

На будущее: нужно посмотреть, как принято тестировать код на OCaml.