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

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

Re: stream concat distinct indeterministic

Show all headers | View raw

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

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