Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

TreeMultimap.create(TreeMultimap) takes O(n log n) #1579

Open
gissuebot opened this issue Oct 31, 2014 · 7 comments
Open

TreeMultimap.create(TreeMultimap) takes O(n log n) #1579

gissuebot opened this issue Oct 31, 2014 · 7 comments
Labels
P3 package=collect status=triaged type=performance Related to performance

Comments

@gissuebot
Copy link

gissuebot commented Oct 31, 2014 •
edited by cgdecker

Original issue created by jbel...@datastax.com on 2013-11-13 at 05:29 PM

Inserting into a binary tree in sorted order is the worst case scenario for a red-black tree like the one backing TreeMultimap, and that's exactly what happens when you call putAll on another TreeMultimap.

Prior art: TreeMap special cases new-from-SortedMap via buildFromSorted.
@gissuebot
Copy link
Author

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

(No comment entered for this change.)

Owner: lowasser@google.com
Labels: Type-Performance, Package-Collect

@gissuebot
Copy link
Author

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

To be clear: is that actually quadratic time? I understand that it's the worst case scenario, but I'm not sure I follow why that would lead to quadratic time instead of O(n log n).

@gissuebot
Copy link
Author

gissuebot commented Nov 1, 2014 •
edited by cgdecker

Original comment posted by jbel...@datastax.com on 2013-11-13 at 05:56 PM

My apologies, O(n log n) is correct. I'm not sure if there is a way to edit the issue title.

@gissuebot
Copy link
Author

Original comment posted by lowasser@google.com on 2013-11-13 at 06:03 PM

(No comment entered for this change.)

@cgdecker cgdecker removed the migrated label Nov 1, 2014
@kevinb9n
Copy link
Contributor

kevinb9n commented Oct 8, 2015

Pull request welcome.

@wodomierz
Copy link
Contributor

Should TreeMultimap.create(TreeMultimap) be a new method in API?
If yes, what is expected behavior?
Like in TreeMultimap.create(Multimap)
-> natural order
or like in java TreeMap(SortedMap)
-> order from other Treemultimap ?

IMO TreeMultimap.create(TreeMultimap) should be a new method with specification like in java TreeMap - new TreeMultimap with ordering from other TreeMultimap.

@wodomierz
Copy link
Contributor

Pull request:
#2498

@wodomierz wodomierz mentioned this issue Jun 5, 2016
Open
@raghsriniv raghsriniv added the P3 label Jun 24, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
P3 package=collect status=triaged type=performance Related to performance
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
6 participants
@cgdecker @lowasser @kevinb9n @gissuebot @raghsriniv @wodomierz