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

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

Re: stream concat distinct indeterministic

Show all headers | View raw

On Mon, 15 Feb 2016 17:45:50 -0500, Eric Sosman wrote:

> 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
>
Yeah IIRC this means by comparing natural keys.

It also says something about 'ordered' depending on the natural keys 
which, to me anyway means that an ordered stream is in natural key 
sequence.

However I don't think Philipp has said precisely what he means by 
'indeterministic' except that that count() returns different values, but 
not how (or if) he changes the input streams, inputs them in a different 
order or what, and how this relates to the  
different item counts.

I merely observe that, if distinct() scans the whole stream for matching 
natural keys, concat() does what it says on the tin, then count()'s 
result should should be invariant AND distinct()'s performance should not 
be linearly dependent on the number of items in the stream output from 
concat().

However, if distinct() does a single pass along the stream comparing 
adjacent items, then count()'s output will be affected by the item 
ordering and distinct()'s performance will be linearly dependent on the 
number of items in the stream.

 -- 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.
>
No argument with this.
 
>      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.
>
However, if the stream isn't sorted you can get several batches of equals
() items any the count will be affected by the number of batches in the 
stream.
  
>      The Javadoc for Stream::concat says (emphasis mine)
> 
> 	[...] all the elements of the first stream *followed by* all the
> 	elements of the second stream [...]
>
Agreed.
 
> and goes on to say
> 
> 	The resulting stream is ordered if both of the input streams are
> 	ordered [...]
>
Yes, also true, BUT concatenating two ordered streams is likely to 
produce an unordered stream, e.g.

'a,b,c,a,c,e' = concat('a,b,c', 'a,c,e') 

and applying distinct() will give 'a,b,c,a,c,e' and count() == 6 while 
 
'a,a,b,c,c,e' = concat('a,b,c', 'a,c,e').sorted()

and this time applying distinct() will give 'a,b,c,e' and count() == 4 

At least, that's how I read it and if that's what is happening it does 
explain Philipp's results.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

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