Хвост-рекурсивная сортировка слиянием в OCaml - PullRequest
Новая
       38

Хвост-рекурсивная сортировка слиянием в OCaml

8 голосов
/ 27 марта 2010

Я пытаюсь реализовать хвостовую рекурсивную функцию сортировки списка в OCaml, и я придумаю следующий код: 

let tailrec_merge_sort l =
  let split l = 
    let rec _split source left right =
      match source with
        | [] -> (left, right)
        | head :: tail -> _split tail right (head :: left) 
    in _split l [] []
  in

  let merge l1 l2 = 
    let rec _merge l1 l2 result =
      match l1, l2 with
        | [], [] -> result
        | [], h :: t | h :: t, [] -> _merge [] t (h :: result)
        | h1 :: t1, h2 :: t2 ->
            if h1 < h2 then _merge t1 l2 (h1 :: result)
            else            _merge l1 t2 (h2 :: result)
    in List.rev (_merge l1 l2 [])
  in

  let rec sort = function
    | [] -> []
    | [a] -> [a]
    | list -> let left, right = split list in merge (sort left) (sort right)
  in sort l
;;

Тем не менее, похоже, что на самом деле это не хвостовая рекурсия, поскольку я сталкиваюсь с ошибкой "Переполнение стека во время оценки (циклическая рекурсия?)".

Не могли бы вы помочь мне определить нерекурсивный вызов в этом коде? Я искал довольно много, не найдя его. Может ли быть привязка let в функции sort?

Ответы [ 2 ]

9 голосов
/ 28 марта 2010

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

Убедитесь, что вы используете последнюю версию OCaml. В версиях 3.08 и более старых, List.rev может уничтожить стек. Эта проблема исправлена ​​в версии 3.10. Используя версию 3.10.2, я могу отсортировать список из десяти миллионов элементов , используя ваш код. Это займет пару минут, но я не бью стопку. Поэтому я надеюсь, что ваша проблема просто в том, что у вас есть старая версия OCaml.

Если нет, то следующим шагом будет установка переменной окружения 

OCAMLRUNPARAM=b=1

, который даст трассировку стека, когда вы ударите стек.

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

Если вам нужно отсортировать более 10 миллионов элементов, может быть, вам стоит взглянуть на другой алгоритм? Или, если хотите, вы можете CPS-конвертировать слияние вручную, что даст хвостовую рекурсивную версию за счет распределения переходов в куче. Но я думаю, что в этом нет необходимости.

7 голосов
/ 27 марта 2010

Выражение 

merge (sort left) (sort right)

не является хвостовой рекурсией; он вызывает оба (сортировка влево) и (сортировка вправо) рекурсивно, пока в вызове остается работа (объединение).

Я думаю, вы можете исправить это с помощью дополнительного параметра продолжения: 

  let rec sort l k =
    match l with
    | [] -> k [] 
    | [a] -> k [a] 
    | list -> let left, right = split list in sort left (fun leftR -> sort right (fun rightR -> k (merge leftR rightR)))
  in sort l (fun x -> x)
...