CODEWITHSUNDEEP
clojure
qbert
qbert

Reputation: 3

Find maximum element in Clojure sorted-set

I am looking for an idiomatic, O(1), way to extract the maximum element of a sorted-set of integers, in Clojure. Do I have to cast the set into a seq?

Upvotes: 0

Views: 292

Answers (2)

RJ Acuña
RJ Acuña

Reputation: 530

If you take into account the construction of the set, (into #{} my-coll) & (max my-set) is faster, than (into (sorted-seq) my-coll) & (last my-sorted-set).

Upvotes: 0

Michał Marczyk
Michał Marczyk

Reputation: 84331

With Clojure's built-in sorted sets, this is O(log n):

(first (rseq the-set))

With data.avl sets, the above also works, and you can also use nth to access elements by rank in O(log n) time:

(nth the-set (dec (count the-set)))

None of these data structures offers O(1) access to extreme elements, but you could certainly use [the-set max-element] bundles (possibly represented as records for cleaner manipulation) with a custom API if you expect to perform frequent repeated accesses to the maximum element.

If you only care about fast access to the maximum element and not about ordered traversals, you could actually use the bundle approach with "unsorted" sets – either built-in hash sets or data.int-map sets. That's not useful for repeated disj of maximum elements, of course, only for maintaining upper bound information for a fundamentally unsorted set (unless you keep a stack of max elements in the bundle, at which point it definitely makes sense to simply use sorted sets and get all relevant operations for free).

Upvotes: 5

Related Questions