search

eclipse / eclipse-collections

Eclipse Collections is a collections framework for Java with optimized data structures and a rich, functional and fluent API.
http://www.eclipse.org/collections
2.39k stars 593 forks source link

Fix performance problem in MutableList.subList() / implement similar optimization as ArrayList.subList() #1603

Closed motlin closed 3 weeks ago

motlin commented 1 month ago

When implementing head/tail list algorithms in Java, it's common to use subList() to get the tail. When calling subList() on a subList, we must get a chain of wrappers. However, we must also maintain constant times for lookups or the list algorithms become quadratic.

There's a kind of obvious optimization here, and java.util.ArrayList.SubList implements it but none of the SubLists in Eclipse Collections do. SubLists maintain a pointer to their parent sublist as well as the root list in the chain. Mutation operations go through the parent chain, but lookups go straight to the root.

yoa1226 commented 1 month ago

@motlin hi motlin, I can understand what you said. I can Mimick the Implementation of Java Standard Library. you can assign this issue to me.

motlin commented 1 month ago

Thanks @yoa1226 I've assigned it to you. Let me know if you have any questions.

yoa1226 commented 1 month ago

@motlin Okay, I will complete the task perfectly, and I'll communicate with you promptly as soon as I have any questions.

yoa1226 commented 1 month ago

@motlin hi, motlin . I have completed this task, and the pull request at 1620. Some unit tests was added to MutableListTestCase and all unit tests at package org.eclipse.collections.test.list.mutable have passed. You can check my code whenever it's convenient for you.

yoa1226 commented 3 weeks ago

@motlin hi motlin, please close this issue.