Я пишу реализацию математически описанного алгоритма в OCaml. Я стараюсь, чтобы реализация была чистой и близкой к бумаге, и использовать только хорошо определенные методы, такие как запоминание для повышения производительности.Автоматическое запоминание сложных типов данных в OCaml посредством перечисления?
К сожалению, несмотря на то, что memoization хорошо работает с целыми числами, он может быть O (n) для больших или сложных типов данных. Можно получить производительность O (1), перечислив типы данных до memoization. Например, в приведенном ниже примере мы видим, что memo len
все равно будет O (n), но DroidMemoized.len
будет O (1) и что DroidMemoized
является заменой для Droid
.
Однако, возможно ли создать DroidMemoized
от Droid
? Например, существует ли модуль EnumMemo, чтобы мы могли написать let DroidMemoized = EnumMemo.Make(Droid)
?
module Droid = struct
type t = string
let empty = ""
let beep x = x^" notdroids"
let boop x = x^" lookingfor"
let len x = String.length x
end
let memo f =
let m = Hashtbl.create 9 in
fun x ->
try Hashtbl.find m x
with Not_found ->
let y = f x in
Hashtbl.add m x y; y
module DroidMemoized = struct
(* Boilerplate *)
let to_id_h : (Droid.t, int) Hashtbl.t = Hashtbl.create 9
let from_id_h : (int, Droid.t) Hashtbl.t = Hashtbl.create 9 (*or use array*)
let size = ref 0
let from_id i = (Hashtbl.find from_id_h i)
let to_id (x :Droid.t) : int =
if Hashtbl.mem to_id_h x
then Hashtbl.find to_id_h x
else (size := (!size)+1;
Hashtbl.add to_id_h x (!size);
Hashtbl.add from_id_h (!size) x;
!size)
(* Function wrappers *)
let empty = to_id Droid.empty
let beep = memo (fun x -> to_id (Droid.beep (from_id x)))
let boop = memo (fun x -> to_id (Droid.boop (from_id x)))
let len = memo (fun x -> (Droid.len (from_id x)))
end
Почему '~ O (Log N)' Не Hashtbl в 'O (1)'? –
Ну, O (1) средний случай с хорошей хэш-функцией и O (n) наихудший случай, мы можем получить наихудший случай O (log n) с красным черным деревом. Я просто перейду на O (1), так как эти данные не слишком релевантны вопросу. – gmatht