*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

воскресенье, 12 сентября 2010 г.

Проба на Эрланге

Решал я тут одну красивую задачу. Решение - рекурсивная функция, динамическое программирование.

Для эксперимента написал свою первую программу на Эрланге как решение этой задачи.

Вот оригинал на C++ (рекурсия с кешированием):

bignum f(int n, int k, int t, int& K, vector<vector<vector<bignum> > >& dp) {
  if (n == 0 && k == 0 && t == 0) return 1;
  if (n == 0 || k < 0) return 0;

  if (!(dp[t][n][k] == -1)) return dp[t][n][k];

  bignum ans = 0;

  if (k < K) {
    ans = ans + f(n - 1, k - 1, t, K, dp);
    if (t == 1 || (t == 0 && k < K - 1))
      ans = ans + f(n - 1, k + 1, t, K, dp);
  }

  if (t == 1 && k == K) {
    ans = ans + f(n - 1, k - 1, 0, K, dp);
    ans = ans + f(n - 1, k - 1, 1, K, dp);
  }

  dp[t][n][k] = ans;
  return ans;
}

А теперь Эрланг:

main(_) ->
  N = 50, K = 25,
  io:format("~w\n", [rbs(2*N, 0, 1, K)]).

rbs(0, 0, 0, _) -> 1;
rbs(0, _, _, _) -> 0;
rbs(_, K, _, _) when K < 0 -> 0;

rbs(N, K, 0, MAX_K) ->
  if 
    K < MAX_K-1 -> rbs(N-1, K-1, 0, MAX_K) + rbs(N-1, K+1, 0, MAX_K);
    K < MAX_K   -> rbs(N-1, K-1, 0, MAX_K);
    K =:= MAX_K -> 0
  end;

rbs(N, K, 1, MAX_K) ->
  if
    K < MAX_K   -> rbs(N-1, K-1, 1, MAX_K) + rbs(N-1, K+1, 1, MAX_K);
    K =:= MAX_K -> rbs(N-1, K-1, 0, MAX_K) + rbs(N-1, K-1, 1, MAX_K)
  end.

Красиво, а?

Но вот увы, кеширование результатов пришлось делать тоже вручную, так как без нее программа имеет экспоненциальное время. Так что итоговый вариант выглядит так:

#!/usr/bin/env escript

main(_) ->
  N = 50, K = 25,
  io:format("~w\n", [rbs(2*N, 0, 1, K)]).

rbs(0, 0, 0, _) -> 1;
rbs(0, _, _, _) -> 0;
rbs(_, K, _, _) when K < 0 -> 0;

rbs(N, K, 0, MAX_K) ->
  if 
    K < MAX_K-1 -> rbs_memo(N-1, K-1, 0, MAX_K) + rbs_memo(N-1, K+1, 0, MAX_K);
    K < MAX_K   -> rbs_memo(N-1, K-1, 0, MAX_K);
    K =:= MAX_K -> 0
  end;

rbs(N, K, 1, MAX_K) ->
  if
    K < MAX_K   -> rbs_memo(N-1, K-1, 1, MAX_K) + rbs_memo(N-1, K+1, 1, MAX_K);
    K =:= MAX_K -> rbs_memo(N-1, K-1, 0, MAX_K) + rbs_memo(N-1, K-1, 1, MAX_K)
  end.

rbs_memo(N, K, T, MAX_K) ->
  Name = rbs,
  case ets:info(Name) of
    undefined ->
      ets:new(Name, [public, named_table]);
    _ -> true
  end,
  Key = {N, K, T, MAX_K},
  case ets:lookup(Name, Key) of
    [] ->
      Val = rbs(N, K, T, MAX_K),
      ets:insert(Name, {Key, Val}),
      Val;
    [{_, Val}] -> Val;
    Else -> Else
  end.

Странно, ведь можно было бы заложить кеширование прямо в языке. Ведь когда функция вызывается повторно с теми же самыми аргументами, то очевидно, что результат будет такой же (ибо Эрланг - это "чистый" функциональный язык, и side effects тут исключены). Но в целом функция кеширования весьма универсальна и ее можно быстро адаптировать для других ситуаций.

По времени выполнения эрланговый вариант не уступает C++. При это надо учесть, что Эгланге по умочанию арифметика "длинная", а в С++ мне пришлось использовать доморощенный класс bignum.

11 комментариев:

  1. эта задача легко решается в MMIXAL.NET(http://peternikmmixal.blogspot.com/).
    Там тоже длинная арифметика.

    ОтветитьУдалить
  2. Эрланг не чистый (ввод-вывод) и побочные эффекты запросто могут быть.

    ОтветитьУдалить
  3. Сохранение уже вычисленных значений обычно называют мемоизацией.

    P.S. Что-то все эрланг нахваливают. Посмотреть, что ли?

    ОтветитьУдалить
  4. Возможно, что я законченный плюсофил, но не увидел я в этом узелковом письме никакой красоты... Код не стал понятнее, меньше или выразительнее.

    ОтветитьУдалить
  5. @Tier
    Не смотря на то, что Erlang не знаю, смог разобраться что к чему, т.к. прологовский стиль сопоставления с образцом (если я правильно понял) очень сильно повышает читабельность программы. Если бы не знал С++ - вряд ли разобрался бы в коде.

    ОтветитьУдалить
  6. @Владислав: Чтобы два раза не вставать, можете порекомендовать хорошую книгу по Прологу?

    ОтветитьУдалить
  7. Владислав, значит, вам знаком "прологовский стиль". Понятность и красота слишком субъективные понятия, чтобы можно было уверенно о них говорить. Лично я "поплыл" уже на этом
    rbs(N, K, 0, MAX_K) ->
    if

    ОтветитьУдалить
  8. @Александр, к сожалению не могу, т.к. Пролог изучал в универе по лекциям.

    @Tier, согласен. Просто "->" общепринятое (в ФП) обозначение результата, возвращаемого функцией.

    ОтветитьУдалить
  9. to Александр:
    Стобо Д. Ж.
    Языл программирования Пролог.
    М,: Радио и связь.

    ОтветитьУдалить
  10. Что-то мне подсказывает, что посылка сообщений другим процессам как раз и будет side effects, разве нет?

    ОтветитьУдалить
  11. @bialix: Может и так. Просто в managed языках многое можно автоматизировать. Например, у функции может быть опциональный атрибут кеширования результатов. Если ты уверен в "чистоте" функции, то можно его выставить.

    ОтветитьУдалить