<div><br></div><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">ti 14.6.2022 klo 18.49 Rodion Efremov <<a href="mailto:coderodd3@gmail.com">coderodd3@gmail.com</a>> kirjoitti:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;padding-left:1ex;border-left-color:rgb(204,204,204)"><div dir="auto">Hi community,</div><div dir="auto"><br></div><div dir="auto">> <span style="color:rgb(0,0,0)">One use case I've had in the past was for a list that is</span><span style="color:rgb(0,0,0)"> </span></div><span style="border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(204,204,204);color:rgb(0,0,0)">always sorted but also allows index based access when displaying a </span><br style="font-family:-apple-system,HelveticaNeue"><span style="border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(204,204,204);color:rgb(0,0,0)">window into the list.</span><div dir="auto"><font style="border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(204,204,204);color:rgb(0,0,0)"><br></font></div><div dir="auto"><font style="border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(204,204,204);color:rgb(0,0,0)">I suppose you are talking about an order statistic tree. If that is the case, I have one [1].</font></div><div dir="auto"><font style="border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(204,204,204);color:rgb(0,0,0)"><br></font></div><div dir="auto"><font style="border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(204,204,204);color:rgb(0,0,0)">Best regards,</font></div><div dir="auto"><font style="border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(204,204,204);color:rgb(0,0,0)">rodde</font></div><div dir="auto"><font style="border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(204,204,204);color:rgb(0,0,0)"><br></font></div><div dir="auto"><font style="border-color:rgb(0,0,0) rgb(0,0,0) rgb(0,0,0) rgb(204,204,204);color:rgb(0,0,0)">[1] https<span>://<a href="http://github.com/coderodde/OrderStatisticTree" target="_blank">github.com/coderodde/OrderStatisticTree</a></span><br><br></font></div><div dir="auto"><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">ma 13.6.2022 klo 15.00 John Hendrikx <<a href="mailto:john.hendrikx@gmail.com" target="_blank">john.hendrikx@gmail.com</a>> kirjoitti:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;padding-left:1ex;border-left-color:rgb(204,204,204)">I took a look.<br>
<br>
I found a few results odd:<br>
<br>
|com.github.coderodde.util.IndexedLinkedList.addLast in (ms): 8 <br>
java.util.LinkedList.addLast in (ms): 2 java.util.ArrayList.addLast in <br>
(ms): 157 org.apache.commons.collections4.list.TreeList.addLast in (ms): 38|<br>
<br>
Basically, ArrayList's performance (which should be O(1) in this case) <br>
is surprising. Looking at the benchmark, it is calling <br>
ArrayList#add(int, E) -- this method is not special cased for adding at <br>
the end of the list (it will do a range check and call System#arrayCopy <br>
in all cases).<br>
<br>
|com.github.coderodde.util.IndexedLinkedList.stream() in (ms): 1 <br>
java.util.LinkedList.stream() in (ms): 20 java.util.ArrayList.stream() <br>
in (ms): 16 org.apache.commons.collections4.list.TreeList.stream() in <br>
(ms): 15|<br>
<br>
This test isn't only measuring streaming (iteration?) but also <br>
re-inserting all elements back into a List <br>
(collect(Collectors.toList()). What I find odd is that the <br>
IndexedLinkedList would perform much better here than ArrayList, given <br>
that the time is probably dominated by the final collect, and not the <br>
iteration itself.  Is ArrayList#stream poorly optimized or is something <br>
else going on?<br>
<br>
A pure iteration test would be interesting to see.<br>
<br>
I also ran the benchmark on my machine. The benchmark on Github doesn't <br>
mention with what parameters it is run, and so when I run it I get quite <br>
different results. The committed version of the benchmark seems to use <br>
collections with a max size of 20 elements. The total time when I run <br>
the benchmark favors TreeList more than any other:<br>
<br>
--- Total time elapsed ---<br>
com.github.coderodde.util.IndexedLinkedList in (ms): 207<br>
java.util.LinkedList in (ms): 4248<br>
java.util.ArrayList in (ms): 1799<br>
org.apache.commons.collections4.list.TreeList in (ms): 159<br>
<br>
That said, I think there might be a place for a new list implementation <br>
in the JDK.  One use case I've had in the past was for a list that is <br>
always sorted but also allows index based access when displaying a <br>
window into the list. A TreeMap satisfies the sorting criteria but <br>
doesn't offer index access, while a plain ArrayList doesn't lend itself <br>
well for doing sorted inserts/removals (locating the correct location is <br>
trivial enough, but the actual insert or removal results in a <br>
potentially large copy).  Apache's TreeList is fairly good at this use case.<br>
<br>
--John<br>
<br>
<br>
On 13/06/2022 09:56, Rodion Efremov wrote:<br>
> Hello,<br>
><br>
> I have this List/Deque implementation [1] that (in a versatile benchmark)<br>
> runs much faster than ArrayList/LinkedList. Under mild assumptions, it<br>
> accesses an element in O(sqrt(N)) time.<br>
><br>
> Now, if all we want to do is to add at the tail and read via get(int<br>
> index), you are better of using java.util.ArrayList. If you wish to iterate<br>
> a list removing some elements, the way to go is to use java.util.LinkedList.<br>
><br>
>   However,, if you deal with larger lists via many different operations<br>
> (addFirst/addLast/add(int, E)/get(int)/remove(int)/ettc. my<br>
> IndexedLinkedLiist will outperform both of them gracefully.<br>
><br>
> So, what do you think? Does it deserve to become a class candidate for<br>
> java.util?<br>
><br>
> [1]<a href="https://github.com/coderodde/IndexedLinkedList" rel="noreferrer" target="_blank">https://github.com/coderodde/IndexedLinkedList</a><br>
</blockquote></div></div></div>
</blockquote></div></div>