I'm trying to understand the time complexity of determining equality between persistent data structures in Clojure (Vectors, Maps, Sets, etc.). These are based on data structures pioneered by Phil Bagwell - hash array mapped tries - so if you know of these from their implementation in other languages you probably also know the answer.

I know enough to understand their general implementation (shallow tree, high branching factor, structural sharing, path copying, stuff like that).

My question is, how can these structures be tested for equality quickly? In Clojure, if their values are the same, they are equal, it's built into the equality testing function of the language. I've heard that one advantage of these structures is in quickly determining if a structure has changed and needs to be updated (advantages in ClojureScript wrapping React for example in preventing unnecessary component updates).

Are these structures faster at determining equality then say, having to walk a tree of objects and checking all values? That's a O(n) operation. How are these persistent tries faster, is this in fact true?

  • $\begingroup$ Actually I don't think you can unless you walk through the data structure and compare. $\endgroup$ – xuq01 Dec 21 '18 at 4:31

Your Answer

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.