Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #37901

Re: 1.8 java.util.LinkedList.spliterator()

Show all headers | View raw

On 2017-12-20 00:00, Volker Borchert wrote:
> Took a look at it to see how one might write a Spliterator
> for a linked data structure; in particular, how to handle
> size estimation.
> 
> I am aware that structures like LinkedList and LinkedHashMap
> are not really suitable for spliterating unless the action is
> expensive enough to justify the time and space overhead of
> trySplit(), but I'm still wondering.
> 
> Outline of test code:
> - create a LinkedList<Long> containing Long.valueOf(0..16383)
> - get a spliterator
> - call trySplit() until it returns null, put the split-offs
>   into a list
> - add the spliterator itself to the list
> - exhaust each spliterator in the list using an action that
>   counts how often it is called
> - stare in disbelief at the result:
>   1024,2048,3072,4096,5120,1024,0
> 
> The reason for copying the part to split off into an array
> is probably that further splits become trivial. That would
> also explain why it splits off the last chunk instead of
> returning null from trySplit() and handling it itself.
> 
> But: Why does the size of said array increase each time,
> and why linearly rather than e.g. doubling? Why doesn't it
> split in halves?

Are you asking us to speculate why Oracle implemented their
LinkedList#spliterator() in that way?

If so, I'd have to guess... which I'll gladly do: probably because they
determined empirically that taking that monotic ad-hoc approach yielded
better performance than leaning on the O(log(n)) of LinkedList#size().
Which seems rather plausible, I must say.

-- 
DF.

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

1.8 java.util.LinkedList.spliterator() v_borchert@despammed.com (Volker Borchert) - 2017-12-19 23:00 +0000
  Re: 1.8 java.util.LinkedList.spliterator() Daniele Futtorovic <da.futt.news@laposte.net> - 2017-12-21 14:14 +0100

csiph-web