Через скобочки к ЛИСПу: неудавшееся домашнее задание для Coursera.org

Feb 08, 2013 11:00

Недавно стартанул кур Algorithms: Design & Analysis (Part I).
Так как параллельно с ним я изучаю LISP (sbcl), то решено было задания писать на нем. В результате по первой неделе был написан следующий код:[Spoiler (click to open)]
(defvar *inv* 0)
(defun count-inversions (input)
  (if (> (length input) 1)
      (let ((length-input (floor (/ (length input) 2))))
(count-and-merge (count-inversion
subseq input 0  length-input)
(count-inversion
subseq input length-input))))
      input))

(defun count-and-merge (half1 half2)
  (con
    ((and (endp half1)  (endp half2))
     ())
    ((endp half1)
     half2)
    ((endp half2)
     half1)
    ((< (car half1) (car half2)
     (cons (car half1) (count-and-merge (cdr half1) half2)))
    ((> (car half1) (car half2))
     (setq *inv* (+ *inv* (length half1)))
     (cons (car half2) (count-and-merge half1 (cdr half2)))
     )))

(defun main (filename)
  (with-open-file (fp filename :direction :input)
    (count-inversions (read-delimited-list #\} fp)))
  *inv*)


Все здорово работаетна небольших файлах, но как только появляется 100.000 курсеровского задания выходит за стек.

Т.е. древний и до мозга костей функциональный ЛИСП не умеет рекурсию оптимизировать (я вижу, что рекурия не хвостовая)? Или я что-то делаю очень не так?

На эрланге то же самое вполне работает.
[Нажмите, чтобы прочитать код]

-module(m1).
-export([
main/0
]).
main() ->
    {ok, Data} = file:read_file("./input.txt"),
%    io:format("~p~n", [Data]),
    DList = lists:map(fun(X) -> list_to_integer(binary_to_list(X)) end, binary:split(Data, <<"\r\n">>, [global, trim])),
%    io:format("~p~n", [DList]),
    count_inversions(DList).
count_inversions(Input) when length(Input) > 1 ->
    {First, Second} = lists:split(trunc(length(Input) / 2), Input),
    {List, Inversions} = merge_and_count(count_inversions(First), count_inversions(Second));
count_inversions(Input) ->
    {Input, 0}.
merge_and_count({[H1 | IList1], ICount1}, {[H2 | IList2], ICount2}) when H1 < H2  ->
    {OList, OCount} =  merge_and_count({IList1, ICount1}, {[H2 | IList2], ICount2}),
    {[H1 | OList], OCount};
merge_and_count({[H1 | IList1], ICount1}, {[H2 | IList2], ICount2}) when H1 > H2 ->
    {OList, OCount} =  merge_and_count({[H1 | IList1], ICount1}, {IList2, ICount2}),
    {[H2 | OList], OCount + length(IList1) + 1};
merge_and_count({IList, ICount1}, {[], ICount2}) ->
    {IList, ICount1 + ICount2};
merge_and_count({[], ICount1}, {IList, ICount2}) ->
    {IList, ICount1 + ICount2};
merge_and_count({[], ICount1}, {[], ICount2}) ->
    {[], ICount1 + ICount2}.
   


Помогите гуру ЛИСПа.

lisp, рекурсия, cl, coursera

Previous post Next post
Up