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

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

stream concat distinct indeterministic

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

Contents

  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

#33815 — stream concat distinct indeterministic

Hello,

I run Stream.concat to concat two streams. These two streams are "stream" and use a flatMap call.
After the concat I run distinct() to create an unique stream of elements, but I get an indeterministic behaviour of my concated stream, so my question is how can I create a concated and distinct stream?

Thanks

Phil

[toc] | [next] | [standalone]

#33819

On 2/15/2016 11:08 AM, Philipp Kraus wrote:
> I run Stream.concat to concat two streams. These two streams are
> "stream" and use a flatMap call. After the concat I run distinct() to
> create an unique stream of elements, but I get an indeterministic
> behaviour of my concated stream, so my question is how can I create a
> concated and distinct stream?

Docs for distinct says:

"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."

so I would guess that you would need to do .sorted().distinct() instead
of just .distinct().

Arne

[toc] | [prev] | [next] | [standalone]

#33829

Am Montag, 15. Februar 2016 17:30:23 UTC+1 schrieb Arne Vajhøj:
> On 2/15/2016 11:08 AM, Philipp Kraus wrote:
> > I run Stream.concat to concat two streams. These two streams are
> > "stream" and use a flatMap call. After the concat I run distinct() to
> > create an unique stream of elements, but I get an indeterministic
> > behaviour of my concated stream, so my question is how can I create a
> > concated and distinct stream?
> 
> Docs for distinct says:
> 
> "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."
> 
> so I would guess that you would need to do .sorted().distinct() instead
> of just .distinct().

Thanks, this seems to be working, I have added a compareTo (overload) and run sorted() before distinct().

Thanks Phil

[toc] | [prev] | [next] | [standalone]

#33830

On 2/15/2016 3:54 PM, Philipp Kraus wrote:
> Am Montag, 15. Februar 2016 17:30:23 UTC+1 schrieb Arne Vajhøj:
>> On 2/15/2016 11:08 AM, Philipp Kraus wrote:
>>> I run Stream.concat to concat two streams. These two streams are
>>> "stream" and use a flatMap call. After the concat I run distinct() to
>>> create an unique stream of elements, but I get an indeterministic
>>> behaviour of my concated stream, so my question is how can I create a
>>> concated and distinct stream?
>>
>> Docs for distinct says:
>>
>> "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."
>>
>> so I would guess that you would need to do .sorted().distinct() instead
>> of just .distinct().
>
> Thanks, this seems to be working, I have added a compareTo (overload) and run sorted() before distinct().

     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.

     Except, of course, that there's no obvious reason why the original
pipeline would misbehave, and no obvious reason why sorted() should make
any difference (there are exactly as many elements in ACDB as in ABCD).
So I *strongly* encourage you not to let the matter rest, but to look
deeper and see what's really going on.

     You may have uncovered a serious bug in the streams framework --
or you may have made a slip-up elsewhere.  The former is possible, but
to me the latter seems far more likely.

     For the last time: SSCCE?  <http://www.sscce.org/>

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

[toc] | [prev] | [next] | [standalone]

#33831

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. 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

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.
 

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

[toc] | [prev] | [next] | [standalone]

#33832

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

[toc] | [prev] | [next] | [standalone]

#33833

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       |

[toc] | [prev] | [next] | [standalone]

#33840

On 2/15/2016 6:29 PM, Martin Gregorie wrote:
> 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.

     Perhaps you've mixed up equals() and compareTo().

> 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.

     What is the "it" that says ordered streams deal with keys of any
kind, natural or unnatural?

> [...]
> 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.

     This would be a bug in distinct().  It would also make meaningless
hash out of much of the Javadoc's text describing distinct().  In
particular, the Javadoc recommends against using it on ordered parallel
streams, saying that an UNordered parallel stream will perform better.
If your interpretation is correct, this text in the Javadoc is without
meaning -- and although the Javadoc certainly has its share of bloopers,
it seems far more likely to me that you are misinterpreting.

>> [...]
> 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

     You're still confusing "ordered" with "sorted."  An ordered stream
need not be sorted; its elements need not even implement Comparable nor
be handed to a Comparator.  (An unordered stream, obviously, cannot be
sorted.)

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

[toc] | [prev] | [next] | [standalone]

#33835

On 2/15/2016 4:13 PM, Eric Sosman wrote:
> On 2/15/2016 3:54 PM, Philipp Kraus wrote:
>> Am Montag, 15. Februar 2016 17:30:23 UTC+1 schrieb Arne Vajhøj:
>>> On 2/15/2016 11:08 AM, Philipp Kraus wrote:
>>>> I run Stream.concat to concat two streams. These two streams are
>>>> "stream" and use a flatMap call. After the concat I run distinct() to
>>>> create an unique stream of elements, but I get an indeterministic
>>>> behaviour of my concated stream, so my question is how can I create a
>>>> concated and distinct stream?
>>>
>>> Docs for distinct says:
>>>
>>> "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."
>>>
>>> so I would guess that you would need to do .sorted().distinct() instead
>>> of just .distinct().
>>
>> Thanks, this seems to be working, I have added a compareTo (overload)
>> and run sorted() before distinct().
>
>      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.
>
>      Except, of course, that there's no obvious reason why the original
> pipeline would misbehave, and no obvious reason why sorted() should make
> any difference (there are exactly as many elements in ACDB as in ABCD).
> So I *strongly* encourage you not to let the matter rest, but to look
> deeper and see what's really going on.
>
>      You may have uncovered a serious bug in the streams framework --
> or you may have made a slip-up elsewhere.  The former is possible, but
> to me the latter seems far more likely.

The post I replied to did not talk about different count but about
"indeterministic behaviour".

.sorted() should not impact .count() at all, but I thought it may
help on .distinct() and "indeterministic behaviour".

Arne

[toc] | [prev] | [next] | [standalone]

#33821

On 2/15/2016 11:08 AM, Philipp Kraus wrote:
> Hello,
>
> I run Stream.concat to concat two streams. These two streams are "stream" and use a flatMap call.
> After the concat I run distinct() to create an unique stream of elements, but I get an indeterministic behaviour of my concated stream, so my question is how can I create a concated and distinct stream?

     SSCCE?

     And what, exactly, do you mean by "indeterministic?"

     Observe that with parallel streams, distinct() is necessarily
non-deterministic: When equal (as reported by equals()) elements are
present, exactly which of the equal elements passes through distinct()
is a matter of happenstance.

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

[toc] | [prev] | [next] | [standalone]

#33824

Am Montag, 15. Februar 2016 17:38:18 UTC+1 schrieb Eric Sosman:
> On 2/15/2016 11:08 AM, Philipp Kraus wrote:
>      And what, exactly, do you mean by "indeterministic?"
> 
>      Observe that with parallel streams, distinct() is necessarily
> non-deterministic: When equal (as reported by equals()) elements are
> present, exactly which of the equal elements passes through distinct()
> is a matter of happenstance.

The stream uses a class which overloads equal (for my data structure), I don't use any parallel stream operation, but the concated stream is incorrect. I use Stream.concat( myfirststream, mysecondstream).distinct().count(), and count returns different results by equal input. 

I tested sequential() but I don't see any mistake of my stream, so I would like to return a stream with unique elements of both streams, but in my two streams some objects are duplicated

[toc] | [prev] | [next] | [standalone]

#33825

On 2/15/2016 12:05 PM, Philipp Kraus wrote:
> Am Montag, 15. Februar 2016 17:38:18 UTC+1 schrieb Eric Sosman:
>> On 2/15/2016 11:08 AM, Philipp Kraus wrote:
>>       And what, exactly, do you mean by "indeterministic?"
>>
>>       Observe that with parallel streams, distinct() is necessarily
>> non-deterministic: When equal (as reported by equals()) elements are
>> present, exactly which of the equal elements passes through distinct()
>> is a matter of happenstance.
>
> The stream uses a class which overloads equal (for my data structure), I don't use any parallel stream operation, but the concated stream is incorrect. I use Stream.concat( myfirststream, mysecondstream).distinct().count(), and count returns different results by equal input.
>
> I tested sequential() but I don't see any mistake of my stream, so I would like to return a stream with unique elements of both streams, but in my two streams some objects are duplicated

     Once again: SSCCE?

     (I can't debug what I can't see.  Not usually, anyhow.)

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

[toc] | [prev] | [next] | [standalone]

#33841

Philipp Kraus <philipp.kraus.flashpixx@gmail.com> wrote:
> The stream uses a class which overloads equal (for my data structure), ...

If you overload equals, then did you also overload hashCode such that it
is consistent with your equals?

I ask, because without knowing much about Java 8 streams yet, "distinct"
sounds like some hashmap or hashset might be used internally, and these
structures will produce odd behaviour, if equals and hashCode are not 
consistent.

Note: a custom equals and default hashCode are almost never consistent.

[toc] | [prev] | [standalone]

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

csiph-web