Re: [collections]

[Rodion Efremov]

Hello,

Fair enough. However, why we have CursorableLinkedList and
NodeCachingLinkedList around when my previous benchmarking showed that they
are inferior compated to both TreeList and IndexedLinkedList?

Also, note that TreeList requires 3 references, 2 ints and 2 booleans per
node. IndexedLinkedList requires only 3  references per node.

If you need benchmarking on small lists, just tell me and I will arrange
that.

rodde

ti 9.4.2024 klo 22.17 Gary Gregory  kirjoitti:

> Hm... how about all the existing "Linked" classes in the JRE:
> java.util.LinkedList and so on.
>
> Gary
>
> On Tue, Apr 9, 2024 at 2:50 PM Elliotte Rusty Harold 
> wrote:
> >
> > How does it compare to a simple array or ArrayList? Given modern CPU
> > architecture and caching, I rarely encounter real world use cases
> > where a linked list outperforms an array list, no matter what the data
> > structures textbooks say. Maybe on very large lists with a lot of
> > mutations, though last I checked the size where this came into play
> > was 100K elements and growing. Maybe your algorithm is faster. I don't
> > know.
> >
> >
> https://www.reddit.com/r/learnprogramming/comments/10hwrmy/why_arent_linked_lists_more_popular/
> >
> >
> >
> > On Tue, Apr 9, 2024 at 9:01 AM Rodion Efremov 
> wrote:
> > >
> > > Good day,
> > >
> > > I would like to propose a Deque/List that is implemented as a doubly
> linked
> > > list with a sublinear index speeding up single-element operations to
> > > (likely) O(sqrt(n)). It passes a benchmark faster than TreeList by the
> > > factor of around 5.
> > >
> > > The data structure is hosted in GitHub:
> > > https://github.com/coderodde/IndexedLinkedList
> > >
> > > Does it have potential to be included in Collections?
> > >
> > > Best regards,
> > > rodde
> >
> >
> >
> > --
> > Elliotte Rusty Harold
> > elh...@ibiblio.org
> >
> > -
> > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > For additional commands, e-mail: dev-h...@commons.apache.org
> >
>
> -
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>

[collections]

[Rodion Efremov]

Good day,

I would like to propose a Deque/List that is implemented as a doubly linked
list with a sublinear index speeding up single-element operations to
(likely) O(sqrt(n)). It passes a benchmark faster than TreeList by the
factor of around 5.

The data structure is hosted in GitHub:
https://github.com/coderodde/IndexedLinkedList

Does it have potential to be included in Collections?

Best regards,
rodde

Re: [collections] Benchmark all 6 lists

[Rodion Efremov]

Hello community,

I hereby decided to mail the list since my last message did not produce any
response.

Question: should I give up on the process of inclusion of my
IndexedLinkedList to the [collections]?

Best regards,
rodde

la 16.7.2022 klo 6.17 Rodion Efremov  kirjoitti:

> Hello,
>
> I have benchmarked
> 1. ArrayList
> 2. LinkedList
> 3. IndexedLinkedList
> 4. NodeCachingLinkedList
> 5. CursorableLinkedList
> 6. TreeList
>
> IndexedLinkedList outperforms all other lists except ArrayList.
>
> See:
> https://issues.apache.org/jira/plugins/servlet/mobile#issue/COLLECTIONS-797
>
> Best regards,
> rodde
>

[collections] Benchmark all 6 lists

[Rodion Efremov]

Hello,

I have benchmarked
1. ArrayList
2. LinkedList
3. IndexedLinkedList
4. NodeCachingLinkedList
5. CursorableLinkedList
6. TreeList

IndexedLinkedList outperforms all other lists except ArrayList.

See:
https://issues.apache.org/jira/plugins/servlet/mobile#issue/COLLECTIONS-797

Best regards,
rodde

Re: [collections] An AVL-tree based sorted set implementing get by index and indexOf by key

[Rodion Efremov]

Hi Gary,

I can’t follow the source code of the 2 DS you mentioned. Could you,
please, explain how, say, TreeSet can be used for O(log N) select/rank?

I, however, noticed that JDK Sets rely internally on corresponding Maps
thus wasting a reference per element in a Set.

Best regards,
rodde


ke 13.7.2022 klo 15.12 Gary Gregory  kirjoitti:

> Hi Rodde,
>
> Why would a user use this implementation instead of a
> ConcurrentSkipListSet or a TreeSet?
>
> IMO, we need to consider users first, IOW, what is the use case?
>
> Gary
>
> On Wed, Jul 13, 2022 at 1:48 AM Rodion Efremov 
> wrote:
> >
> > Hello,
> >
> > I have an order statistic tree implemented [1]. I am aware of a red/black
> > BST version of the sama ADT [2]. However, [1] implements the Set
> interface;
> > [2] implements none.
> >
> > What do you think about it?
> >
> > Best regards,
> > rodde
> >
> > [1]
> > https://github.com/coderodde/OrderStatisticTree
> > [2]
> >
> https://issues.apache.org/jira/projects/COLLECTIONS/issues/COLLECTIONS-479
>
> -
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>

[collections] An AVL-tree based sorted set implementing get by index and indexOf by key

[Rodion Efremov]

Hello,

I have an order statistic tree implemented [1]. I am aware of a red/black
BST version of the sama ADT [2]. However, [1] implements the Set interface;
[2] implements none.

What do you think about it?

Best regards,
rodde

[1]
https://github.com/coderodde/OrderStatisticTree
[2]
https://issues.apache.org/jira/projects/COLLECTIONS/issues/COLLECTIONS-479

Re: [collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hi community,

I have created a PR: https://github.com/apache/commons-collections/pull/321
Also, I signed the ASF ICLA and sent it to secret...@apache.org

Best regards,
rodde

On Wed, Jul 13, 2022 at 6:18 AM Rodion Efremov  wrote:

> Hi Matt and community,
>
> Answering the first question: yes, it’s entirely my work and I don’t
> expect it to appear in CS literature since the idea behind it and the
> implementation are rather simple and straightforward, albeit with many
> corner cases.
>
> About OCA: is Postal Address and Country mandatory?
>
> Best regards,
> rodde
>
> ke 13.7.2022 klo 0.15 Matt Juntunen  kirjoitti:
>
>> Is this algorithm and its implementation entirely your own work? If
>> so, first of all, that's awesome! Thanks for the contribution! Second,
>> go ahead and update the license. You'll also need to have a
>> Contributor License Agreement [1] on file with the ASF. I think that
>> covers it. If I'm forgetting something, someone please chime in.
>>
>> Regards,
>> Matt J
>>
>> [1] https://www.apache.org/licenses/contributor-agreements.html#clas
>>
>> On Tue, Jul 12, 2022 at 4:08 PM Rodion Efremov 
>> wrote:
>> >
>> > Hello,
>> >
>> > Should I change the license from MIT to Apache License 2.0 before PRing
>> it?
>> >
>> > Best regards,
>> > rodde
>> >
>> > ti 12.7.2022 klo 22.49 Matt Juntunen 
>> kirjoitti:
>> >
>> > > Thanks! We should be ready for you to put together a PR for this. Have
>> > > we cleared any licensing or copyright issues on this algorithm? I
>> > > can't recall.
>> > >
>> > > Regards,
>> > > Matt J
>> > >
>> > > On Tue, Jul 12, 2022 at 2:06 AM Rodion Efremov 
>> > > wrote:
>> > > >
>> > > > Hello,
>> > > >
>> > > > I have added the benchmark data (both my and Matt's) to the JIRA
>> issue.
>> > > > Please see the
>> https://issues.apache.org/jira/browse/COLLECTIONS-797
>> > > >
>> > > > Best  regards,
>> > > > rodde
>> > > >
>> > > > On Tue, Jul 12, 2022 at 2:34 AM Alex Herbert <
>> alex.d.herb...@gmail.com>
>> > > > wrote:
>> > > >
>> > > > > On Mon, 11 Jul 2022 at 17:16, Gilles Sadowski <
>> gillese...@gmail.com>
>> > > > > wrote:
>> > > > >
>> > > > > > Le lun. 11 juil. 2022 à 09:51, Rodion Efremov <
>> codero...@gmail.com>
>> > > a
>> > > > > > écrit :
>> > > > > > >
>> > > > > > > Hi Gilles,
>> > > > > > >
>> > > > > > > Would it be sufficient to include .txt files for the tables
>> and the
>> > > > > .ods
>> > > > > > > file provided by Matt?
>> > > > > >
>> > > > > > It would be more handy for readers that tables are inserted
>> "inline"
>> > > > > > within a comment (using the JIRA syntax) and plots are uploaded
>> > > > > > as PNG images.  See e.g. this report:
>> > > > > > https://issues.apache.org/jira/browse/NUMBERS-156
>> > > > >
>> > > > >
>> > > > > Note that the Jira web editor will accept a table copied from
>> > > > > Excel/OpenOffice and pasted in when in 'Visual' mode. You can then
>> > > switch
>> > > > > from 'Visual' to 'Text' mode to see the raw JIRA syntax and make
>> > > changes to
>> > > > > improve the layout. The 'Visual' mode has some editor buttons to
>> > > manipulate
>> > > > > the table.
>> > > > >
>> > > > > Alex
>> > > > >
>> > >
>> > > -
>> > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
>> > > For additional commands, e-mail: dev-h...@commons.apache.org
>> > >
>> > >
>>
>> -
>> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
>> For additional commands, e-mail: dev-h...@commons.apache.org
>>
>>

Re: [collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hi Matt and community,

Answering the first question: yes, it’s entirely my work and I don’t expect
it to appear in CS literature since the idea behind it and the
implementation are rather simple and straightforward, albeit with many
corner cases.

About OCA: is Postal Address and Country mandatory?

Best regards,
rodde

ke 13.7.2022 klo 0.15 Matt Juntunen  kirjoitti:

> Is this algorithm and its implementation entirely your own work? If
> so, first of all, that's awesome! Thanks for the contribution! Second,
> go ahead and update the license. You'll also need to have a
> Contributor License Agreement [1] on file with the ASF. I think that
> covers it. If I'm forgetting something, someone please chime in.
>
> Regards,
> Matt J
>
> [1] https://www.apache.org/licenses/contributor-agreements.html#clas
>
> On Tue, Jul 12, 2022 at 4:08 PM Rodion Efremov 
> wrote:
> >
> > Hello,
> >
> > Should I change the license from MIT to Apache License 2.0 before PRing
> it?
> >
> > Best regards,
> > rodde
> >
> > ti 12.7.2022 klo 22.49 Matt Juntunen 
> kirjoitti:
> >
> > > Thanks! We should be ready for you to put together a PR for this. Have
> > > we cleared any licensing or copyright issues on this algorithm? I
> > > can't recall.
> > >
> > > Regards,
> > > Matt J
> > >
> > > On Tue, Jul 12, 2022 at 2:06 AM Rodion Efremov 
> > > wrote:
> > > >
> > > > Hello,
> > > >
> > > > I have added the benchmark data (both my and Matt's) to the JIRA
> issue.
> > > > Please see the https://issues.apache.org/jira/browse/COLLECTIONS-797
> > > >
> > > > Best  regards,
> > > > rodde
> > > >
> > > > On Tue, Jul 12, 2022 at 2:34 AM Alex Herbert <
> alex.d.herb...@gmail.com>
> > > > wrote:
> > > >
> > > > > On Mon, 11 Jul 2022 at 17:16, Gilles Sadowski <
> gillese...@gmail.com>
> > > > > wrote:
> > > > >
> > > > > > Le lun. 11 juil. 2022 à 09:51, Rodion Efremov <
> codero...@gmail.com>
> > > a
> > > > > > écrit :
> > > > > > >
> > > > > > > Hi Gilles,
> > > > > > >
> > > > > > > Would it be sufficient to include .txt files for the tables
> and the
> > > > > .ods
> > > > > > > file provided by Matt?
> > > > > >
> > > > > > It would be more handy for readers that tables are inserted
> "inline"
> > > > > > within a comment (using the JIRA syntax) and plots are uploaded
> > > > > > as PNG images.  See e.g. this report:
> > > > > > https://issues.apache.org/jira/browse/NUMBERS-156
> > > > >
> > > > >
> > > > > Note that the Jira web editor will accept a table copied from
> > > > > Excel/OpenOffice and pasted in when in 'Visual' mode. You can then
> > > switch
> > > > > from 'Visual' to 'Text' mode to see the raw JIRA syntax and make
> > > changes to
> > > > > improve the layout. The 'Visual' mode has some editor buttons to
> > > manipulate
> > > > > the table.
> > > > >
> > > > > Alex
> > > > >
> > >
> > > -
> > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > > For additional commands, e-mail: dev-h...@commons.apache.org
> > >
> > >
>
> -
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>

Re: [collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hello,

Should I change the license from MIT to Apache License 2.0 before PRing it?

Best regards,
rodde

ti 12.7.2022 klo 22.49 Matt Juntunen  kirjoitti:

> Thanks! We should be ready for you to put together a PR for this. Have
> we cleared any licensing or copyright issues on this algorithm? I
> can't recall.
>
> Regards,
> Matt J
>
> On Tue, Jul 12, 2022 at 2:06 AM Rodion Efremov 
> wrote:
> >
> > Hello,
> >
> > I have added the benchmark data (both my and Matt's) to the JIRA issue.
> > Please see the https://issues.apache.org/jira/browse/COLLECTIONS-797
> >
> > Best  regards,
> > rodde
> >
> > On Tue, Jul 12, 2022 at 2:34 AM Alex Herbert 
> > wrote:
> >
> > > On Mon, 11 Jul 2022 at 17:16, Gilles Sadowski 
> > > wrote:
> > >
> > > > Le lun. 11 juil. 2022 à 09:51, Rodion Efremov 
> a
> > > > écrit :
> > > > >
> > > > > Hi Gilles,
> > > > >
> > > > > Would it be sufficient to include .txt files for the tables and the
> > > .ods
> > > > > file provided by Matt?
> > > >
> > > > It would be more handy for readers that tables are inserted "inline"
> > > > within a comment (using the JIRA syntax) and plots are uploaded
> > > > as PNG images.  See e.g. this report:
> > > > https://issues.apache.org/jira/browse/NUMBERS-156
> > >
> > >
> > > Note that the Jira web editor will accept a table copied from
> > > Excel/OpenOffice and pasted in when in 'Visual' mode. You can then
> switch
> > > from 'Visual' to 'Text' mode to see the raw JIRA syntax and make
> changes to
> > > improve the layout. The 'Visual' mode has some editor buttons to
> manipulate
> > > the table.
> > >
> > > Alex
> > >
>
> -
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>

Re: [collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hello,

I have added the benchmark data (both my and Matt's) to the JIRA issue.
Please see the https://issues.apache.org/jira/browse/COLLECTIONS-797

Best  regards,
rodde

On Tue, Jul 12, 2022 at 2:34 AM Alex Herbert 
wrote:

> On Mon, 11 Jul 2022 at 17:16, Gilles Sadowski 
> wrote:
>
> > Le lun. 11 juil. 2022 à 09:51, Rodion Efremov  a
> > écrit :
> > >
> > > Hi Gilles,
> > >
> > > Would it be sufficient to include .txt files for the tables and the
> .ods
> > > file provided by Matt?
> >
> > It would be more handy for readers that tables are inserted "inline"
> > within a comment (using the JIRA syntax) and plots are uploaded
> > as PNG images.  See e.g. this report:
> > https://issues.apache.org/jira/browse/NUMBERS-156
>
>
> Note that the Jira web editor will accept a table copied from
> Excel/OpenOffice and pasted in when in 'Visual' mode. You can then switch
> from 'Visual' to 'Text' mode to see the raw JIRA syntax and make changes to
> improve the layout. The 'Visual' mode has some editor buttons to manipulate
> the table.
>
> Alex
>

Re: [collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hi Gilles,

Would it be sufficient to include .txt files for the tables and the .ods
file provided by Matt?

Best regards,
rodde

ma 11.7.2022 klo 10.33 Gilles Sadowski  kirjoitti:

> Hi.
>
> Le lun. 11 juil. 2022 à 07:23, Rodion Efremov  a
> écrit :
> >
> > Hello Matt and community,
> >
> > I have created an ASF JIRA issue back in the days:
> >
> https://issues.apache.org/jira/projects/COLLECTIONS/issues/COLLECTIONS-797?filter=allopenissues
>
> I suggest that the benchmark tables and figures be copied over there.
> [Preferably, in separate files in formats that can be readily
> displayed in a browser.]
>
> Gilles
>
> >
> > Best regards,
> > rodde
> >
> > On Mon, Jul 11, 2022 at 6:23 AM Matt Juntunen  >
> > wrote:
> >
> > > Hello rodde,
> > >
> > > Thanks for your patience while I looked at this. I've made a PR [1] on
> > > your benchmark project with an updated benchmark class. (I used the
> > > completely uninspired class name of IndexedLinkedListPerformance2 :-)
> > > The results back up what you've been saying about the performance of
> > > this list implementation. I've attached a spreadsheet summarizing the
> > > data for a number of different operations along with some images of
> > > some of the most interesting comparisons. I've compared results for
> > > java.util.ArrayList, java.util.LinkedList,
> > > org.apache.commons.collections4.list.TreeList, and
> > > com.github.coderodde.util.IndexedLinkedList (the list in question
> > > here) using JDK 18 on list sizes of 10, 100, 1000, and 1.
> > >
> > > Below are some notes on the attached images.
> > > - get-random.png - Displays timings for element access at random
> > > indices. As expected, ArrayList is by far the best. TreeList and
> > > IndexedLinkedList are relatively close to each other but
> > > IndexedLinkedList is consistently faster. LinkedList was too terrible
> > > to even include on the graph.
> > > - iterate.png - Displays timings for list traversal using the list's
> > > iterator. This was unexpectedly bad for TreeList, which performed far
> > > worse than the others. The performance of IndexedLinkedList was on par
> > > with the JDK lists overall.
> > > - iterate-and-modify.png - Displays timings for iterating through the
> > > list while randomly adding and removing elements via the iterator.
> > > IndexedLinkedList did extraordinarily well here, with performance very
> > > close to LinkedList. Surprisingly, TreeList did worse than all of the
> > > others, including ArrayList.
> > >
> > > Overall, I think this list implementation would be a good option to
> > > include in commons-collections. Does anyone have any objections to
> > > opening a Jira ticket to pursue this?
> > >
> > > Regards,
> > > Matt J
> > >
> > > [1] https://github.com/coderodde/IndexedLinkedListBenchmark/pull/3
> > >
> > > > [...]
>
> -
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>

Re: [collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hello Matt and community,

I have created an ASF JIRA issue back in the days:
https://issues.apache.org/jira/projects/COLLECTIONS/issues/COLLECTIONS-797?filter=allopenissues

Best regards,
rodde

On Mon, Jul 11, 2022 at 6:23 AM Matt Juntunen 
wrote:

> Hello rodde,
>
> Thanks for your patience while I looked at this. I've made a PR [1] on
> your benchmark project with an updated benchmark class. (I used the
> completely uninspired class name of IndexedLinkedListPerformance2 :-)
> The results back up what you've been saying about the performance of
> this list implementation. I've attached a spreadsheet summarizing the
> data for a number of different operations along with some images of
> some of the most interesting comparisons. I've compared results for
> java.util.ArrayList, java.util.LinkedList,
> org.apache.commons.collections4.list.TreeList, and
> com.github.coderodde.util.IndexedLinkedList (the list in question
> here) using JDK 18 on list sizes of 10, 100, 1000, and 1.
>
> Below are some notes on the attached images.
> - get-random.png - Displays timings for element access at random
> indices. As expected, ArrayList is by far the best. TreeList and
> IndexedLinkedList are relatively close to each other but
> IndexedLinkedList is consistently faster. LinkedList was too terrible
> to even include on the graph.
> - iterate.png - Displays timings for list traversal using the list's
> iterator. This was unexpectedly bad for TreeList, which performed far
> worse than the others. The performance of IndexedLinkedList was on par
> with the JDK lists overall.
> - iterate-and-modify.png - Displays timings for iterating through the
> list while randomly adding and removing elements via the iterator.
> IndexedLinkedList did extraordinarily well here, with performance very
> close to LinkedList. Surprisingly, TreeList did worse than all of the
> others, including ArrayList.
>
> Overall, I think this list implementation would be a good option to
> include in commons-collections. Does anyone have any objections to
> opening a Jira ticket to pursue this?
>
> Regards,
> Matt J
>
> [1] https://github.com/coderodde/IndexedLinkedListBenchmark/pull/3
>
> On Sun, Jul 10, 2022 at 4:16 AM Bruno Kinoshita  wrote:
> >
> > Hi Rodde,
> >
> > It has been almost a week since your last response. Did you take a look
> at
> > > my work?
> > >
> >
> > Please note that we are all volunteers here, so sometimes we may be able
> to
> > respond quickly, others we may take a few days/weeks/months/...
> >
> > I know Matt is active in other Apache mailing lists, and that he works on
> > multiple Apache components. Besides also having $work, personal life,
> etc.,
> > of course. So please be patient :)
> >
> > Cheers
> > -Bruno
> >
> > On Sun, 10 Jul 2022 at 17:03, Rodion Efremov 
> wrote:
> >
> > > Hi Matt,
> > >
> > > It has been almost a week since your last response. Did you take a
> look at
> > > my work?
> > >
> > > Best regards,
> > > rodde
> > >
> > > ma 4.7.2022 klo 20.51 Matt Juntunen 
> kirjoitti:
> > >
> > > > Thanks, rodde! I should have some time this week to take a closer
> > > > look. I plan on playing with the benchmarks a bit on my own. I'll let
> > > > you know what I find.
> > > >
> > > > Regards,
> > > > Matt J
> > > >
> > > > On Mon, Jul 4, 2022 at 4:53 AM Rodion Efremov 
> > > wrote:
> > > > >
> > > > > Hi Matt and community,
> > > > >
> > > > > I have compiled the benchmark result data into 3 tables [1] (three
> > > > > different load sizes) [2]. If nothing else, IndexedLiinkedList
> (called
> > > > > RoddeList in output) is faster than both java.util.LinkedList and
> > > > TreeList.
> > > > >
> > > > > If, for further discussion, you require something else, please let
> me
> > > > know.
> > > > >
> > > > > Best regards,
> > > > > rodde
> > > > >
> > > > > [1]
> https://github.com/coderodde/indexedLinkedList/#benchmark-with-jmh
> > > > > [2]
> > > > >
> > > >
> > >
> https://github.com/coderodde/IndexedLinkedListBenchmark/blob/main/src/main/java/com/coderodde/IndexedLinkedListPerformance.java
> > > > >
> > > > > On Fri, Jul 1, 2022 at 6:11 AM Matt Juntunen <
> > > matt.a.juntu...@gmail.com>
> > > > > wrote:
> > > > &

Re: [collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hi Matt,

It has been almost a week since your last response. Did you take a look at
my work?

Best regards,
rodde

ma 4.7.2022 klo 20.51 Matt Juntunen  kirjoitti:

> Thanks, rodde! I should have some time this week to take a closer
> look. I plan on playing with the benchmarks a bit on my own. I'll let
> you know what I find.
>
> Regards,
> Matt J
>
> On Mon, Jul 4, 2022 at 4:53 AM Rodion Efremov  wrote:
> >
> > Hi Matt and community,
> >
> > I have compiled the benchmark result data into 3 tables [1] (three
> > different load sizes) [2]. If nothing else, IndexedLiinkedList (called
> > RoddeList in output) is faster than both java.util.LinkedList and
> TreeList.
> >
> > If, for further discussion, you require something else, please let me
> know.
> >
> > Best regards,
> > rodde
> >
> > [1] https://github.com/coderodde/indexedLinkedList/#benchmark-with-jmh
> > [2]
> >
> https://github.com/coderodde/IndexedLinkedListBenchmark/blob/main/src/main/java/com/coderodde/IndexedLinkedListPerformance.java
> >
> > On Fri, Jul 1, 2022 at 6:11 AM Matt Juntunen 
> > wrote:
> >
> > > Hello rodde,
> > >
> > > Thank you for sending me a reminder on this. Unfortunately, I haven't
> > > had time to look at the code yet. Gilles suggestions are something I
> > > would like to see as well. Having tables of JMH results for the
> > > different algorithms at different sizes would be very helpful.
> > >
> > > Regards,
> > > Matt J
> > >
> > > On Thu, Jun 30, 2022 at 11:34 AM Gilles Sadowski  >
> > > wrote:
> > > >
> > > > Hello.
> > > >
> > > > Le jeu. 30 juin 2022 à 07:54, Rodion Efremov  a
> > > écrit :
> > > > >
> > > > > Hi Matt and community,
> > > > >
> > > > > Have you take a look at my work? If so, what do you think?
> > > >
> > > > Perhaps you missed that feedback:
> > > >   https://markmail.org/message/y3tozjdke2ivz3dr
> > > >
> > > > >
> > > > > Best regards,
> > > > > rodde
> > > > >
> > > > > to 23.6.2022 klo 19.06 Matt Juntunen 
> > > kirjoitti:
> > > > >
> > > > > > Hello,
> > > > > >
> > > > > > Thanks for providing the data here. I will hopefully have time to
> > > take
> > > > > > a look at this over the weekend. Send me a ping here on the dev
> list
> > > > > > if you don't hear back from me (or someone else) within a week.
> > > > > >
> > > > > > Regards,
> > > > > > Matt J
> > > > > >
> > > > > > On Tue, Jun 21, 2022 at 7:22 AM Rodion Efremov <
> codero...@gmail.com>
> > > > > > wrote:
> > > > > > >
> > > > > > > Hi,
> > > > > > >
> > > > > > > Data structure: IndexedLinkedList
> > > > > > > <https://github.com/coderodde/IndexedLinkedList>
> > > > > > > Benchmark: IndexedLinkedListBenchmark
> > > > > > > <https://github.com/coderodde/IndexedLinkedListBenchmark>
> > > > > > >
> > > > > > > Benchmark output:
> > > > > > >
> https://github.com/coderodde/indexedLinkedList/#benchmark-output
> > > > > > >
> > > > > > > From the benchmark output, we can judge that IndexedLinkedList
> > > > > > outperforms
> > > > > > > both java.util.LinkedList and the Apache Commons Collections
> > > TreeList.
> > > > > > It,
> > > > > > > however, does not seem to supersede the java.util.ArrayList.
> > > > > > >
> > > > > > > Basically, I would expect the IndexedLinkedList to beat the
> > > ArrayList
> > > > > > where
> > > > > > > we have a lot of following operations:
> > > > > > >
> > > > > > >- addFirst(E)
> > > > > > >- add(int, E)
> > > > > > >- remove(int)
> > > > > > >
> > > > > > > So, what do you think? I am getting anywhere with that?
> > > > > > >
> > > > > > > Best regards,
> > > > > > > rodde
> > > >
> > > > -
> > > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > > > For additional commands, e-mail: dev-h...@commons.apache.org
> > > >
> > >
> > > -
> > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > > For additional commands, e-mail: dev-h...@commons.apache.org
> > >
> > >
>
> -
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>

Re: [collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hi Matt and community,

I have compiled the benchmark result data into 3 tables [1] (three
different load sizes) [2]. If nothing else, IndexedLiinkedList (called
RoddeList in output) is faster than both java.util.LinkedList and TreeList.

If, for further discussion, you require something else, please let me know.

Best regards,
rodde

[1] https://github.com/coderodde/indexedLinkedList/#benchmark-with-jmh
[2]
https://github.com/coderodde/IndexedLinkedListBenchmark/blob/main/src/main/java/com/coderodde/IndexedLinkedListPerformance.java

On Fri, Jul 1, 2022 at 6:11 AM Matt Juntunen 
wrote:

> Hello rodde,
>
> Thank you for sending me a reminder on this. Unfortunately, I haven't
> had time to look at the code yet. Gilles suggestions are something I
> would like to see as well. Having tables of JMH results for the
> different algorithms at different sizes would be very helpful.
>
> Regards,
> Matt J
>
> On Thu, Jun 30, 2022 at 11:34 AM Gilles Sadowski 
> wrote:
> >
> > Hello.
> >
> > Le jeu. 30 juin 2022 à 07:54, Rodion Efremov  a
> écrit :
> > >
> > > Hi Matt and community,
> > >
> > > Have you take a look at my work? If so, what do you think?
> >
> > Perhaps you missed that feedback:
> >   https://markmail.org/message/y3tozjdke2ivz3dr
> >
> > >
> > > Best regards,
> > > rodde
> > >
> > > to 23.6.2022 klo 19.06 Matt Juntunen 
> kirjoitti:
> > >
> > > > Hello,
> > > >
> > > > Thanks for providing the data here. I will hopefully have time to
> take
> > > > a look at this over the weekend. Send me a ping here on the dev list
> > > > if you don't hear back from me (or someone else) within a week.
> > > >
> > > > Regards,
> > > > Matt J
> > > >
> > > > On Tue, Jun 21, 2022 at 7:22 AM Rodion Efremov 
> > > > wrote:
> > > > >
> > > > > Hi,
> > > > >
> > > > > Data structure: IndexedLinkedList
> > > > > <https://github.com/coderodde/IndexedLinkedList>
> > > > > Benchmark: IndexedLinkedListBenchmark
> > > > > <https://github.com/coderodde/IndexedLinkedListBenchmark>
> > > > >
> > > > > Benchmark output:
> > > > > https://github.com/coderodde/indexedLinkedList/#benchmark-output
> > > > >
> > > > > From the benchmark output, we can judge that IndexedLinkedList
> > > > outperforms
> > > > > both java.util.LinkedList and the Apache Commons Collections
> TreeList.
> > > > It,
> > > > > however, does not seem to supersede the java.util.ArrayList.
> > > > >
> > > > > Basically, I would expect the IndexedLinkedList to beat the
> ArrayList
> > > > where
> > > > > we have a lot of following operations:
> > > > >
> > > > >- addFirst(E)
> > > > >- add(int, E)
> > > > >- remove(int)
> > > > >
> > > > > So, what do you think? I am getting anywhere with that?
> > > > >
> > > > > Best regards,
> > > > > rodde
> >
> > -
> > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > For additional commands, e-mail: dev-h...@commons.apache.org
> >
>
> -
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>

Re: [collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hi Matt and community,

Have you take a look at my work? If so, what do you think?

Best regards,
rodde

to 23.6.2022 klo 19.06 Matt Juntunen  kirjoitti:

> Hello,
>
> Thanks for providing the data here. I will hopefully have time to take
> a look at this over the weekend. Send me a ping here on the dev list
> if you don't hear back from me (or someone else) within a week.
>
> Regards,
> Matt J
>
> On Tue, Jun 21, 2022 at 7:22 AM Rodion Efremov 
> wrote:
> >
> > Hi,
> >
> > Data structure: IndexedLinkedList
> > <https://github.com/coderodde/IndexedLinkedList>
> > Benchmark: IndexedLinkedListBenchmark
> > <https://github.com/coderodde/IndexedLinkedListBenchmark>
> >
> > Benchmark output:
> > https://github.com/coderodde/indexedLinkedList/#benchmark-output
> >
> > From the benchmark output, we can judge that IndexedLinkedList
> outperforms
> > both java.util.LinkedList and the Apache Commons Collections TreeList.
> It,
> > however, does not seem to supersede the java.util.ArrayList.
> >
> > Basically, I would expect the IndexedLinkedList to beat the ArrayList
> where
> > we have a lot of following operations:
> >
> >- addFirst(E)
> >- add(int, E)
> >- remove(int)
> >
> > So, what do you think? I am getting anywhere with that?
> >
> > Best regards,
> > rodde
>
> -
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>

[collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hi,

Data structure: IndexedLinkedList

Benchmark: IndexedLinkedListBenchmark


Benchmark output:
https://github.com/coderodde/indexedLinkedList/#benchmark-output

>From the benchmark output, we can judge that IndexedLinkedList outperforms
both java.util.LinkedList and the Apache Commons Collections TreeList. It,
however, does not seem to supersede the java.util.ArrayList.

Basically, I would expect the IndexedLinkedList to beat the ArrayList where
we have a lot of following operations:

   - addFirst(E)
   - add(int, E)
   - remove(int)

So, what do you think? I am getting anywhere with that?

Best regards,
rodde

Re: [collections] Add a list/deque faster than TreeList?

[Rodion Efremov]

Hi Matt and community,

About thread safety: I keep an int counting modifications (called
modCount). Now, spliterator/iterator/sublist check that modCount ==
expectedModCount, and if that is not the case, throws
ConcurrentModificationException. Basically, it resembles the fail-fast
behavior of ArrayList/LinkedList. In order to deal with concurrency, one
should wrap an instance of IndexedLinkedList into
Collections.synchronizedList(...).

About Guava: they happily turned down my offer.

Best regards,
rodde

la 11.6.2022 klo 19.44 Matt Sicker  kirjoitti:

> Looks pretty interesting. I’ll be honest that my own data structure
> expertise revolves around immutable persistent patterns rather than mutable
> ones, but your class makes perfect sense as a mutable one.
>
> Do you have any notes on thread safety?
>
> While it’s neat that you’re submitting to the JDK as well, that sort of
> process is fairly long term, so I’d imagine that Collections would be a
> great place for it. If you’re trying to donate this to multiple projects,
> then Eclipse also has a collections library that might like it, and Guava
> might like it, too.
>
> —
> Matt Sicker
>
> > On Jun 10, 2022, at 14:30, Rodion Efremov  wrote:
> >
> > Hi,
> >
> > I have this List/Deque data structure:
> >
> > https://github.com/coderodde/IndexedLinkedList
> >
> > In a versatile benchmark, it outperforms the O(log n) TreeList easily by
> > the factor of 2. (Also, it requires less memory than TreeList.)
> >
> > What do you think? Does it deserve to be included in collections?
> >
> > Best regards,
> > rodde
>

[collections] Add a list/deque faster than TreeList?

[Rodion Efremov]

Hi,

I have this List/Deque data structure:

https://github.com/coderodde/IndexedLinkedList

In a versatile benchmark, it outperforms the O(log n) TreeList easily by
the factor of 2. (Also, it requires less memory than TreeList.)

What do you think? Does it deserve to be included in collections?

Best regards,
rodde

[collections] Faster, indexed doubly-linked list data structure

[Rodion Efremov]

Hello,

I have implemented a heuristic, indexed doubly-linked list data structure
[1][2] implementing java.util.List and java.util.Deque interfaces that has
superior performance compared to java.util.LinkedList and
java.util.ArrayList, and comparable performance to TreeList while having
smaller (around 10 bytes per item) memory footprint.

I would like to propose it into Collections4, but, first, I need to know
what do you think about it?

Best regards,
rodde

[1] https://github.com/coderodde/LinkedList
[2] http://coderodde.github.io/weblog/#eill

[collections] An order statistic tree

[Rodion Efremov]

Hello, all.
I would like to announce that I have a java.util.Set implementation that is an 
order statistic tree (all non-bulk operations + select + rank in O(log n) time) 
[1]. However, it seems like the team on behalf of the order statistic tree 
issue is rather idle [2], hence the message.
Best,
rodde
[1] https://github.com/coderodde/OrderStatisticTree
[2] https://issues.apache.org/jira/browse/COLLECTIONS-479

[collections] An order statistic tree (COLLECTIONS-479)

[Rodion Efremov]

I have revived some discussion at 
https://issues.apache.org/jira/browse/COLLECTIONS-479 
(https://issues.apache.org/jira/browse/COLLECTIONS-479)
Basically, what interfaces an order statistic tree should implement? What comes 
to the structure, will a counted AVL-tree do?
Best,
rodde

[COLLECTIONS] Introducing OrderStatisticTree

[Rodion Efremov]

Hello, y'all and Merry Xmas!

I am mailing you as to notify about a new patch patching the 
order-statistic tree in Commons Collections, which is contained in 
COLLECTIONS-479.patch. May I expect it to be reviewed any time soon?


--
TIA, Rodion



-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

[Collections] A better TreeList?

[Rodion Efremov]

Hello, y'all!

My buggy experiments show that it makes sense to produce a 
TreeList-like structure, that doesn't use an entire AVLNode for storing 
each god damned element, but rather stores, say, 128 elements in a node. 
In such a way, you can talk about a structure that takes the best from 
Array-/Linked-/Tree-list.


Your opinion?

--
TIA, Rodion



-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

[graph] Breadth-Fist Search library to commons graph?

[Rodion Efremov]

Hello, might it be funky to have a few esoteric BFS-algorithms from 
[1]? :^)


--
TIA, Rodion

[1] https://github.com/coderodde/bfsbuddy

-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

[graph] is now ****** up :(

[Rodion Efremov]

Hello, y'all!

I did a checkout of commons graph, and guess what? There is no crucial 
BaseLabeledVertex.java in the entire repo.
Did anyone of you tampered with the [graph] recently, because i would 
be infinitely happy, if some of you committers would fix the issue. I 
want to contribute more to [graph], but currently i am at *your* mercy, 
guys.


--
TIA, Rodion



-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

[COLLECTIONS] Preparing to solve issue 479 (Order statistic tree).

[Rodion Efremov]

I have partially implemented ordered statistic tree [1], which I would 
like to contribute (right after I refactor it). If I submit a patch, how 
long does it take to get some attention from the committers?


--
TIA, Rodion

[1] Counted AVLTree at http://mureakuha.com/koodikirjasto/1253

-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

[MATH] Missing Gauss-Jordan -elimination algorithm?

[Rodion Efremov]

Hello, all!

I have a couple of matrices, to which I would like to apply the 
Gauss-Jordan -elimination (i.e., I need the reduced row-echelon form of 
aforementioned), yet I cannot find from 3.2 anything relevant.


A couple of noob questions follow..

(1) Is there already implemented algorithms doing the task efficiently?
(2) If answer to (1) is negative, would it be nice to have one in the 
trunk?


--
TIA, Rodion



-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

Re: [DISCUSS] Math TLP...

[Rodion Efremov]

Don't you can conclude that matter, shut the f*** up, and enjoy the 
last days of summer? ;)


---
TIA, Rodion

James Carman писал 29.08.2013 05:46 PM:
To be clear, I don't really care one way or the other.  I just 
thought

it was probably good to have a formal discussion on the matter.  I'm
also a math geek, so I like reading the emails sometimes (sometimes
they're way over my head too).  It takes me back to my college days.
:)  I would probably subscribe to the mailing list even if it went
TLP.  I also like the fact that we are able to help with API design.
It sounds like most folks either don't mind if CM stays or don't want
it to stay.  More folks are free to contribute to the discussion, of
course, but at this point, it looks like we have somewhat of a
consensus.

On Thu, Aug 29, 2013 at 4:37 AM, Gilles 
gil...@harfang.homelinux.org wrote:

Hello.




James, it's good that you bring this up here. This is something 
I've been

thinking about lately.

I agree that the mathematical knowledge that seems to be necessary 
to dig
into [MATH] goes beyond what you learn in Computer Science courses 
at
university. I usually skip discussions about math but they don't 
bother me

or anything (like Luc has feared).

Several people have expressed that there have been valuable 
contributions
on design related decisions from people without a mathematical 
background.
I'm always open for some design related chatter but I find it hard 
to
filter those messages. Maybe an additional tag would help here? 
Something
to tell me, that the discussion is not related to mathematical 
theory like

[MATH][DESIGN] or [MATH][API] or something like that?



It's rarely clear-cut. Most often, API changes or new DESIGNs are
derived from
1. how one sees the mathematical field to be modelled
2. how extensive this model is going to be
3. how much of the domain is already modelled
4. how strongly we want to maintain compatibility




To cut a long story short: If [MATH] wants to stay here, let it 
stay here.

:-)



Thanks for the hospitality,[1]
Gilles

[1] Although, as I pointed out several times, we should always
take into account that CM is on several counts fairly
different from all the other Commons projects.
The most important aspect here is the code maturity level.




-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org



-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org



-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

Re: [MATH] What is the derivative of 0^x

[Rodion Efremov]

Hi!

IMHO, 0^x should equal 0. But note please, that 0^0 is not define, so 
it should be NaN


---
TIA, Rodion

Ajo Fod писал 23.08.2013 05:17 PM:

Seems like the DerivativeCompiler returns NaN.

IMHO it should return 0.

Is this worthy of an issue?

Thanks,
-Ajo



-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

Re: [Graph] the future of commons-graph and modularization

[Rodion Efremov]

Simone Tripodi kirjoitti 26.05.2013 18:35:

Hi all, mates,

after a long while I haven't touched commons-graph, I had the
opportunity to get influenced by some activities at my paid work that
made me think twice on what as been already done in that component,
and would like to bring new experiences in.

So, what I still like about it:

 * graph APIs: the use of generics make the usage of graphes
extensible and adaptable;

 * fluent APIs: this is the most powerful feature IMHO that 
simplifies

the APIs usage;

What I *don't* like anymore:

 * poor modularization: commons-graph is ATM a big fat monolith;

 * one single entry-point; for each new family of algorithm(s), new
methods have to be added in the main Commons-Graph class.

What I would like to propose to work _in a separated branch_, is
trying to split the big monolith in smaller modules and separate APIs
from related implementation as much as possible.

Questions are:

 * WDYT? :)


Might the API look like this?

public interface PathFinderV, E, W {
public PathV, E search();
public PathFinderV, E, W from( V source );
public PathFinderV, E, W to( V target );
public PathFinderV, E, W withHeuristic( HeuristicFunctionV, W f 
); // for A* search.

}

... and then we would have, say, A* as follows:

public class AStarFinderV, E, W implements PathFinderV, E, W {
public PathV, E search() {
// A* magic here.
}

... implement the rest.
}

... with usage as follows:

PathV, E path = new AStarFinderV, E, W().withHeuristic( 
myFunkyHeuristic ).from( source ).to( target ).search();


This would seem like eliminating the need for CommonsGraph -monolith at 
the cost of introducing new interfaces/abstract base classes for every 
type of algos out there, plus the actual implementation classes 
implementing the API.



 * About release process: would it be acceptable, here in commons,
release a single module - the only one that has been changed, I mean 
-

without releasing the whole project?

 * In case the answer to previous question is no, would it make
sense moving commons-graph to the Incubator (and possibly to TLP)?

TIA, all the best!
-Simo

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/

-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org



-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

[Graph] On activity of Sandbox Graph

[Rodion Efremov]

Hello all.

Have attached the patch containing bidirectional Dijkstra SSSP algo + 
tests at org.apache.commons.graph.shortestpath (issue SANDBOX-457) in 
hope someone will review it. The benchmark is telling:

  applyingDijkstra():  time.warmup: 0.30, time.bench: 1.09
  applyingBidirectionalDijkstra(): time.warmup: 0.01, time.bench: 0.04
both on the same connected graph and identical sequences of source, 
target -pairs.


Couple of questions:
(a) What is the average duration between sending a patch P and getting 
it reviewed by a committer, assuming P will draw some attention 
eventually?
(b) Is it possible that a patch to a Sandbox component will be ignored 
for a very looong time in favor of more important issues going on in 
*Commons Proper*?


-rodde

-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org