We should one day implement the TODO for an efficient ImmutableMultiset.asList()

[gissuebot]

Original issue created by kevinb@google.com on 2013-05-24 at 07:29 PM

---

I almost recommended on Stack Overflow finding the most frequently occurring element in a multiset using

Multisets.copyHighestCountFirst(theMultiset).asList().get(0)

If I read the code right this would have spectacularly bad performance, risking an OutOfMemoryException even. (Sorry, no time to verify this yet, jotting this here before I forget it.)

[gissuebot]

Original comment posted by kevinb@google.com on 2013-05-24 at 07:31 PM

---

(yes, I'm aware that SO answer is bad anyway, but it's the best non-manual-looping way we offer right now, and it's not as horrific as what asList() does, again if I'm reading things right.)

[gissuebot]

Original comment posted by lowasser@google.com on 2013-05-24 at 11:37 PM

---

So, if d is the number of distinct elements, and n is the size of the multiset (counting duplicates), then

• The current implementation takes O(n) to build and O(1) to query.

The only real alternative I can conceive of would take O(d) to build and O(log d) to query.

Do we consider that acceptable? It does feel weird to have an ImmutableList without O(1) get.

[gissuebot]

Original comment posted by kevinb@google.com on 2013-05-25 at 12:44 AM

---

I worry about the cases, which I believe are plentiful, where d is
extremely small compared to n; Multisets lead you to do things like that.
 This is just one opinion, but an O(log d) List.get() doesn't necessarily
offend me.