2
\$\begingroup\$

List<string> difference tool for two input List<string> listA and listB

Output List<string>

  • both - in both listA and listB
  • listAonly - in listA only
  • listBonly - in listB only

Looking for speed, space, and style

.

//test
List<string> both;
List<string> both;
List<string> listAonly;
List<string> listBonly;
ListDiff( new List<string>() { "AAA", "BBB", "CCC", "DDD", "GGG", "FFF", "BBB", "GGG" }
        , new List<string>() { "AAA", "BBB", "DDD", "FFF", "EEE", "FFF", "EEE" }
        , false, out both, out listAonly, out listBonly );
Debug.WriteLine("both");
foreach (string s in both)
    Debug.WriteLine($"  {s}");
Debug.WriteLine("listAonly");
foreach (string s in listAonly)
    Debug.WriteLine($"  {s}");
Debug.WriteLine("listBonly");
foreach (string s in listBonly)
    Debug.WriteLine($"  {s}");
//end test

public static void ListDiff(List<string> listA, List<string> listB, bool ignoreCase, out List<string> both, out List<string> listAonly, out List<string> listBonly)
{
    both = new List<string>();
    listAonly = new List<string>();
    listBonly = new List<string>();

    IEnumerable<string> listAsorted = listA.OrderBy(x => x).Distinct();
    IEnumerable<string> listBsorted = listB.OrderBy(x => x).Distinct();

    var listAenumerator = listAsorted.GetEnumerator();
    var listBenumerator = listBsorted.GetEnumerator();

    bool listAcanmove = listAenumerator.MoveNext();
    bool listBcanmove = listBenumerator.MoveNext();

    while (listAcanmove | listBcanmove)
    {
        string valueA = listAenumerator.Current;
        string valueB = listBenumerator.Current;

        //Debug.WriteLine($"valueA = {valueA}");
        //Debug.WriteLine($"valueB = {valueB}");

        if (!listAcanmove && listBcanmove)
        {
            //Debug.WriteLine($"{valueB} in B not in A");
            listBonly.Add(valueB);
            listBcanmove = listBenumerator.MoveNext();
        }
        if (listAcanmove && !listBcanmove)
        {
            //Debug.WriteLine($"{valueA} in A not in B");
            listAonly.Add(valueA);
            listAcanmove = listAenumerator.MoveNext();
        }
        else
        {
            int comp = string.Compare(valueA, valueB, ignoreCase);
            if (comp == -1)
            {
                //Debug.WriteLine($"{valueA} in A not in B");
                listAonly.Add(valueA);
                listAcanmove = listAenumerator.MoveNext();
            }
            else if (comp == 1)
            {
                //Debug.WriteLine($"{valueB} in B not in A");
                listBonly.Add(valueB);
                listBcanmove = listBenumerator.MoveNext();
            }
            else
            {
                //Debug.WriteLine($"{valueA} {valueB} in B and A");
                both.Add(valueA);
                listAcanmove = listAenumerator.MoveNext();

                listBcanmove = listBenumerator.MoveNext();
            }
        }
        //Debug.WriteLine("");
    }
    //Debug.WriteLine($"done");
}
\$\endgroup\$
  • \$\begingroup\$ I'll write a full review soon but my initial impression is that this doesn't cope when an item is duplicated, for example if add another "AAA" to listA then it appears in "both" and "listAonly". \$\endgroup\$ – Eterm Jul 18 '17 at 17:08
  • \$\begingroup\$ @Eterm I think you are correct and I think I know how to fix it. \$\endgroup\$ – paparazzo Jul 18 '17 at 17:18
  • \$\begingroup\$ Down vote may I ask the problem? \$\endgroup\$ – paparazzo Jul 18 '17 at 17:32
  • 2
    \$\begingroup\$ @Paparazzi I didn't downvote but I assume the lack of explanation of the problem you're solving. \$\endgroup\$ – Denis Jul 18 '17 at 17:46
  • 4
    \$\begingroup\$ @Paparazzi It indicates lack of effort, I haven't looked at your code to answer your question. \$\endgroup\$ – Denis Jul 18 '17 at 17:50
5
\$\begingroup\$

You asked about style so I'll start off with a few points around that.


Don't leave commented code around especially when you're asking for a code review. It adds a lot of needless noise.


I've noticed that you seem to prefer to use Debug.WriteLine rather than stepping through with a debugger. I'm interested to know why you do that, it certainly takes more time to write the code that way.


Your naming is a bit sloppy, e.g. listAonly should be listAOnly at the least.


Why are you using out parameters here? I think you should create a class to return the data.


Why have you tied yourself to string only lists? There's nothing here (apart from the case sensitivity flag) which couldn't work on generic lists.


I think there's a simpler algorithm here that leverages a HashSet<T>. Note that I'm trading reduced complexity and time for more memory.

// Simple wrapper around the 3 lists.
public class DiffData<T>
{
    public IEnumerable<T> InBoth {get;set;}
    public IEnumerable<T> InLeftOnly {get;set;}
    public IEnumerable<T> InRightOnly {get;set;}
}

// Convenience so we don't always have to supply a comparer 
public static DiffData<T> DiffList<T>(List<T> left, List<T> right)
{
    return DiffList(left, right, EqualityComparer<T>.Default);
}

public static DiffData<T> DiffList<T>(List<T> left, List<T> right, IEqualityComparer<T> comparer)
{
    var diffFilter = new HashSet<T>(left, comparer);
    var both = new List<T>();
    var rightOnly = new List<T>();

    foreach(var item in right.Distinct())
    {
        if (diffFilter.Contains(item))
        {
            both.Add(item);
            diffFilter.Remove(item);
        }
        else 
        {
            rightOnly.Add(item);
        }
    }
    var leftOnly = diffFilter.ToList();
    return new DiffData<T> 
    {
        InBoth = both,
        InLeftOnly = leftOnly,
        InRightOnly = rightOnly
    };
}

I hope the code is self describing. You can call it like this:

var result = DiffList(new List<string> { "A", "B", "C", "D"}, new List<string> { "A", "C", "E"});

If time performance really is critical (I doubt it is), you can create the lists with an initial capacity equal to the size of the bigger list. That way the lists won't need to resize and Add will be O(1); if you did that then this is O(n).


Edit

After reading a comment on RubberDuck's excellent answer, I decided to do a bit of very rough and not at all reliable tests for speed.

This answer is only about 2-2.5x faster than the simpler solution (3 Linq calls). I looked at the reference source and see that they rely on a much simpler Set<T> for Except and Intersect which appears to be a bit faster than HashSet<T>.

My testing also puts the OP at least an order of magnitude slower.

I'd just use the 3 lines of Linq to be honest.

\$\endgroup\$
  • \$\begingroup\$ Question specifically stated space. I use WriteLine because I like the line written out. Clever approach. \$\endgroup\$ – paparazzo Jul 19 '17 at 8:57
  • \$\begingroup\$ @Paparazzi - sorry. I didn't realise that you meant space in a memory context. I thought you were talking about space in a style context. \$\endgroup\$ – RobH Jul 19 '17 at 9:13
  • \$\begingroup\$ This is faster. Faster then mine or Intersect Except. It is not minimum space but still a good answer. \$\endgroup\$ – paparazzo Jul 19 '17 at 14:24
7
\$\begingroup\$

I wouldn't want to maintain this code. Unless you have proven that this code is a performance problem, do the simple thing. Yes, the following solution will iterate over the lists 3 times. No, I don't care that it does.

var both = listA.Intersect(listB);
var listAOnly = listA.Except(listB);
var listBOnly = listB.Except(listA);

If you're worried about case insensitivity, pass in a StringComparer.

\$\endgroup\$
  • \$\begingroup\$ It should iterate 3 times, you're doing 3 separate things, that's something OP is missing. \$\endgroup\$ – Denis Jul 19 '17 at 0:29
  • \$\begingroup\$ There maybe a usecase (likely millions of records) where you'd want to go from O(3(n^2)) to O(n^2) and optimize, but then I'd likely just make each of them their own task to be run in parallel. \$\endgroup\$ – RubberDuck Jul 19 '17 at 0:35
  • \$\begingroup\$ Then don't care. It is O(nlogn) because of the sort. \$\endgroup\$ – paparazzo Jul 19 '17 at 5:51
  • \$\begingroup\$ @Denis So if I need milk, bread, and eggs I should go to the store 3 times because it is 3 separate things? \$\endgroup\$ – paparazzo Jul 19 '17 at 9:18
  • 3
    \$\begingroup\$ If you need to handle large amounts of data that's full of hash collisions then this may not be suitable, but in the few tests I ran (1 million random strings, 5-50 alpha-numeric characters each, using a StringComparer) it's actually faster than the OP's code by a factor of 4 on average. \$\endgroup\$ – Pieter Witvoet Jul 19 '17 at 11:39
5
\$\begingroup\$

Firstly, your algorithm fails in the case where listA or listB can have duplicates.

You should generate more test cases and check them against the following code. This code is not as efficient as it can be since it enumerates the list many times over, but should provide you cases for comparison:

public static void ListDiff2(List<string> listA, List<string> listB, bool ignoreCase,  
                                    out List<string> both, out List<string> listAonly, out List<string> listBonly)
    {

        both = listA.Where(a => listB.IndexOf(a) >= 0).ToList();
        listAonly = listA.Where(a => listB.IndexOf(a) == -1).ToList();
        listBonly = listB.Where(a => listA.IndexOf(a) == -1).ToList();
    }

Secondly, your style is over-engineered with a lot of checking for the end of the lists. It is better to loop while you can move either iterator and then consider that if you have an empty list on one side, then all the remaining items end up in "listAonly" or "listBonly" as appropriate.

Note that with your comparisons you could also use switch/case after your string comparison, however the specification doesn't actually guarentee that String.Compare returns -1, 0 or 1, just that it will be less than zero, equal to zero or greater than zero.

I would avoid the use of iterators and instead prefer indexes when all you are doing is moving them next by one.

Applying all those refactorings results in the following:

public static void ListDiff(List<string> listA, List<string> listB, bool ignoreCase,  
                                out List<string> both, out List<string> listAonly, out List<string> listBonly)
{
    both = new List<string>();
    listAonly = new List<string>();
    listBonly = new List<string>();

    List<string> listAsorted = listA.OrderBy(x => x).Distinct().ToList();
    List<string> listBsorted = listB.OrderBy(x => x).Distinct().ToList();

    int listAindex = 0;
    int listBindex = 0;

    int aLength = listAsorted.Count();
    int bLength = listBsorted.Count();

    while (listAindex < aLength && listBindex < bLength)
    {
        int comp = string.Compare(listAsorted[listAindex], listBsorted[listBindex], ignoreCase);

        if (comp < 0)
            {
                listAonly.Add(listAsorted[listAindex]);
                listAindex++;
            }
            else if (comp > 0)
            {
                listBonly.Add(listBsorted[listBindex]);
                listBindex++;
            }
            else
            {
                both.Add(listAsorted[listAindex]);
                listAindex++;
                listBindex++;
            }
    }
    //loop has finished, add any remaining items to list.
    while(listAindex < aLength)
        listAonly.Add(listAsorted[listAindex++]);
    while(listBindex < bLength)
        listBonly.Add(listBsorted[listBindex++]);
}

On in your preferred iterator style, this looks like:

public static void ListDiff(List<string> listA, List<string> listB, bool ignoreCase,  
                                out List<string> both, out List<string> listAonly, out List<string> listBonly)
{
    both = new List<string>();
    listAonly = new List<string>();
    listBonly = new List<string>();

    IEnumerable<string> listAsorted = listA.OrderBy(x => x).Distinct();
    IEnumerable<string> listBsorted = listB.OrderBy(x => x).Distinct();

    int aLength = listAsorted.Count();
    int bLength = listBsorted.Count();

    var listAenumerator = listAsorted.GetEnumerator();
    var listBenumerator = listBsorted.GetEnumerator();

    bool listAcanmove = listAenumerator.MoveNext();
    bool listBcanmove = listBenumerator.MoveNext();

    while (listAcanmove && listBcanmove)
    {
        int comp = string.Compare(listAenumerator.Current, listBenumerator.Current, ignoreCase);

        if (comp < 0)
            {
                listAonly.Add(listAenumerator.Current);
                listAcanmove = listAenumerator.MoveNext();
            }
            else if (comp > 0)
            {
                listBonly.Add(listBenumerator.Current);
                listBcanmove = listBenumerator.MoveNext();
            }
            else
            {
                both.Add(listAenumerator.Current);
                listAcanmove = listAenumerator.MoveNext();
                listBcanmove = listBenumerator.MoveNext();
            }
    }
    //loop has finished, add any remaining items to list.
    while(listAcanmove)
    {
        listAonly.Add(listAenumerator.Current);
        listAcanmove = listAenumerator.MoveNext();
    }

    while(listBcanmove)
    {
        listBonly.Add(listBenumerator.Current);
        listBcanmove = listBenumerator.MoveNext();
    }
}
\$\endgroup\$
  • \$\begingroup\$ This could be further improved by using List.AddRange to add the remaining items. \$\endgroup\$ – Eterm Jul 18 '17 at 17:56
  • \$\begingroup\$ Thanks. I had already fixed the Distinct and it looks like we posted at the same time. I happen to like like the Enumerator. I used on a very large application and got better performance compared in index. I happen to like IEnumerable rather than allocate another List. Not getting how move 1 by 1 is a reason not to use and iterator. Still great feedback. Not getting how move 1 by 1 is a reaso +1 \$\endgroup\$ – paparazzo Jul 18 '17 at 18:04
  • \$\begingroup\$ I can add another version with iterators instead of indexes, the key difference is not having the "canMove" checks twice. In your original you check them for the loop then test each again in case one can move. If you have very different length lists then it is much more efficient to recognise when one list is empty and the other can be moved across to one of the buckets. \$\endgroup\$ – Eterm Jul 18 '17 at 18:08
  • 1
    \$\begingroup\$ It's not a literal cost of the comparisons, comparing booleans is quick, but the cost of maintainability and readability of having an extra nesting of conditionals. It can be hard to read if / else if nested under another else branch. This avoids such nesting. \$\endgroup\$ – Eterm Jul 18 '17 at 18:20
  • 1
    \$\begingroup\$ I am not talking of your parameter naming, I am saying that in your original you have nested conditionals. It is hard to quickly reason about an "if / else if / else" block nested in another "else" block, there is a lot of conditions to keep track of. This removes the whole first if block from your original code by incorporating those conditions into the loop. \$\endgroup\$ – Eterm Jul 18 '17 at 18:26
1
\$\begingroup\$

I have one very specific suggestion, that may or may not be worth a whole answer. Oh well, here goes anyway:

I'm not a fan of using function parameters as outputs. I've worked with languages that allow this before, and I generally find it to be confusing down the road and error-prone. Inevitably what happens is you forget that half of your function parameters are outputs instead of inputs, and when you look over the code that uses your function you'll need a minute to figure out what is actually input and what is output. In other words, I find this general syntax:

output = function( input1, input2 )

Much more clear and less confusing than this:

function( input1, input2, output )

In cases like this where a function has to return multiple values, it's just a simple matter of unpacking the return value. From my quick googling C# doesn't have any simple syntax for unpacking return values, but it is still very straight-forward to do if you return a tuple, which is perfect (https://stackoverflow.com/a/8514859/1921979):

var returned = ListDiff( listA, listB );
var Both = returned.Both;
var listAOnly = returned.listAOnly;
var listBOnly = returned.listBOnly;

Granted, this is more verbose due to the lack of an unpacking operator, but the intent is much more clear. That's a big win in my book (also, you don't necessarily have to unpack everything into its own variable). I suppose others may have different opinions though.

\$\endgroup\$
  • \$\begingroup\$ But you cannot forget. It must have in out. I would find working with a tuple much more confusing and then you have to know what it in the tuple. \$\endgroup\$ – paparazzo Jul 18 '17 at 19:41
  • \$\begingroup\$ As I said, others may disagree. To some extent it is a matter of personal preference. There may be better ways of returning multiple parameters in C#, as I'm not an expert in it. When I do the equivalent in typescript I just return an object and type it clearly, which mitigates any confusion (especially if your IDE is smart enough to follow the code and provide suggestions). Roughly: function multiple_return( listA: integer[], listB: integer[] ): { both: integer[], listAOnly: integer[], listBOnly: integer[] }. Either way, I think it is worth pointing out that there are other options. \$\endgroup\$ – Conor Mancone Jul 18 '17 at 20:03
  • \$\begingroup\$ Don't know how it could be more clear than List<string> listA, List<string> listB, bool ignoreCase, out List<string> both, out List<string> listAonly, out List<string> listBonly \$\endgroup\$ – paparazzo Jul 18 '17 at 20:13
  • 1
    \$\begingroup\$ Wish I could move this to chat... oh well. Anyway... your out identifier makes it clear that it is output when you are looking at the function definition. When you look at the function call as used by other code, you have no indications as to what is input and what is output. Again, I'm sure personal preference plays a role here, but I would rather have input/output be explicitly defined in all contexts. \$\endgroup\$ – Conor Mancone Jul 18 '17 at 20:56
  • 1
    \$\begingroup\$ I would recommend returning a tuple with named members and/or deconstructing it. (C# 7) `var (both, a, b) = ListDiff(listA, listB) \$\endgroup\$ – RubberDuck Jul 18 '17 at 22:52
0
\$\begingroup\$

Based on the accepted answer I ended up with this.
It is fast. Faster than my original or Intersect Except.
Even take out the sort time this is faster than my original.

public static void ListDiffHash(List<string> listA, List<string> listB, bool ignoreCase, out List<string> both, out List<string> listAonly, out List<string> listBonly)
{
    both = new List<string>(Math.Min(listA.Count, listB.Count)/2);
    listAonly = new List<string>();
    listBonly = new List<string>(listB.Count/2);
    var diffFilter = new HashSet<string>(listA);
    foreach(var item in listB.Distinct())
    {
        if (diffFilter.Contains(item))
        {
            both.Add(item);
            diffFilter.Remove(item);
        }
        else 
        {
            listBonly.Add(item);
        }
    }
    listAonly = diffFilter.ToList();
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.