CODEWITHSUNDEEP
ocaml
Jackson Tale
Jackson Tale

Reputation: 25812

What's the complexity of comparison between two lists in OCaml?

If l1 and l2 are two lists, will l1 = l2 cost O(N) or O(1)?

Futher questions:

If l1=l2, will l1 and l2 share the same physical memory?

How about strings? will s1 = s2 cost O(1)?

Upvotes: 3

Views: 201

Answers (1)

Daniel Bünzli
Daniel Bünzli

Reputation: 5167

For structural comparison = you need to at least see all the data so it's (almost, see comment below) always O(n) both for lists and strings in the worst case (equal values). Physical comparison == is O(1) you just compare the pointers.

Note however that on your own data structures it is possible to implement structural comparison as physical comparison by ensuring, during value construction, that no two structurally equal values will use different physical memory. This is called hash-consing and you can find a more thorough explanation in this paper (doi).

In general with lists you cannot infer from l1 = l2 that they share the same physical memory since it depends on how they have been constructed as OCaml does not hash-cons lists. This also holds for strings.

Upvotes: 4

Related Questions