Krdytkyu

I just started Advent of Code 2018. This is exercise 2 of day 1, and I can't understand why my code is so slow (4 minutes 37 seconds, compared to 200ms for a friend who did it in Clojure with the same computer).

Basically, it accumulates integers from a provided list of ints, named input. Whenever the current value of the accumulator is equal to one of its previous values, it is returned. We might have to loop many times over the provided list before we find such an occurrence. Here is the code:

  let main () =

    let rec my_slow_code lst history =

        if lst ==  then my_slow_code input history

        else

          let current = List.hd lst + List.hd history in

          if List.mem current history then current

          else my_slow_code (List.tl lst) (current :: history)

      in

      my_slow_code input [0]

I can't understand what mistake here makes such a slow code, maybe the use of List.mem?

I won't give it all away, since that would take away some of the fun of Advent of Code, but I'll point out:

First, yes, List.mem takes time proportional to the length of your list, which means if you're calling it over and over again it can be quite slow indeed. There might be faster structures you could use if you want to track if a previous value has been seen before, like Sets. Also, you should not be using == for equality here but rather =; I recommend learning the difference between = and ==, you will want to know it.

Second, your code is not very idiomatic OCaml; in general, if you're doing things like nesting lots of ifs and using List.hd instead of pattern matching, you may not be doing things quite right. This won't impact your performance but might impact readability and correctness. (For example, the match l with | -> ... pattern will warn you if a pattern match isn't exhaustive, which avoids nasty bugs.)