[
https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17565283#comment-17565283
]
Rodion Efremov commented on COLLECTIONS-797:
--------------------------------------------
h1. Matt Juntunen's benchmark data
|AddAtBeginning|10|100|1000|10000|
|ArrayList|176,494|1829,177|54234,528|3596775,413|
|LinkedList|62,349|611,409|5985,934|40763,271|
|TreeList|289,289|6047,984|76074,686|1036649,782|
|IndexedLinkedList|271,902|2637,837|35760,869|556869,866|
| | | | | |
|AddAtEnd|10|100|1000|10000|
|ArrayList|38,403|340,092|6234,836|43002,528|
|LinkedList|46,435|419,293|3654,735|35110,072|
|TreeList|306,81|5548,954|75700,567|1032992,861|
|IndexedLinkedList|104,868|1167,873|9634,173|89805,435|
| | | | | |
|AddRandom|10|100|1000|10000|
|ArrayList|326,341|4049,986|54582,256|1838828,271|
|LinkedList|158,058|2961,179|135891,252|37013702,205|
|TreeList|445,3|10293,414|147119,262|2099673,765|
|IndexedLinkedList|400,325|8783,948|111983,722|1959815,294|
| | | | | |
|GetRandom|10|100|1000|10000|
|ArrayList|78,197|734,423|7392,402|78862,244|
|LinkedList|197,489|3080,72|267972,607|29310899,638|
|TreeList|512,842|9117,646|138437,578|2065061,895|
|IndexedLinkedList|394,431|5541,905|75018,345|1460147,41|
| | | | | |
|Iterate|10|100|1000|10000|
|ArrayList|62,91|658,353|5301,981|61719,071|
|LinkedList|58,287|623,843|5621,306|51213,218|
|TreeList|305,393|6014,726|80169,228|1099637,001|
|IndexedLinkedList|122,368|1184,691|11022,604|105572,877|
| | | | | |
|IterateAndModify|10|100|1000|10000|
|ArrayList|303,264|3632,378|49540,669|2166356,311|
|LinkedList|213,742|1956,385|18953,499|190022,112|
|TreeList|833,69|16568,651|229605,468|2628626,757|
|IndexedLinkedList|412,749|4119,585|43289,963|429104,878|
| | | | | |
|RemoveFromBeginning|10|100|1000|10000|
|ArrayList|224,3|2002,162|54503,096|3349610,69|
|LinkedList|96,701|878,316|8615,404|80760,189|
|TreeList|506,639|9316,205|147200,981|1844505,941|
|IndexedLinkedList|325,617|4446,252|68059,728|1487927,03|
| | | | | |
|RemoveFromEnd|10|100|1000|10000|
|ArrayList|63,038|576,588|6041,023|65557,309|
|LinkedList|93,665|901,071|9109,41|81397,164|
|TreeList|500,438|9933,087|144084,59|1854624,745|
|IndexedLinkedList|280,929|3161,684|49786,83|1086159,843|
| | | | | |
|RemoveRandom|10|100|1000|10000|
|ArrayList|248,224|4220,029|56008,838|1844820,638|
|LinkedList|202,722|2961,544|138105,844|24060522,809|
|TreeList|737,165|16914,397|258522,451|3666183,061|
|IndexedLinkedList|461,359|6393,501|131263,122|10657129,748|
> An indexed, doubly-linked list data structure running some operations in
> O(sqrt(n)) time instead of O(n)
> --------------------------------------------------------------------------------------------------------
>
> Key: COLLECTIONS-797
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-797
> Project: Commons Collections
> Issue Type: Improvement
> Components: Collection
> Reporter: Rodion Efremov
> Priority: Minor
> Labels: beginner, newbie, performance
> Attachments: AddAtBeginning.png, AddAtEnd.png, AddAtRandom.png,
> GetAtRandom.png, Iterate.png, IterateAndModify.png, RemoveAtRandom.png,
> RemoveFromBeginning.png, RemoveFromEnd.png
>
>
> (The data structure in question lives in
> [GitHub|https://github.com/coderodde/LinkedList].)
>
> IndexedLinkedList, according to discussion on the mailing list, runs most
> operations faster than TreeList, while still having smaller memory
> fingerprint: in TreeList, for each element there are 3 references, 2 ints and
> 2 booleans. In IndexedLinkedList, for each element there is only 3
> references. (Also, IndexedLinkedList maintains ceil(sqrt(N)) so called
> "fingers", each consisting of a reference to a linked list node Node and an
> int value being the appearance index of Node.)
>
> What comes to the implemented interfaces, they are Deque, List, Cloneable and
> Serializable. All four are implemented fully in accordance to JDK 18.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
