/
14-Distinct.html
12 lines (12 loc) · 11.7 KB
/
14-Distinct.html
1
2
3
4
5
6
7
8
9
10
11
12
<html>
<head>
<title>Reimplementing LINQ to Objects: Part 14 - Distinct</title>
<link rel="stylesheet" href="codestyles.css" />
</head>
<body>
<h1>Part 14 - Distinct</h1>
<p>I'm going to implement the set-based operators next, starting with Distinct.</p> <h3>What is it?</h3> <p><a href="http://msdn.microsoft.com/en-us/library/system.linq.enumerable.distinct.aspx" target="_blank">Distinct</a> has two overloads, which differ only in the simplest possible way:</p> <div class="code"><span class="Modifier">public</span> <span class="Modifier">static</span> IEnumerable<TSource> Distinct<TSource>( <br />    <span class="Keyword">this</span> IEnumerable<TSource> source) <br /> <br /><span class="Modifier">public</span> <span class="Modifier">static</span> IEnumerable<TSource> Distinct<TSource>( <br />    <span class="Keyword">this</span> IEnumerable<TSource> source, <br />    IEqualityComparer<TSource> comparer) </div> <p>The point of the operator is straightforward: the result sequence contains the same items as the input sequence, but with the duplicates removed - so an input of { 0, 1, 3, 1, 5 } will give a result sequence of { 0, 1, 3, 5 } - the second occurrence of 1 is ignored.</p> <p>This time I've checked and double-checked the documentation - and in this case it really <em>is</em> appropriate to think of the first overload as just a simplified version of the second. If you don't specify an equality comparer, the default comparer for the type will be used. The same will happen if you pass in a null reference for the comparer. The default equality comparer for a type can be obtained with the handy <a href="http://msdn.microsoft.com/en-us/library/ms224763.aspx" target="_blank">EqualityComparer<T>.Default</a> property.</p> <p>Just to recap, an <em>equality comparer </em>(represented by the <a href="http://msdn.microsoft.com/en-us/library/ms132151.aspx" target="_blank">IEqualityComparer<T></a> interface) is able to do two things:</p> <ul> <li>Determine the hash code for a single item of type T </li> <li>Compare any two items of type T for equality </li> </ul> <p>It doesn't have to give any sort of ordering - that's what <a href="http://msdn.microsoft.com/en-us/library/8ehhxeaf.aspx" target="_blank">IComparer<T></a> is for, although that <em>doesn't</em> have the ability to provide a hash code.</p> <p>One interesting point about IEqualityComparer<T> is that the GetHashCode() method is <em>meant</em> to throw an exception if it's provided with a null argument, but in practice the EqualityComparer<T>.Default implementations appear not to. This leads to an interesting question about Distinct: how should it handle null elements? It's not documented either way, but in reality both the LINQ to Objects implementation and the simplest way of implementing it ourselves simply throws a NullReferenceException if you use a not-null-safe comparer and have a null element present. Note that the <em>default</em> equality comparer for any type (EqualityComparer<T>.Default) <em>does</em> cope with nulls.</p> <p>There are other undocumented aspects of Distinct, too. Both the ordering of the result sequence and the choice of which exact element is returned when there are equal options are unspecified. In the case of ordering, it's <em>explicitly</em> unspecified. From the documentation: "The Distinct method returns an unordered sequence that contains no duplicate values." However, there's a natural approach which answers both of these questions. Distinct <em>is</em> specified to use deferred execution (so it won't look at the input sequence until you start reading from the output sequence) but it also streams the results to some extent: to return the first element in the result sequence, it only needs to read the first element from the input sequence. Some other operators (such as OrderBy) have to read <em>all</em> their data before yielding any results.</p> <p>When you implement Distinct in a way which only reads as much data as it has to, the answer to the ordering and element choice is easy:</p> <ul> <li>The result sequence is in the same order as the input sequence </li> <li>When there are multiple equal elements, it is the one which occurs earliest in the input sequence which is returned as part of the result sequence. </li> </ul> <p>Remember that it's perfectly possible to have elements which are considered equal under a particular comparer, but are still clearly different when looked at another way. The simplest example of this is case-insensitive string equality. Taking the above rules into account, the distinct sequence returned for { "ABC", "abc", "xyz" } with a case-insensitive comparer is { "ABC", "xyz" }.</p> <h3>What are we going to test?</h3> <p>All of the above :)</p> <p>All the tests use sequences of strings for clarity, but I'm using four different comparers:</p> <ul> <li>The default string comparer (which is a case-sensitive ordinal comparer) </li> <li>The case-insensitive ordinal comparer </li> <li>A comparer which uses object identity (so will treat two equal but distinct strings as different) </li> <li>A comparer which explicitly <em>doesn't</em> try to cope with null values </li> </ul> <p>The tests assume that the undocumented aspects listed above are implemented with the rules that I've given. This means they're over-sensitive, in that an implementation of Distinct which matches all the <em>documented</em> behaviour but returns elements in a different order would fail the tests. This highlights an interesting aspect of unit testing in general... what exactly are we trying to test? I can think of three options in our case:</p> <ul> <li>Just the documented behaviour: anything conforming to that, however oddly, should pass </li> <li>The LINQ to Objects behaviour: the framework implementation should pass all our tests, and then our implementation should as well </li> <li>Our implementation's known (designed) behaviour: we can specify that our implementation will follow particular rules above and beyond the documented contracts </li> </ul> <p>In production projects, these different options are valid in different circumstances, depending on exactly what you're trying to do. At the moment, I don't <em>have</em> any known differences in behaviour between LINQ to Objects and Edulinq, although that may well change later in terms of optimizations.</p> <p>None of the tests themselves are particularly interesting - although I find it interesting that I had to implement a deliberately fragile (but conformant) implementation of IEqualityComparer<T> in order to test Distinct fully.</p> <h3>Let's implement it!</h3> <p>I'm absolutely confident in implementing the overload that doesn't take a custom comparer using the one that does. We have two options for how to specify the custom comparer in the delegating call though - we could pass null or EqualityComparer<T>.Default, as the two are explicitly defined to behave the same way in the second overload. I've chosen to pass in EqualityComparer<T>.Default just for the sake of clarity - it means that anyone reading the first method doesn't need to check the behavior of the second to understand what it will do.</p> <p>We need to use the "private iterator block method" approach again, so that the arguments can be evaluated eagerly but still let the result sequence use deferred execution. The real work method uses HashSet<T> to keep track of all the elements we've already returned - it takes an IEqualityComparer<T> in its constructor, and the Add method adds an element to the set if there isn't already an equal one, and returns whether or not it <em>really</em> had to add anything. All we have to do is iterate over the input sequence, call Add, and yield the item as part of the result sequence if Add returned true. Simple!</p> <div class="code"><span class="Modifier">public</span> <span class="Modifier">static</span> IEnumerable<TSource> Distinct<TSource>( <br />    <span class="Keyword">this</span> IEnumerable<TSource> source) <br />{ <br />    <span class="Statement">return</span> source.Distinct(EqualityComparer<TSource>.Default); <br />} <br /> <br /><span class="Modifier">public</span> <span class="Modifier">static</span> IEnumerable<TSource> Distinct<TSource>( <br />    <span class="Keyword">this</span> IEnumerable<TSource> source, <br />    IEqualityComparer<TSource> comparer) <br />{ <br />    <span class="Statement">if</span> (source == <span class="Keyword">null</span>)  <br />    { <br />        <span class="Statement">throw</span> <span class="Keyword">new</span> ArgumentNullException(<span class="String">"source"</span>); <br />    } <br />    <span class="Statement">return</span> DistinctImpl(source, comparer ?? EqualityComparer<TSource>.Default); <br />} <br /> <br /><span class="Modifier">private</span> <span class="Modifier">static</span> IEnumerable<TSource> DistinctImpl<TSource>( <br />    IEnumerable<TSource> source, <br />    IEqualityComparer<TSource> comparer) <br />{ <br />    HashSet<TSource> seenElements = <span class="Keyword">new</span> HashSet<TSource>(comparer); <br />    <span class="Statement">foreach</span> (TSource item <span class="Statement">in</span> source) <br />    { <br />        <span class="Statement">if</span> (seenElements.Add(item)) <br />        { <br />            <span class="Statement">yield</span> <span class="Statement">return</span> item; <br />        } <br />    } <br />} </div> <p>So what about the behaviour with nulls? Well, it seems that HashSet<T> just handles that automatically, if the comparer it uses does. So long as the comparer returns the same hash code each time it's passed null, and considers null and null to be equal, it can be present in the sequence. Without HashSet<T>, we'd have had a much uglier implementation - especially as Dictionary<TKey, TValue> doesn't allow null keys.</p> <h3>Conclusion</h3> <p>I'm frankly bothered by the lack of specificity in the documentation for Distinct. Should you rely on the ordering rules that I've given here? I think that in reality, you're reasonably safe to rely on it - it's the natural result of the most obvious implementation, after all. I wouldn't rely on the same results when using a different LINQ provider, mind you - when fetching the results back from a database, for example, I wouldn't be at all surprised to see the ordering change. And of course, the fact that t documentation explicitly states that the result is unordered should act as a bit of a deterrent from relying on this.</p> <p>We'll have to make similar decisions for the other set-based operators: Union, Intersect and Except. And yes, they're very likely to use HashSet<T> too...</p><div style="clear:both;"></div>
<hr />
<p>Back to the <a href="index.html">table of contents</a>.</p>
</body>
</html>