0
\$\begingroup\$

I'm implementing some simple algorithms (e.g. two-sum) in OCaml and I am unsure why my OCaml solution is running much slower than the equivalent Python version.

My OCaml version:

open Base

let two_sum_hash lst target = 
  let rec loop tbl counter = function
    | [] -> failwith "No sum found"
    | x :: xs -> match Hashtbl.find tbl x with 
      | None -> Hashtbl.set tbl ~key:(target - x) ~data:counter; loop tbl (counter+1) xs 
      | Some index -> [index; counter]
  in loop (Hashtbl.create (module Int)) 0 lst 

and the Python solution

def two_sum(lst, target):
    d = {}
    for i, x in enumerate(lst):
        if x in d:
            return [d[x], i]
        d[target - x] = I

The OCaml version runs in ~2.16 seconds and the Python solution runs in ~1.15 seconds for large inputs (e.g. list of 10⁷ elements).

What is the reason for OCaml running slower? Am I doing something wrong in my OCaml solution?

I know that dicts are heavily optimised in Python - I wonder how/whether can I make the OCaml code more performant.

New contributor
pbmstrk is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

Your Answer

pbmstrk is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.