Должен ли я использовать массивы или списки в рекурсивной функции OCaml?

Question

У меня есть рекурсивная функция в OCaml, которая принимает выражение и возвращает массив инструкций (это для проекта компиляторов).

Код в основном выглядит примерно так:

let rec compile_body (body:expr):fn = 
  match body with 
  | Seq (expr1, expr2) -> Array.concat [compile_body expr1; compile_body expr2;]
  | Add (n1, n2) -> [|Load 0 n1; Load 1 n2; Add 0 0 1;|]
  | ... 

Было бы более производительным написать функцию, возвращающую список, а затем, в самом конце, преобразовать список в массив?

Answer 1

Использование массива будет копировать все это снова и снова.Это быстро становится слишком медленным.

Использование списка с добавлением легко имеет ту же проблему, или даже хуже.Никогда не добавляйте что-либо в длинный список.Закажите свой код, чтобы он добавлялся в короткий список.rev_append также может быть полезен.Но в вашем случае Seq (a, b) может иметь длинные списки для a и b, поэтому добавление - плохая идея.

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

В качестве альтернативы можно выполнить обход слева направо, чтобы построить список в обратном направлении и в конце перевернуть его.Это часто легче читать, когда вы конструируете вещи в порядке, который вы ожидаете.

Answer 2

Array.concat или Array.append, согласно документации, выделите новый массив, а затем скопируйте содержимое двух начальных массивов в последующее.

List.append сложность пропорциональна длине только первого аргумента.

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

правка: как упоминалось @coredump, сохранение дерева массивов, которое представляло бы логическую конкатенацию всех массивов, было бы более дешевыми структурами, и если в конце вам понадобится фактический массив,Затем вы можете вычислить общий размер вашего «абстрактного» массива, создать массив этого размера, а затем заполнить его содержимым дерева массива.Операция будет линейной по размеру конечного массива.

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