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

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

Re: stream concat distinct indeterministic

Show all headers | View raw

On 2/15/2016 4:58 PM, Martin Gregorie wrote:
> On Mon, 15 Feb 2016 16:13:14 -0500, Eric Sosman wrote:
>
>>       Let's review for a moment.  From bits and pieces of several posts,
>> it seems you began with
>>
>> 	Stream.concat(str1, str2).distinct().count();
>>
>> ... and reported that the same str1/2 produced different counts in
>> different runs.  Now you've changed to
>>
>> 	Stream.concat(str1, str2).sorted().distinct().count();
>>
>> ... which shouldn't ("shouldn't") change anything, yet you now report
>> that everything appears to be working.
>>
> This doesn't surprise me because the Stream.distinct() method is only
> guaranteed to produce a stable result from an ordered input stream, which
> implies that the distinctness comparison is made between adjacent
> elements in the stream.

     I doubt the implication.

     Are you confusing "ordered" with "sorted?"  An ordered stream
(saith the java.util.stream package Javadoc) is one for which there
is a defined "encounter order."  Examples are given: Streams created
from Lists are ordered, Streams created from HashSets are not.  It
doesn't matter whether the Stream's elements are sorted (according
to some Comparator or other), just that they appear in a fixed order.

     Also, the Javadoc for Stream::distinct defines what is meant
by "stable:"

	For ordered streams, the selection of distinct elements is
	stable (for duplicated elements, the element appearing first
	in the encounter order is preserved.) For unordered streams,
	no stability guarantees are made.

That is, if a Stream produces several distinct elements that are
equals() of each other -- let us call them X1,X2,...,Xn -- then using
distinct() on an ordered stream will always select X1, the first that
appears; that's what "stable" means here.  For an unordered stream
there is no notion of "first appears" and distinct() may select any
single Xi, and need not select the same one in each of several trials.

     Either way, though, distinct() is documented to select *one* from
each batch of equals() elements -- and since Philipp is simply counting
how many there are, it should not matter which representative is chosen
from each group.  Stability should ("should") make no difference at all.

> elements in the stream. So, I think there are two possible sources of
> instability:
>
> 1) Philipp hasn't said whether any of the streams being concatenated
>     are ordered,
>
> 2) Even if the original streams are all ordered, simply concatenating
>     two or more streams will create a single unordered stream because
>     concat() merely appends the content of Stream b to the content of
>     Stream a

     The Javadoc for Stream::concat says (emphasis mine)

	[...] all the elements of the first stream *followed by* all
	the elements of the second stream [...]

and goes on to say

	The resulting stream is ordered if both of the input streams
	are ordered [...]

> So, applying the sorted() to the output of concat() restores stability to
> distinct()'s operation no matter what the key sequence is in the original
> streams, which is why it solved Philipp's problem.
>
> The only case calling sorted() adds no value is when the input streams
> are already ordered and each successive stream to be concatenated
> contains a key range whose lowest value is greater than or equal to the
> highest key value in the preceding stream.

     My summary:

     1) I think you're mistaken about what "ordered" means,

     2) ... which may have led you to misunderstand this use of "stable,"

     3) ... but even in an unstable situation, distinct().count() should
        yield the same result for the same inputs,

     4) ... which leads me to suspect something else is wrong,

     5) ... but Philipp won't show us any of the "else" (possibly for
        valid but non-technical reasons), so

     6) ... a mystery remains.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

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

Thread

stream concat distinct indeterministic Philipp Kraus <philipp.kraus.flashpixx@gmail.com> - 2016-02-15 08:08 -0800
  Re: stream concat distinct indeterministic Arne Vajhøj <arne@vajhoej.dk> - 2016-02-15 11:30 -0500
    Re: stream concat distinct indeterministic Philipp Kraus <philipp.kraus.flashpixx@gmail.com> - 2016-02-15 12:54 -0800
      Re: stream concat distinct indeterministic Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-02-15 16:13 -0500
        Re: stream concat distinct indeterministic Martin Gregorie <martin@address-in-sig.invalid> - 2016-02-15 21:58 +0000
          Re: stream concat distinct indeterministic Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-02-15 17:45 -0500
            Re: stream concat distinct indeterministic Martin Gregorie <martin@address-in-sig.invalid> - 2016-02-15 23:29 +0000
              Re: stream concat distinct indeterministic Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-02-16 07:47 -0500
        Re: stream concat distinct indeterministic Arne Vajhøj <arne@vajhoej.dk> - 2016-02-15 21:45 -0500
  Re: stream concat distinct indeterministic Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-02-15 11:38 -0500
    Re: stream concat distinct indeterministic Philipp Kraus <philipp.kraus.flashpixx@gmail.com> - 2016-02-15 09:05 -0800
      Re: stream concat distinct indeterministic Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-02-15 14:08 -0500
      Re: stream concat distinct indeterministic Andreas Leitgeb <avl@logic.at> - 2016-02-16 18:40 +0000

csiph-web