переполнение стека при генерации большой последовательности букв в ocaml - PullRequest
Новая
       52

переполнение стека при генерации большой последовательности букв в ocaml

3 голосов
/ 31 марта 2011

С учетом алфавита ["a"; "b"; "c"] Я хочу выгрузить все последовательности длиной 25 в файл.(Буквы могут повторяться в последовательности; это не перестановка.) Проблема в том, что я получаю Stack overflow during evaluation (looping recursion?), когда пытаюсь использовать следующий код: 

let addAlphabetToPrefix alphabet prefix =
  List.map (function letter -> (prefix ^ letter)) alphabet;;

let rec generateWords alphabet counter words =
  if counter > 25 then
    words
  else
    let newWords = List.flatten(List.map (function word -> addAlphabetToPrefix alphabet word) words) in 
    generateWords alphabet (counter + 1) newWords;;

generateWords ["a"; "b"; "c"] 0 [""];; (* Produces a stack overflow. *)

Есть ли лучший способ сделать это?Я думал о том, чтобы сначала сгенерировать весь список, а затем вывести весь список в файл, но нужно ли многократно генерировать списки партиалов, а затем создавать дамп?Поможет ли что-нибудь ленивое?

Почему именно происходит переполнение стека?AFAICT, моя generateWords функция является рекурсивной.Неужели проблема в том, что генерируемый мной список words становится слишком большим, чтобы поместиться в память?

Ответы [ 2 ]

6 голосов
/ 31 марта 2011

OCaml оптимизирует хвостовую рекурсию, поэтому ваш код должен работать, за исключением: функция List.map стандартной библиотеки, к сожалению, не является хвостовой рекурсией.Переполнение стека может произойти в одном из этих вызовов, поскольку ваши списки становятся довольно большими.

Батареи включены и библиотека ядра Джейн Стрит предоставляют хвостовую рекурсивную версию map.Попробуйте один из них и посмотрите, решит ли он проблему.

6 голосов
/ 31 марта 2011

Ваши функции компилируются как tailcalls. Я подтвердил из линеаризованного кода; полученный из опции -dlinear в нативном компиляторе, ocamlopt[.opt].

В том-то и дело, что ваша куча растет в геометрической прогрессии, и в этом методе невозможно удержать 25 слов. Попытка с 11 работает нормально (и является самой высокой, с которой я мог иметь дело).

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

...