Path: csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail From: Eric Sosman Newsgroups: comp.lang.java.programmer Subject: Re: stream concat distinct indeterministic Date: Mon, 15 Feb 2016 17:45:50 -0500 Organization: A noiseless patient Spider Lines: 99 Message-ID: References: <6e75cf37-61c1-4ab8-af9b-851fc280244d@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Mon, 15 Feb 2016 22:42:56 -0000 (UTC) Injection-Info: mx02.eternal-september.org; posting-host="2d081e2f7155c28005d4472f67c2f43d"; logging-data="21840"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19ksBQ/wRO+H9dPGujuwFko" User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1 In-Reply-To: Cancel-Lock: sha1:HAdQlEBPaxn3M/gN8BNUAshJaGQ= Xref: csiph.com comp.lang.java.programmer: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