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

Groups > comp.lang.java.programmer > #37893 > unrolled thread

1.8 java.util.LinkedList.spliterator()

Back to article view | Back to comp.lang.java.programmer

Contents

  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

#37893 — 1.8 java.util.LinkedList.spliterator()

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?


-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

[toc] | [next] | [standalone]

#37901

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web