Substream applied to unordered streams
brian.goetz at oracle.com
Sat Mar 16 13:52:22 PDT 2013
I haven't yet determined whether we want to commit to stable sorting.
But I think we probably do not. Stability is a relatively cheap
property to preserve in a sequential sort (which is why Arrays.sort is
spec'ed as stable), but a relatively expensive property to preserve in
an parallel sort, and this moves the balance of whether stability is
worth the cost.
So I would say the answer is likely to be: "stream sorts are not
guaranteed stable at all", though you might get stability by accident
with some sequential streams.
On 3/16/2013 4:43 PM, Georgiy Rakov wrote:
> On 15.03.2013 22:45, Brian Goetz wrote:
>>> it seems that 'limit' and 'substream' methods applied to unordered
>>> stream return result which seems to be only partially deterministic.
>> Right, which makes sense. substream (and by extension limit) are
>> defined in terms of encounter order; if the encounter order is merely
>> accidental, as it is in an unordered stream, there's not much we can
>> do there.
>>> Similar thing is true for 'sorted' method provided stream contains equal
>>> elements and 'sorted' uses algorithm preserving order.
>> I think you're asking whether sorting is stable (for ordered streams)
>> or not?
> Pardon me, yes I meant "stable sorting",
> I meant that 'sorted' result becomes a bit more nondetermenistic for
> unordered streams provided they contain equal elements and 'sorted' uses
> stable sorting; actually stable sorting turns into unstable sorting (of
> course if sorting was stable originally).
> In general I asked whether you see useful to show these points in spec,
> e. g. if spec contains something like:
> You should keep in mind that substream() could return stream which
> content is nondeterministic provided original stream encounter order
> is not defined, e.g. for stream returned from HashSet instance.
> and for "sorted":
> You should keep in mind that sorting becomes actually unstable when
> applied to unordered stream.
> The later only makes sense if "sorted()" uses stable sort, if it uses
> non stable sorting nothing changes for unordered streams.
> And the question you mentioned above is relevant as well - I would
> appreciate greatly if you tell whether "sorted()" uses stable sorting.
> Thank you,
More information about the lambda-dev