[jira] [Comment Edited] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17565277#comment-17565277 ] Rodion Efremov edited comment on COLLECTIONS-797 at 7/14/22 10:02 AM: -- h3. Below, you can find the performance data. The JMH benchmark project is [here|[https://github.com/coderodde/IndexedLinkedListBenchmark]]. The none-JMH benchmark is [here|https://github.com/coderodde/IndexedLinkedList/tree/main/src/main/java/com/github/coderodde/util/benchmark]. h3. Benchmark with JMH h4. [https://github.com/coderodde/IndexedLinkedList/blob/main/README.md#small-size-data] h4. Small size data ||Operation||ms|| |profileArrayListAddAtIndex|0,074| |profileCursorableLinkedListAddAtIndex|0,185| |profileJavaLinkedListAddAtIndex|0,174| |profileNodeCachingLinkedListAddAtIndex|0,181| |profileRoddeListAddAtIndex|0,116| |profileTreeListAddAtIndex|0,153| | | | |profileArrayListAddCollection|0,127| |profileCursorableLinkedListAddCollection|0,151| |profileJavaLinkedListAddCollection|0,140| |profileNodeCachingLinkedListAddCollection|0,223| |profileRoddeListAddCollection|0,133| |profileTreeListAddCollection|0,413| | | | |profileArrayListAddCollectionAtIndex|0,375| |profileCursorableLinkedListAddCollectionAtIndex|2,989| |profileJavaLinkedListAddCollectionAtIndex|2,899| |profileNodeCachingLinkedListAddCollectionAtIndex|3,079| |profileRoddeListAddCollectionAtIndex|0,327| |profileTreeListAddCollectionAtIndex|1,944| | | | |profileArrayListAddFirst|0,074| |profileCursorableLinkedListAddFirst|0,008| |profileJavaLinkedListAddFirst|0,008| |profileNodeCachingLinkedListAddFirst|0,011| |profileRoddeListAddFirst|0,046| |profileTreeListAddFirst|0,086| | | | |profileArrayListAddLast|0,006| |profileCursorableLinkedListAddLast|0,007| |profileJavaLinkedListAddLast|0,006| |profileNodeCachingLinkedListAddLast|0,015| |profileRoddeListAddLast|0,010| |profileTreeListAddLast|0,082| | | | |profileArrayListGet|0,015| |profileCursorableLinkedListGet|3,738| |profileJavaLinkedListGet|3,721| |profileNodeCachingLinkedListGet|3,758| |profileRoddeListGet|0,144| |profileTreeListGet|0,117| | | | |profileArrayListRemoveAll|0,178| |profileCursorableLinkedListRemoveAll|0,388| |profileJavaLinkedListRemoveAll|19,543| |profileNodeCachingLinkedListRemoveAll|0,377| |profileRoddeListRemoveAll|0,360| |profileTreeListRemoveAll|56,304| | | | |profileArrayListRemoveAtIndex|1,986| |profileCursorableLinkedListRemoveAtIndex|24,609| |profileJavaLinkedListRemoveAtIndex|25,117| |profileNodeCachingLinkedListRemoveAtIndex|28,070| |profileRoddeListRemoveAtIndex|5,798| |profileTreeListRemoveAtIndex|2,978| | | | |profileArrayListRemoveFirst|2,753| |profileCursorableLinkedListRemoveFirst|0,955| |profileJavaLinkedListRemoveFirst|0,139| |profileNodeCachingLinkedListRemoveFirst|0,346| |profileRoddeListRemoveFirst|1,176| |profileTreeListRemoveFirst|1,060| | | | |profileArrayListRemoveLast|0,031| |profileCursorableLinkedListRemoveLast|0,266| |profileJavaLinkedListRemoveLast|0,136| |profileNodeCachingLinkedListRemoveLast|0,379| |profileRoddeListRemoveLast|0,204| |profileTreeListRemoveLast|1,348| | | | |profileArrayListRemoveObject|4,929| |profileCursorableLinkedListRemoveObject|29,639| |profileJavaLinkedListRemoveObject|10,105| |profileNodeCachingLinkedListRemoveObject|11,481| |profileRoddeListRemoveObject|21,035| |profileTreeListRemoveObject|30,990| | | | |profileArrayListRemoveRange|0,051| |profileCursorableLinkedListRemoveRange|11,476| |profileJavaLinkedListRemoveRange|0,540| |profileNodeCachingLinkedListRemoveRange|1,819| |profileRoddeListRemoveRange|0,574| |profileTreeListRemoveRange|7,156| | | | |profileArrayListSortRange|1,412| |profileCursorableLinkedListSortRange|8,641| |profileJavaLinkedListSortRange|1,547| |profileNodeCachingLinkedListSortRange|1,864| |profileRoddeListSortRange|1,488| |profileTreeListSortRange|1,792| | | | |Total of ArrayList|12,012| |Total of JavaLinkedList|64,074| |Total of RoddeList|31,410| |Total of TreeList|104,422| |Total of NodeCachingLinkedList|51,604| |Total of CursorableLinkedList|83,052| h4. [https://github.com/coderodde/IndexedLinkedList/blob/main/README.md#medium-size-data] h4. Medium size data ||Operation||ms|| |profileArrayListAddAtIndex|0,397| |profileCursorableLinkedListAddAtIndex|2,668| |profileJavaLinkedListAddAtIndex|2,653| |profileNodeCachingLinkedListAddAtIndex|2,705| |profileRoddeListAddAtIndex|0,432| |profileTreeListAddAtIndex|0,549| | | | |profileArrayListAddCollection|0,393| |profileCursorableLinkedListAddCollection|0,425| |profileJavaLinkedListAddCollection|0,439| |profileNodeCachingLinkedListAddCollection|0,554| |profileRoddeListAddCollection|0,405| |profileTreeListAddCollection|1,314| | | | |profileArrayListAddCollectionAtIndex|2,108| |profileCursorableLinkedListAddCollectionAtIndex|37,327| |profileJavaLinkedListAddCollectionAtIndex|35,409| |profileNodeCachingLinkedListAddCollectionAtInd
[jira] [Comment Edited] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17565277#comment-17565277 ] Rodion Efremov edited comment on COLLECTIONS-797 at 7/14/22 8:10 AM: - h3. Below, you can find the performance data. The JMH benchmark project is [here|[https://github.com/coderodde/IndexedLinkedListBenchmark]]. The none-JMH benchmark is [here|https://github.com/coderodde/IndexedLinkedList/tree/main/src/main/java/com/github/coderodde/util/benchmark]. h3. Benchmark with JMH h4. [https://github.com/coderodde/IndexedLinkedList/blob/main/README.md#small-size-data] h4. Small size data ||Operation||ms|| |profileArrayListAddAtIndex|0,074| |profileCursorableLinkedListAddAtIndex|0,185| |profileJavaLinkedListAddAtIndex|0,174| |profileNodeCachingLinkedListAddAtIndex|0,181| |profileRoddeListAddAtIndex|0,116| |profileTreeListAddAtIndex|0,153| | | | |profileArrayListAddCollection|0,127| |profileCursorableLinkedListAddCollection|0,151| |profileJavaLinkedListAddCollection|0,140| |profileNodeCachingLinkedListAddCollection|0,223| |profileRoddeListAddCollection|0,133| |profileTreeListAddCollection|0,413| | | | |profileArrayListAddCollectionAtIndex|0,375| |profileCursorableLinkedListAddCollectionAtIndex|2,989| |profileJavaLinkedListAddCollectionAtIndex|2,899| |profileNodeCachingLinkedListAddCollectionAtIndex|3,079| |profileRoddeListAddCollectionAtIndex|0,327| |profileTreeListAddCollectionAtIndex|1,944| | | | |profileArrayListAddFirst|0,074| |profileCursorableLinkedListAddFirst|0,008| |profileJavaLinkedListAddFirst|0,008| |profileNodeCachingLinkedListAddFirst|0,011| |profileRoddeListAddFirst|0,046| |profileTreeListAddFirst|0,086| | | | |profileArrayListAddLast|0,006| |profileCursorableLinkedListAddLast|0,007| |profileJavaLinkedListAddLast|0,006| |profileNodeCachingLinkedListAddLast|0,015| |profileRoddeListAddLast|0,010| |profileTreeListAddLast|0,082| | | | |profileArrayListGet|0,015| |profileCursorableLinkedListGet|3,738| |profileJavaLinkedListGet|3,721| |profileNodeCachingLinkedListGet|3,758| |profileRoddeListGet|0,144| |profileTreeListGet|0,117| | | | |profileArrayListRemoveAll|0,178| |profileCursorableLinkedListRemoveAll|0,388| |profileJavaLinkedListRemoveAll|19,543| |profileNodeCachingLinkedListRemoveAll|0,377| |profileRoddeListRemoveAll|0,360| |profileTreeListRemoveAll|56,304| | | | |profileArrayListRemoveAtIndex|1,986| |profileCursorableLinkedListRemoveAtIndex|24,609| |profileJavaLinkedListRemoveAtIndex|25,117| |profileNodeCachingLinkedListRemoveAtIndex|28,070| |profileRoddeListRemoveAtIndex|5,798| |profileTreeListRemoveAtIndex|2,978| | | | |profileArrayListRemoveFirst|2,753| |profileCursorableLinkedListRemoveFirst|0,955| |profileJavaLinkedListRemoveFirst|0,139| |profileNodeCachingLinkedListRemoveFirst|0,346| |profileRoddeListRemoveFirst|1,176| |profileTreeListRemoveFirst|1,060| | | | |profileArrayListRemoveLast|0,031| |profileCursorableLinkedListRemoveLast|0,266| |profileJavaLinkedListRemoveLast|0,136| |profileNodeCachingLinkedListRemoveLast|0,379| |profileRoddeListRemoveLast|0,204| |profileTreeListRemoveLast|1,348| | | | |profileArrayListRemoveObject|4,929| |profileCursorableLinkedListRemoveObject|29,639| |profileJavaLinkedListRemoveObject|10,105| |profileNodeCachingLinkedListRemoveObject|11,481| |profileRoddeListRemoveObject|21,035| |profileTreeListRemoveObject|30,990| | | | |profileArrayListRemoveRange|0,051| |profileCursorableLinkedListRemoveRange|11,476| |profileJavaLinkedListRemoveRange|0,540| |profileNodeCachingLinkedListRemoveRange|1,819| |profileRoddeListRemoveRange|0,574| |profileTreeListRemoveRange|7,156| | | | |profileArrayListSortRange|1,412| |profileCursorableLinkedListSortRange|8,641| |profileJavaLinkedListSortRange|1,547| |profileNodeCachingLinkedListSortRange|1,864| |profileRoddeListSortRange|1,488| |profileTreeListSortRange|1,792| | | | |Total of ArrayList|12,012| |Total of JavaLinkedList|64,074| |Total of RoddeList|31,410| |Total of TreeList|104,422| |Total of NodeCachingLinkedList|51,604| |Total of CursorableLinkedList|83,052| h4. [https://github.com/coderodde/IndexedLinkedList/blob/main/README.md#medium-size-data] h4. Medium size data ||Operation||ms|| |profileArrayListAddAtIndex|0,397| |profileCursorableLinkedListAddAtIndex|2,668| |profileJavaLinkedListAddAtIndex|2,653| |profileNodeCachingLinkedListAddAtIndex|2,705| |profileRoddeListAddAtIndex|0,432| |profileTreeListAddAtIndex|0,549| | | | |profileArrayListAddCollection|0,393| |profileCursorableLinkedListAddCollection|0,425| |profileJavaLinkedListAddCollection|0,439| |profileNodeCachingLinkedListAddCollection|0,554| |profileRoddeListAddCollection|0,405| |profileTreeListAddCollection|1,314| | | | |profileArrayListAddCollectionAtIndex|2,108| |profileCursorableLinkedListAddCollectionAtIndex|37,327| |profileJavaLinkedListAddCollectionAtIndex|35,409| |profileNodeCachingLinkedListAddCollectionAtIndex
[jira] [Comment Edited] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17565277#comment-17565277 ] Rodion Efremov edited comment on COLLECTIONS-797 at 7/14/22 8:00 AM: - h3. Below, you can find the performance data. The JMH benchmark project is [here|[https://github.com/coderodde/IndexedLinkedListBenchmark]]. The none-JMH benchmark is [here|https://github.com/coderodde/IndexedLinkedList/tree/main/src/main/java/com/github/coderodde/util/benchmark]. h3. Benchmark with JMH h4. [|https://github.com/coderodde/IndexedLinkedList/blob/main/README.md#small-size-data]Small size data ||Operation||ms|| |profileArrayListAddAtIndex|0,074| |profileCursorableLinkedListAddAtIndex|0,185| |profileJavaLinkedListAddAtIndex|0,174| |profileNodeCachingLinkedListAddAtIndex|0,181| |profileRoddeListAddAtIndex|0,116| |profileTreeListAddAtIndex|0,153| | | | |profileArrayListAddCollection|0,127| |profileCursorableLinkedListAddCollection|0,151| |profileJavaLinkedListAddCollection|0,140| |profileNodeCachingLinkedListAddCollection|0,223| |profileRoddeListAddCollection|0,133| |profileTreeListAddCollection|0,413| | | | |profileArrayListAddCollectionAtIndex|0,375| |profileCursorableLinkedListAddCollectionAtIndex|2,989| |profileJavaLinkedListAddCollectionAtIndex|2,899| |profileNodeCachingLinkedListAddCollectionAtIndex|3,079| |profileRoddeListAddCollectionAtIndex|0,327| |profileTreeListAddCollectionAtIndex|1,944| | | | |profileArrayListAddFirst|0,074| |profileCursorableLinkedListAddFirst|0,008| |profileJavaLinkedListAddFirst|0,008| |profileNodeCachingLinkedListAddFirst|0,011| |profileRoddeListAddFirst|0,046| |profileTreeListAddFirst|0,086| | | | |profileArrayListAddLast|0,006| |profileCursorableLinkedListAddLast|0,007| |profileJavaLinkedListAddLast|0,006| |profileNodeCachingLinkedListAddLast|0,015| |profileRoddeListAddLast|0,010| |profileTreeListAddLast|0,082| | | | |profileArrayListGet|0,015| |profileCursorableLinkedListGet|3,738| |profileJavaLinkedListGet|3,721| |profileNodeCachingLinkedListGet|3,758| |profileRoddeListGet|0,144| |profileTreeListGet|0,117| | | | |profileArrayListRemoveAll|0,178| |profileCursorableLinkedListRemoveAll|0,388| |profileJavaLinkedListRemoveAll|19,543| |profileNodeCachingLinkedListRemoveAll|0,377| |profileRoddeListRemoveAll|0,360| |profileTreeListRemoveAll|56,304| | | | |profileArrayListRemoveAtIndex|1,986| |profileCursorableLinkedListRemoveAtIndex|24,609| |profileJavaLinkedListRemoveAtIndex|25,117| |profileNodeCachingLinkedListRemoveAtIndex|28,070| |profileRoddeListRemoveAtIndex|5,798| |profileTreeListRemoveAtIndex|2,978| | | | |profileArrayListRemoveFirst|2,753| |profileCursorableLinkedListRemoveFirst|0,955| |profileJavaLinkedListRemoveFirst|0,139| |profileNodeCachingLinkedListRemoveFirst|0,346| |profileRoddeListRemoveFirst|1,176| |profileTreeListRemoveFirst|1,060| | | | |profileArrayListRemoveLast|0,031| |profileCursorableLinkedListRemoveLast|0,266| |profileJavaLinkedListRemoveLast|0,136| |profileNodeCachingLinkedListRemoveLast|0,379| |profileRoddeListRemoveLast|0,204| |profileTreeListRemoveLast|1,348| | | | |profileArrayListRemoveObject|4,929| |profileCursorableLinkedListRemoveObject|29,639| |profileJavaLinkedListRemoveObject|10,105| |profileNodeCachingLinkedListRemoveObject|11,481| |profileRoddeListRemoveObject|21,035| |profileTreeListRemoveObject|30,990| | | | |profileArrayListRemoveRange|0,051| |profileCursorableLinkedListRemoveRange|11,476| |profileJavaLinkedListRemoveRange|0,540| |profileNodeCachingLinkedListRemoveRange|1,819| |profileRoddeListRemoveRange|0,574| |profileTreeListRemoveRange|7,156| | | | |profileArrayListSortRange|1,412| |profileCursorableLinkedListSortRange|8,641| |profileJavaLinkedListSortRange|1,547| |profileNodeCachingLinkedListSortRange|1,864| |profileRoddeListSortRange|1,488| |profileTreeListSortRange|1,792| | | | |Total of ArrayList|12,012| |Total of JavaLinkedList|64,074| |Total of RoddeList|31,410| |Total of TreeList|104,422| |Total of NodeCachingLinkedList|51,604| |Total of CursorableLinkedList|83,052| h4. [|https://github.com/coderodde/IndexedLinkedList/blob/main/README.md#medium-size-data]Medium size data ||Operation||ms|| |profileArrayListAddAtIndex|0,397| |profileCursorableLinkedListAddAtIndex|2,668| |profileJavaLinkedListAddAtIndex|2,653| |profileNodeCachingLinkedListAddAtIndex|2,705| |profileRoddeListAddAtIndex|0,432| |profileTreeListAddAtIndex|0,549| | | | |profileArrayListAddCollection|0,393| |profileCursorableLinkedListAddCollection|0,425| |profileJavaLinkedListAddCollection|0,439| |profileNodeCachingLinkedListAddCollection|0,554| |profileRoddeListAddCollection|0,405| |profileTreeListAddCollection|1,314| | | | |profileArrayListAddCollectionAtIndex|2,108| |profileCursorableLinkedListAddCollectionAtIndex|37,327| |profileJavaLinkedListAddCollectionAtIndex|35,409| |profileNodeCachingLinkedListAddCollectionAtIndex|36,83
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: IndexedLinkedList.java) > 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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: FingerListTest.java) > 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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: IndexedLinkedListTest.java) > 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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: IndexedLinkedListTest.java FingerListTest.java > 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, > FingerListTest.java, GetAtRandom.png, IndexedLinkedList.java, > IndexedLinkedListTest.java, 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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: IndexedLinkedList.java > 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, IndexedLinkedList.java, 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)
[jira] [Comment Edited] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17565283#comment-17565283 ] Rodion Efremov edited comment on COLLECTIONS-797 at 7/12/22 6:04 AM: - h1. Matt Juntunen's benchmark data (See the performance graphs in the Attachments.) |AddAtBeginning|10|100|1000|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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| was (Author: coderodde): h1. Matt Juntunen's benchmark data |AddAtBeginning|10|100|1000|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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
[jira] [Commented] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ 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|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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|1| |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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: IterateAndModify.png RemoveAtRandom.png RemoveFromBeginning.png RemoveFromEnd.png AddAtBeginning.png AddAtEnd.png AddAtRandom.png GetAtRandom.png Iterate.png > 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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: GetAtRandom.png) > 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: AddAtRandom.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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: AddAtRandom.png) > 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 > > (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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: IterateAndModify.png) > 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: AddAtRandom.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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: RemoveFromBeginning.png) > 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: AddAtRandom.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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: Iterate.png) > 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: AddAtRandom.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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: RemoveAtRandom.png) > 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: AddAtRandom.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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: AddAtEnd.png) > 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: AddAtRandom.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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: RemoveFromEnd.png) > 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: AddAtRandom.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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: (was: AddAtBeginning.png) > 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: AddAtRandom.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)
[jira] [Commented] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17565281#comment-17565281 ] Rodion Efremov commented on COLLECTIONS-797: !AddAtBeginning.png! > 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)
[jira] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797 ] Rodion Efremov deleted comment on COLLECTIONS-797: was (Author: coderodde): !AddAtBeginning.png! > 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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Attachment: AddAtBeginning.png AddAtEnd.png AddAtRandom.png GetAtRandom.png Iterate.png IterateAndModify.png RemoveAtRandom.png RemoveFromBeginning.png RemoveFromEnd.png > 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)
[jira] [Commented] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[
https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17565277#comment-17565277
]
Rodion Efremov commented on COLLECTIONS-797:
h3. Below, you can find the performance data. The JMH benchmark project is
[here|[https://github.com/coderodde/IndexedLinkedListBenchmark]]. The none-JMH
benchmark is
[here|https://github.com/coderodde/IndexedLinkedList/tree/main/src/main/java/com/github/coderodde/util/benchmark].
h3. Benchmark with JMH
h4. Small size data
||Operation||ms||
| | |
|{{profileArrayListAddAtIndex}}|0,084|
|{{profileLinkedListAddAtIndex}}|0,186|
|{{profileRoddeListAddAtIndex}}|0,114|
|{{profileTreeListAddAtIndex}}|0,153|
| | |
|{{profileArrayListAddCollection}}|0,133|
|{{profileLinkedListAddCollection}}|0,118|
|{{profileRoddeListAddCollection}}|0,131|
|{{profileTreeListAddCollection}}|0,408|
| | |
|{{profileArrayListAddCollectionAtIndex}}|0,348|
|{{profileLinkedListAddCollectionAtIndex}}|2,898|
|{{profileRoddeListAddCollectionAtIndex}}|0,315|
|{{profileTreeListAddCollectionAtIndex}}|1,883|
| | |
|{{profileArrayListAddFirst}}|0,074|
|{{profileLinkedListAddFirst}}|0,007|
|{{profileRoddeListAddFirst}}|0,043|
|{{profileTreeListAddFirst}}|0,221|
| | |
|{{profileArrayListAddLast}}|0,005|
|{{profileLinkedListAddLast}}|0,006|
|{{profileRoddeListAddLast}}|0,010|
|{{profileTreeListAddLast}}|0,105|
| | |
|{{profileArrayListGet}}|0,015|
|{{profileLinkedListGet}}|3,840|
|{{profileRoddeListGet}}|0,141|
|{{profileTreeListGet}}|0,155|
| | |
|{{profileArrayListRemoveAll}}|0,164|
|{{profileLinkedListRemoveAll}}|19,716|
|{{profileRoddeListRemoveAll}}|0,362|
|{{profileTreeListRemoveAll}}|57,339|
| | |
|{{profileArrayListRemoveAtIndex}}|2,144|
|{{profileLinkedListRemoveAtIndex}}|24,915|
|{{profileRoddeListRemoveAtIndex}}|4,892|
|{{profileTreeListRemoveAtIndex}}|2,901|
| | |
|{{profileArrayListRemoveFirst}}|3,747|
|{{profileLinkedListRemoveFirst}}|0,191|
|{{profileRoddeListRemoveFirst}}|1,105|
|{{profileTreeListRemoveFirst}}|0,988|
| | |
|{{profileArrayListRemoveLast}}|0,031|
|{{profileLinkedListRemoveLast}}|0,137|
|{{profileRoddeListRemoveLast}}|0,186|
|{{profileTreeListRemoveLast}}|1,381|
| | |
|{{profileArrayListRemoveObject}}|4,617|
|{{profileLinkedListRemoveObject}}|11,606|
|{{profileRoddeListRemoveObject}}|21,167|
|{{profileTreeListRemoveObject}}|33,067|
| | |
|{{profileArrayListRemoveRange}}|0,050|
|{{profileLinkedListRemoveRange}}|0,517|
|{{profileRoddeListRemoveRange}}|0,533|
|{{profileTreeListRemoveRange}}|6,120|
| | |
|{{profileArrayListSortRange}}|1,389|
|{{profileLinkedListSortRange}}|1,507|
|{{profileRoddeListSortRange}}|1,482|
|{{profileTreeListSortRange}}|1,635|
| | |
|Total of {{ArrayList}}|12,800|
|Total of {{LinkedList}}|65,644|
|Total of {{RoddeList}}|30,480|
|Total of {{TreeList}}|106,356|
h4. Medium size data
||Operation||ms||
|{{profileArrayListAddAtIndex}}|0,327|
|{{profileLinkedListAddAtIndex}}|2,599|
|{{profileRoddeListAddAtIndex}}|0,432|
|{{profileTreeListAddAtIndex}}|0,555|
| | |
|{{profileArrayListAddCollection}}|0,386|
|{{profileLinkedListAddCollection}}|0,369|
|{{profileRoddeListAddCollection}}|0,394|
|{{profileTreeListAddCollection}}|1,246|
| | |
|{{profileArrayListAddCollectionAtIndex}}|2,413|
|{{profileLinkedListAddCollectionAtIndex}}|36,648|
|{{profileRoddeListAddCollectionAtIndex}}|1,370|
|{{profileTreeListAddCollectionAtIndex}}|5,880|
| | |
|{{profileArrayListAddFirst}}|0,421|
|{{profileLinkedListAddFirst}}|0,019|
|{{profileRoddeListAddFirst}}|0,141|
|{{profileTreeListAddFirst}}|0,272|
| | |
|{{profileArrayListAddLast}}|0,016|
|{{profileLinkedListAddLast}}|0,017|
|{{profileRoddeListAddLast}}|0,035|
|{{profileTreeListAddLast}}|0,290|
| | |
|{{profileArrayListGet}}|0,054|
|{{profileLinkedListGet}}|35,779|
|{{profileRoddeListGet}}|0,661|
|{{profileTreeListGet}}|0,468|
| | |
|{{profileArrayListRemoveAll}}|0,809|
|{{profileLinkedListRemoveAll}}|172,829|
|{{profileRoddeListRemoveAll}}|1,273|
|{{profileTreeListRemoveAll}}|699,206|
| | |
|{{profileArrayListRemoveAtIndex}}|18,441|
|{{profileLinkedListRemoveAtIndex}}|258,263|
|{{profileRoddeListRemoveAtIndex}}|48,384|
|{{profileTreeListRemoveAtIndex}}|10,126|
| | |
|{{profileArrayListRemoveFirst}}|38,078|
|{{profileLinkedListRemoveFirst}}|0,576|
|{{profileRoddeListRemoveFirst}}|5,176|
|{{profileTreeListRemoveFirst}}|3,377|
| | |
|{{profileArrayListRemoveLast}}|0,089|
|{{profileLinkedListRemoveLast}}|0,576|
|{{profileRoddeListRemoveLast}}|0,863|
|{{profileTreeListRemoveLast}}|3,666|
| | |
|{{profileArrayListRemoveObject}}|46,814|
|{{profileLinkedListRemoveObject}}|105,916|
|{{profileRoddeListRemoveObject}}|191,653|
|{{profileTreeListRemoveObject}}|306,468|
| | |
|{{profileArrayListRemoveRange}}|0,099|
|{{profileLinkedListRemoveRange}}|1,262|
|{{profileRoddeListRemoveRange}}|1,212|
|{{profileTreeListRemoveRange}}|13,690|
| | |
|{{profileArrayListSortRange}}|8,449|
|{{profileLinkedListSortRange}}|9,291|
|
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Description: (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. was: (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. > 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 > > (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)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Description: (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. was: The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList]. The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time. While not (quite) as efficient as the TreeList, my LinkedList requires less memory: where TreeList requires 3 references, 2 ints and 2 booleans per node, my list requires only 3 references per node + ceil(sqrt(N/2)) fingers, one reference and one int per finger. > 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 > > (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)
[jira] [Created] (SANDBOX-512) Load balance the bidirectional Dijkstra's algorithm
Rodion Efremov created SANDBOX-512: -- Summary: Load balance the bidirectional Dijkstra's algorithm Key: SANDBOX-512 URL: https://issues.apache.org/jira/browse/SANDBOX-512 Project: Commons Sandbox Issue Type: Improvement Components: Graph Reporter: Rodion Efremov When iterating the outer loop, pop the new vertex from the smaller search frontiers. -- This message was sent by Atlassian Jira (v8.3.4#803005)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Description: The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList]. The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time. While not (quite) as efficient as the TreeList, my LinkedList requires less memory: where TreeList requires 3 references, 2 ints and 2 booleans per node, my list requires only 3 references per node + ceil(sqrt(N/2)) fingers, one reference and one int per finger. was: The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList]. The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time. While not as efficient as the TreeList, my LinkedList requires less memory: where TreeList requires 3 references, 2 ints and 2 booleans per node, my list requires only 3 references per node + ceil(sqrt(N/2)) fingers, one reference and one int per finger. > 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 > > The data structure in question lives in > [GitHub|https://github.com/coderodde/LinkedList]. > > The idea is that we maintain sqrt(N/2) so called "fingers" along the actual > list. Each finger contains a reference to a list node and an index of that > node. Now, when we need to access a node via an index, we don't have to scan > through the entire linked list, but, instead, only consult all the finger, > choose the closest finger, and iterate from the respective node towards the > target node. > > If the fingers are distributely evenly, also traversal from the node pointed > by a finger to the target node will require O(sqrt(N)) time. > > While not (quite) as efficient as the TreeList, my LinkedList requires less > memory: where TreeList requires 3 references, 2 ints and 2 booleans per node, > my list requires only 3 references per node + ceil(sqrt(N/2)) fingers, one > reference and one int per finger. -- This message was sent by Atlassian Jira (v8.3.4#803005)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Description: The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList]. The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time. While not as efficient as the TreeList, my LinkedList requires less memory: where TreeList requires 3 references, 2 ints and 2 booleans per node, my list requires only 3 references per node + ceil(sqrt(N/2)) fingers, one reference and one int per finger. was: The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList]. The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time. While not as efficient as the TreeList, my LinkedList requires less memory: where TreeList requires 3 references, 2 ints and 2 booleans per node, my list requires only 3 references per node + ceil(N/2) fingers, one reference and one int per finger. > 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 > > The data structure in question lives in > [GitHub|https://github.com/coderodde/LinkedList]. > > The idea is that we maintain sqrt(N/2) so called "fingers" along the actual > list. Each finger contains a reference to a list node and an index of that > node. Now, when we need to access a node via an index, we don't have to scan > through the entire linked list, but, instead, only consult all the finger, > choose the closest finger, and iterate from the respective node towards the > target node. > > If the fingers are distributely evenly, also traversal from the node pointed > by a finger to the target node will require O(sqrt(N)) time. > > While not as efficient as the TreeList, my LinkedList requires less memory: > where TreeList requires 3 references, 2 ints and 2 booleans per node, my list > requires only 3 references per node + ceil(sqrt(N/2)) fingers, one reference > and one int per finger. -- This message was sent by Atlassian Jira (v8.3.4#803005)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Description: The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList]. The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time. While not as efficient as the TreeList, my LinkedList requires less memory: where TreeList requires 3 references, 2 ints and 2 booleans per node, my list requires only 3 references per node + ceil(N/2) fingers, one reference and one int per finger. was: The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList]. The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time. While not as efficient as the TreeList, my LinkedList requires less memory: where TreeList requires 3 references, 2 ints and 2 booleans per node, my list requires only 3 references + ceil(N/2) fingers, one reference and one int per finger. > 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 > > The data structure in question lives in > [GitHub|https://github.com/coderodde/LinkedList]. > > The idea is that we maintain sqrt(N/2) so called "fingers" along the actual > list. Each finger contains a reference to a list node and an index of that > node. Now, when we need to access a node via an index, we don't have to scan > through the entire linked list, but, instead, only consult all the finger, > choose the closest finger, and iterate from the respective node towards the > target node. > > If the fingers are distributely evenly, also traversal from the node pointed > by a finger to the target node will require O(sqrt(N)) time. > > While not as efficient as the TreeList, my LinkedList requires less memory: > where TreeList requires 3 references, 2 ints and 2 booleans per node, my list > requires only 3 references per node + ceil(N/2) fingers, one reference and > one int per finger. -- This message was sent by Atlassian Jira (v8.3.4#803005)
[jira] [Updated] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-797: --- Description: The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList]. The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time. While not as efficient as the TreeList, my LinkedList requires less memory: where TreeList requires 3 references, 2 ints and 2 booleans per node, my list requires only 3 references + ceil(N/2) fingers, one reference and one int per finger. was: The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList]. The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time. > 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 > > The data structure in question lives in > [GitHub|https://github.com/coderodde/LinkedList]. > > The idea is that we maintain sqrt(N/2) so called "fingers" along the actual > list. Each finger contains a reference to a list node and an index of that > node. Now, when we need to access a node via an index, we don't have to scan > through the entire linked list, but, instead, only consult all the finger, > choose the closest finger, and iterate from the respective node towards the > target node. > > If the fingers are distributely evenly, also traversal from the node pointed > by a finger to the target node will require O(sqrt(N)) time. > > While not as efficient as the TreeList, my LinkedList requires less memory: > where TreeList requires 3 references, 2 ints and 2 booleans per node, my list > requires only 3 references + ceil(N/2) fingers, one reference and one int > per finger. -- This message was sent by Atlassian Jira (v8.3.4#803005)
[jira] [Created] (COLLECTIONS-797) An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)
Rodion Efremov created COLLECTIONS-797: -- Summary: 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 The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList]. The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time. -- This message was sent by Atlassian Jira (v8.3.4#803005)
[jira] [Created] (COLLECTIONS-607) Adding a hash table based BidiMap
Rodion Efremov created COLLECTIONS-607: -- Summary: Adding a hash table based BidiMap Key: COLLECTIONS-607 URL: https://issues.apache.org/jira/browse/COLLECTIONS-607 Project: Commons Collections Issue Type: New Feature Components: BidiMap Reporter: Rodion Efremov Priority: Minor In the class Javadoc of http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/bidimap/DualHashBidiMap.java?view=markup there is a mention that Collections would welcome a direct hash-based implementation of BidiMap interface. I am working on such; my source is available at https://github.com/coderodde/BidirectionalHashMap At this point it does not adhere to style/interfaces of Commons Collections (such as implementing the BidiMap interface), yet I believe that is a matter of simple rewrite. Currently, it represents the "collision chains" as AVL-trees, thus guaranteeing O(log n) access/modification even on poor hash functions. If that is not required, rewriting would be trivial as well. I have several questions, but I have to start from the most important: is there any acute need for such a data structure? -- This message was sent by Atlassian JIRA (v6.4.14#64029)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15148762#comment-15148762 ] Rodion Efremov commented on COLLECTIONS-479: I am more or less done with a Set-implementation that provides methods get(int index) and indexOf(T element); both run in O(log N). See here: https://github.com/coderodde/OrderStatisticTree However, if a Map is required, please tell me, should not take much time to refactor. Best, rodde > An Order Statistic Tree > --- > > Key: COLLECTIONS-479 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 > Project: Commons Collections > Issue Type: New Feature >Reporter: Ajo Fod >Priority: Minor > Fix For: 4.x > > Attachments: COLLECTIONS-479.patch, NodeExistsException.java, > RedBlackBST.java > > > An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree > provides two useful properties. The ability to rank arbitrary keys relative > to keys existing in the tree AND the ability to retrieve elements from the > tree with the given rank. > This can be used to find the percentile rank of a key for example. > This functionality is not yet provided yet by any of the major libraries > AFAIK. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15143246#comment-15143246 ] Rodion Efremov commented on COLLECTIONS-479: Hello everybody! I wasn't able to work on this one after all. However, I started today from scratch and have a progress on counted AVL-tree: insert, lookup and deletion implemented. Just lacks the actual counts needed for making it an order statistic tree. Question: what interfaces should I implement? java.util.Set seems like natural choice, but there might be more. What would be your opinion on this one? > An Order Statistic Tree > --- > > Key: COLLECTIONS-479 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 > Project: Commons Collections > Issue Type: New Feature >Reporter: Ajo Fod >Priority: Minor > Fix For: 4.x > > Attachments: COLLECTIONS-479.patch, NodeExistsException.java, > RedBlackBST.java > > > An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree > provides two useful properties. The ability to rank arbitrary keys relative > to keys existing in the tree AND the ability to retrieve elements from the > tree with the given rank. > This can be used to find the percentile rank of a key for example. > This functionality is not yet provided yet by any of the major libraries > AFAIK. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Updated] (COLLECTIONS-479) An Order Statistic Tree
[
https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Rodion Efremov updated COLLECTIONS-479:
---
Attachment: COLLECTIONS-479.patch
The patch applies 2 files: {{OrderStatisticTree.java}} and its test file
{{OrderStatisticTreeTest.java}}.
> An Order Statistic Tree
> ---
>
> Key: COLLECTIONS-479
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-479
> Project: Commons Collections
> Issue Type: New Feature
>Reporter: Ajo Fod
>Priority: Minor
> Attachments: COLLECTIONS-479.patch, NodeExistsException.java,
> RedBlackBST.java
>
>
> An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree
> provides two useful properties. The ability to rank arbitrary keys relative
> to keys existing in the tree AND the ability to retrieve elements from the
> tree with the given rank.
> This can be used to find the percentile rank of a key for example.
> This functionality is not yet provided yet by any of the major libraries
> AFAIK.
--
This message was sent by Atlassian JIRA
(v6.1.4#6159)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[
https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13854440#comment-13854440
]
Rodion Efremov commented on COLLECTIONS-479:
What package should I put it in? Might
'{{org.apache.commons.collections4.map}}' be the right place?
> An Order Statistic Tree
> ---
>
> Key: COLLECTIONS-479
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-479
> Project: Commons Collections
> Issue Type: New Feature
>Reporter: Ajo Fod
>Priority: Minor
> Attachments: NodeExistsException.java, RedBlackBST.java
>
>
> An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree
> provides two useful properties. The ability to rank arbitrary keys relative
> to keys existing in the tree AND the ability to retrieve elements from the
> tree with the given rank.
> This can be used to find the percentile rank of a key for example.
> This functionality is not yet provided yet by any of the major libraries
> AFAIK.
--
This message was sent by Atlassian JIRA
(v6.1.4#6159)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13854155#comment-13854155 ] Rodion Efremov commented on COLLECTIONS-479: Hello, y'all! Might the ordered statistic tree look anything like [this|https://github.com/coderodde/cskit/blob/master/src/main/java/net/coderodde/cskit/ds/tree/OrderStatisticTree.java]? Rodde > An Order Statistic Tree > --- > > Key: COLLECTIONS-479 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 > Project: Commons Collections > Issue Type: New Feature >Reporter: Ajo Fod >Priority: Minor > Attachments: NodeExistsException.java, RedBlackBST.java > > > An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree > provides two useful properties. The ability to rank arbitrary keys relative > to keys existing in the tree AND the ability to retrieve elements from the > tree with the given rank. > This can be used to find the percentile rank of a key for example. > This functionality is not yet provided yet by any of the major libraries > AFAIK. -- This message was sent by Atlassian JIRA (v6.1.4#6159)
[jira] [Commented] (COLLECTIONS-479) An Order Statistic Tree
[ https://issues.apache.org/jira/browse/COLLECTIONS-479?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13761740#comment-13761740 ] Rodion Efremov commented on COLLECTIONS-479: Hello, Thomas. Could you assign me to this issue? I just might come up with the implementation in a week or so. > An Order Statistic Tree > --- > > Key: COLLECTIONS-479 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-479 > Project: Commons Collections > Issue Type: New Feature >Reporter: Ajo Fod >Priority: Minor > Attachments: NodeExistsException.java, RedBlackBST.java > > > An order statistic tree http://en.wikipedia.org/wiki/Order_statistic_tree > provides two useful properties. The ability to rank arbitrary keys relative > to keys existing in the tree AND the ability to retrieve elements from the > tree with the given rank. > This can be used to find the percentile rank of a key for example. > This functionality is not yet provided yet by any of the major libraries > AFAIK. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (COLLECTIONS-431) Add useful collections from commons-graph
[ https://issues.apache.org/jira/browse/COLLECTIONS-431?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-431: --- Attachment: COLLECTIONS-431.patch Importing FibonacciHeap and DisjointSet from Commons Sandbox Graph. > Add useful collections from commons-graph > - > > Key: COLLECTIONS-431 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-431 > Project: Commons Collections > Issue Type: Improvement >Affects Versions: 4.0 >Reporter: Thomas Neidhart > Fix For: 4.x > > Attachments: COLLECTIONS-431.patch > > > Commons-graph has support for DisjointSet and FibonacciHeap which could be of > interest also for CC. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (COLLECTIONS-480) BidiMap.values() should be declared to return a Set
[ https://issues.apache.org/jira/browse/COLLECTIONS-480?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated COLLECTIONS-480: --- Attachment: COLLECTIONS-480.patch This fix was trivial as KeyValue(VALUE) is already an AbstractSet. > BidiMap.values() should be declared to return a Set > --- > > Key: COLLECTIONS-480 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-480 > Project: Commons Collections > Issue Type: Improvement > Components: BidiMap >Affects Versions: 4.0-alpha1 >Reporter: Hollis Waite >Priority: Minor > Attachments: COLLECTIONS-480.patch > > > Since values are guaranteed to be unique, BidiMap.values() should be > overridden to return a Set. See http://sourceforge.net/p/collections/bugs/1. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Comment Edited] (COLLECTIONS-480) BidiMap.values() should be declared to return a Set
[ https://issues.apache.org/jira/browse/COLLECTIONS-480?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13761599#comment-13761599 ] Rodion Efremov edited comment on COLLECTIONS-480 at 9/9/13 3:55 AM: Hollis, can you please write down what concrete classes are affected by this issue as I am interest to fix it? was (Author: coderodde): Hollis, can you please write down what concrete classes are affected by this issue? > BidiMap.values() should be declared to return a Set > --- > > Key: COLLECTIONS-480 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-480 > Project: Commons Collections > Issue Type: Improvement > Components: BidiMap >Affects Versions: 4.0-alpha1 >Reporter: Hollis Waite >Priority: Minor > > Since values are guaranteed to be unique, BidiMap.values() should be > overridden to return a Set. See http://sourceforge.net/p/collections/bugs/1. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (COLLECTIONS-480) BidiMap.values() should be declared to return a Set
[ https://issues.apache.org/jira/browse/COLLECTIONS-480?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13761599#comment-13761599 ] Rodion Efremov commented on COLLECTIONS-480: Hollis, can you please write down what concrete classes are affected by this issue? > BidiMap.values() should be declared to return a Set > --- > > Key: COLLECTIONS-480 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-480 > Project: Commons Collections > Issue Type: Improvement > Components: BidiMap >Affects Versions: 4.0-alpha1 >Reporter: Hollis Waite >Priority: Minor > > Since values are guaranteed to be unique, BidiMap.values() should be > overridden to return a Set. See http://sourceforge.net/p/collections/bugs/1. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Closed] (SANDBOX-460) In the uni- and bidirectional Dijkstra's algorithms there are a superfluous operations.
[ https://issues.apache.org/jira/browse/SANDBOX-460?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov closed SANDBOX-460. -- Resolution: Not A Problem Magically, that extra computation pays well. > In the uni- and bidirectional Dijkstra's algorithms there are a superfluous > operations. > --- > > Key: SANDBOX-460 > URL: https://issues.apache.org/jira/browse/SANDBOX-460 > Project: Commons Sandbox > Issue Type: Improvement > Components: Graph >Affects Versions: Nightly Builds >Reporter: Rodion Efremov >Priority: Trivial > Labels: patch > Fix For: Nightly Builds > > Original Estimate: 48h > Remaining Estimate: 48h > > In the > org.apache.commons.graph.shortestpath.DefaultShortestPathAlgorithmSelector > there are such expressions as 'if (shortestDistancesForward.alreadyVisited( > vertex))', which does nothing reasonable, but rather checks an invariant. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Created] (SANDBOX-460) In the uni- and bidirectional Dijkstra's algorithms there are a superfluous operations.
Rodion Efremov created SANDBOX-460: -- Summary: In the uni- and bidirectional Dijkstra's algorithms there are a superfluous operations. Key: SANDBOX-460 URL: https://issues.apache.org/jira/browse/SANDBOX-460 Project: Commons Sandbox Issue Type: Improvement Components: Graph Affects Versions: Nightly Builds Reporter: Rodion Efremov Priority: Trivial Fix For: Nightly Builds In the org.apache.commons.graph.shortestpath.DefaultShortestPathAlgorithmSelector there are such expressions as 'if (shortestDistancesForward.alreadyVisited( vertex))', which does nothing reasonable, but rather checks an invariant. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (SANDBOX-457) Adding an implementation of a bidirectional Dijkstra's algorithm
[ https://issues.apache.org/jira/browse/SANDBOX-457?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated SANDBOX-457: --- Attachment: SANDBOX-457.patch Added javadoc to buildPath(V, V, V, PredecessorList), and removed java.util.Deque from UniVsBiDijkstraBenchmarkTestCase.java. > Adding an implementation of a bidirectional Dijkstra's algorithm > > > Key: SANDBOX-457 > URL: https://issues.apache.org/jira/browse/SANDBOX-457 > Project: Commons Sandbox > Issue Type: New Feature > Components: Graph >Reporter: Rodion Efremov >Priority: Minor > Labels: newbie, performance > Attachments: bidir.patch, SANDBOX-457.patch > > > The bidirectional Dijkstra's algorithm as described in [these > slides|http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf]. > Performed around 10 times faster than unidirectional variant in the supplied > benchmark. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (SANDBOX-457) Adding an implementation of a bidirectional Dijkstra's algorithm
[ https://issues.apache.org/jira/browse/SANDBOX-457?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13661339#comment-13661339 ] Rodion Efremov commented on SANDBOX-457: Thanks for your time, Simone! Will attach new patch ASAP (most likely within next 36 hours). Btw, I can now see you watching this issue. Does it imply, that you will be automatically notified when new patch arrives to SANDBOX-457? (Would not like to keep on spamming dev@commons mailing list.) With regards, rodde. > Adding an implementation of a bidirectional Dijkstra's algorithm > > > Key: SANDBOX-457 > URL: https://issues.apache.org/jira/browse/SANDBOX-457 > Project: Commons Sandbox > Issue Type: New Feature > Components: Graph >Reporter: Rodion Efremov >Priority: Minor > Labels: newbie, performance > Attachments: bidir.patch > > > The bidirectional Dijkstra's algorithm as described in [these > slides|http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf]. > Performed around 10 times faster than unidirectional variant in the supplied > benchmark. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (SANDBOX-457) Adding an implementation of a bidirectional Dijkstra's algorithm
[ https://issues.apache.org/jira/browse/SANDBOX-457?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated SANDBOX-457: --- Description: The bidirectional Dijkstra's algorithm as described in [these slides|http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf]. Performed around 10 times faster than unidirectional variant in the supplied benchmark. (was: A bidirectional Dijkstra's algorithm as described in [these slides|http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf]. Performed around 10 times faster then unidirectional variant in a supplied benchmark.) > Adding an implementation of a bidirectional Dijkstra's algorithm > > > Key: SANDBOX-457 > URL: https://issues.apache.org/jira/browse/SANDBOX-457 > Project: Commons Sandbox > Issue Type: New Feature > Components: Graph >Reporter: Rodion Efremov >Priority: Minor > Labels: newbie, performance > Attachments: bidir.patch > > > The bidirectional Dijkstra's algorithm as described in [these > slides|http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf]. > Performed around 10 times faster than unidirectional variant in the supplied > benchmark. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (SANDBOX-457) Adding an implementation of a bidirectional Dijkstra's algorithm
[ https://issues.apache.org/jira/browse/SANDBOX-457?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated SANDBOX-457: --- Description: A bidirectional Dijkstra's algorithm as described in [these slides|http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf]. Performed around 10 times faster then unidirectional variant in a supplied benchmark. > Adding an implementation of a bidirectional Dijkstra's algorithm > > > Key: SANDBOX-457 > URL: https://issues.apache.org/jira/browse/SANDBOX-457 > Project: Commons Sandbox > Issue Type: New Feature > Components: Graph >Reporter: Rodion Efremov >Priority: Minor > Labels: newbie, performance > Attachments: bidir.patch > > > A bidirectional Dijkstra's algorithm as described in [these > slides|http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf]. > Performed around 10 times faster then unidirectional variant in a supplied > benchmark. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (SANDBOX-457) Adding an implementation of a bidirectional Dijkstra's algorithm
[ https://issues.apache.org/jira/browse/SANDBOX-457?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Rodion Efremov updated SANDBOX-457: --- Attachment: bidir.patch > Adding an implementation of a bidirectional Dijkstra's algorithm > > > Key: SANDBOX-457 > URL: https://issues.apache.org/jira/browse/SANDBOX-457 > Project: Commons Sandbox > Issue Type: New Feature > Components: Graph >Reporter: Rodion Efremov >Priority: Minor > Labels: newbie, performance > Attachments: bidir.patch > > -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Created] (SANDBOX-457) Adding an implementation of a bidirectional Dijkstra's algorithm
Rodion Efremov created SANDBOX-457: -- Summary: Adding an implementation of a bidirectional Dijkstra's algorithm Key: SANDBOX-457 URL: https://issues.apache.org/jira/browse/SANDBOX-457 Project: Commons Sandbox Issue Type: New Feature Components: Graph Reporter: Rodion Efremov Priority: Minor -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
