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