0
\$\begingroup\$

We are given two list on integer arrays, and the objective is to retrieve another list which contains the duplicates in both lists.

The code developed is the following:

public List<int[]> GetDuplicates(List<int[]> pInputList1, List<int[]> pInputList2)
{
    var outputList = new List<int[]>();

    pInputList2.ForEach(x =>
    {
        outputList.AddRange(pInputList1.Select(j => j).Where(y =>
        {
            for (int i = 0; i < y.Length; i++)
                if (y[i] != x[i])
                    return false;
            return true;
        }));
    });

    return outputList;
} 

The code works as intended what I am concerned about is optimization, how to improve this code in both, execution time and stability.

What I am doing in this code is compare each element from one list with ALL of the elements of the other list (I see a problem here, but don't know how to approach it well, the foreach seems not to be the best option here).

\$\endgroup\$
  • \$\begingroup\$ @Oscar Guillamon does the lists must be in the same length? \$\endgroup\$ – morbidCode Jan 11 '16 at 10:27
  • \$\begingroup\$ They must match lengths, forgot to add that into the code, sorry! \$\endgroup\$ – Oscar Guillamon Jan 11 '16 at 10:41
  • \$\begingroup\$ What should it do if the input lists contain duplicates? For example var arr = new int[] { 1 }; var duplicates = GetDuplicates(new List<int[]> { arr, arr }, new List<int[]> { arr, arr, arr });. In your current implementation, this would return a List<int[]> which contains arr 6 times, as each member of the first parameter matches each member of the second parameter. Is this the intention? \$\endgroup\$ – Philip C Jan 11 '16 at 12:51
  • \$\begingroup\$ It should return as much records from the second list that appear at least once in the first list \$\endgroup\$ – Oscar Guillamon Jan 11 '16 at 12:57
  • 1
    \$\begingroup\$ @Oscar Guillamon please edit your question to include all details of your code. \$\endgroup\$ – morbidCode Jan 11 '16 at 13:44
7
\$\begingroup\$

The original code:

public List<int[]> GetDuplicates(List<int[]> pInputList1, List<int[]> pInputList2)
{
    var outputList = new List<int[]>();

    pInputList2.ForEach(x =>
    {
        outputList.AddRange(pInputList1.Select(j => j).Where(y =>
        {
            for (int i = 0; i < y.Length; i++)
                if (y[i] != x[i])
                    return false;
            return true;
        }));
    });

    return outputList;
} 

I'd start with a few readability simplifications first:

  • Select(j => j) is a no-op and can be removed
  • The usage of ForEach is hurting readability (and performance, due to passing delegates around) a little bit
  • Moving the pInputList1.Where(...) outside of the AddRange also makes it clearer what's going on.

public List<int[]> GetDuplicates(List<int[]> pInputList1, List<int[]> pInputList2)
{
    var outputList = new List<int[]>();

    foreach (var x in pInputList2)
    {
        var duplicates = pInputList1.Where(y =>
        {
            for (int i = 0; i < y.Length; i++)
                if (y[i] != x[i])
                    return false;
            return true;
        });

        outputList.AddRange(duplicates);
    }

    return outputList;
}

Next, as mentioned in the comments, the intention is to filter the second list according to whether an identical array appears in the first list. The method and its arguments (and derived local variables) should be renamed to reflect that. I'd also swap the parameters over, because pInputList2 is the important part of the method, while pInputList1 is the set against which pInputList2 is checked.

public List<int[]> FilterByWhitelist(List<int[]> testArrays, List<int[]> whiteListedArrays)
{
    var outputList = new List<int[]>();

    foreach (var testArray in testArrays)
    {
        var duplicates = whiteListedArrays.Where(whiteListedArray =>
        {
            for (int i = 0; i < whiteListedArray.Length; i++)
                if (whiteListedArray[i] != testArray[i])
                    return false;
            return true;
        });

        outputList.AddRange(duplicates);
    }

    return outputList;
}

Using the same point in the comments: we don't need to find every matching array in whiteListedArrays - we only need to know whether there is one. As such, we can use Any instead of Where:

public List<int[]> FilterByWhitelist(List<int[]> testArrays, List<int[]> whiteListedArrays)
{
    var outputList = new List<int[]>();

    foreach (var testArray in testArrays)
    {
        var isWhiteListed = whiteListedArrays.Any(whiteListedArray =>
        {
            for (int i = 0; i < whiteListedArray.Length; i++)
                if (whiteListedArray[i] != testArray[i])
                    return false;
            return true;
        });

        if (isWhiteListed)
        {
            outputList.Add(testArray);
        }
    }

    return outputList;
}

Another bug in this implementation is: what if one of your testArrays is longer than one of the whiteListedArrays? You're accessing x[i] while only ensuring that i is less than the length of y. You'll probably get an ArgumentOutOfRangeException from this. Because two arrays can't be equal if their lengths don't match, this should be checked first.

On the other hand, Linq has a nice built-in method for checking whether two sequences are equal:

public List<int[]> FilterByWhitelist(List<int[]> testArrays, List<int[]> whiteListedArrays)
{
    var outputList = new List<int[]>();

    foreach (var testArray in testArrays)
    {
        var isWhiteListed = whiteListedArrays.Any(
            whiteListedArray => testArray.SequenceEqual(whiteListedArray));

        if (isWhiteListed)
        {
            outputList.Add(testArray);
        }
    }

    return outputList;
}

This method now iterates once over its main argument, and returns a subsequence of that argument. This sounds like an ideal scenario for an extension method on IEnumerable.

public static IEnumerable<int[]> FilterByWhitelist(this IEnumerable<int[]> testArrays, List<int[]> whiteListedArrays)
{
    foreach (var testArray in testArrays)
    {
        var isWhiteListed = whiteListedArrays.Any(
            whiteListedArray => testArray.SequenceEqual(whiteListedArray));

        if (isWhiteListed)
        {
            yield return testArray;
        }
    }
}

This would be called like:

var originalList = new List<int[]> { ... };
var whiteList = new List<int[]> { ... };

var filteredList = originalList.FilterByWhitelist(whiteList).ToList();

One final performance improvement I can see is pre-grouping the whiteListedArrays by length, and only testing for sequence equality where the lengths are already known to be equal:

public static IEnumerable<int[]> FilterByWhitelist(this IEnumerable<int[]> testArrays, List<int[]> whiteListedArrays)
{
    var lengthGroupedWhiteListedArrays = whiteListedArrays
        .GroupBy(arr => arr.Length)
        .ToDictionary(group => group.Key, group => group.ToList());

    foreach (var testArray in testArrays)
    {
        List<int[]> lengthMatchedWhiteListedArrays;

        if (!lengthGroupedWhiteListedArrays.TryGetValue(testArray.Length, out lengthMatchedWhiteListedArrays))
        {
            continue;
        }

        var isWhiteListed = lengthMatchedWhiteListedArrays.Any(
            whiteListedArray => testArray.SequenceEqual(whiteListedArray));

        if (isWhiteListed)
        {
            yield return testArray;
        }
    }
}

At this point, we're only iterating over whiteListedArrays once, so that too can become an IEnumerable:

public static IEnumerable<int[]> FilterByWhitelist(this IEnumerable<int[]> testArrays, IEnumerable<int[]> whiteListedArrays)
{
    var lengthGroupedWhiteListedArrays = whiteListedArrays
        .GroupBy(arr => arr.Length)
        .ToDictionary(group => group.Key, group => group.ToList());

    foreach (var testArray in testArrays)
    {
        List<int[]> lengthMatchedWhiteListedArrays;

        if (!lengthGroupedWhiteListedArrays.TryGetValue(testArray.Length, out lengthMatchedWhiteListedArrays))
        {
            continue;
        }

        var isWhiteListed = lengthMatchedWhiteListedArrays.Any(
            whiteListedArray => testArray.SequenceEqual(whiteListedArray));

        if (isWhiteListed)
        {
            yield return testArray;
        }
    }
}

We could, at this point, extract the array-specific code into a class that encapsulates the whitelist:

public class Whitelist
{
    private readonly IReadOnlyDictionary<int, List<int[]>> _lengthGroupedWhiteListedArrays;

    public Whitelist(IEnumerable<int[]> whitelistedArrays)
    {
        _lengthGroupedWhiteListedArrays= whitelistedArrays
            .GroupBy(arr => arr.Length)
            .ToDictionary(group => group.Key, group => group.ToList());
    }

    public bool Contains(int[] item)
    {
        List<int[]> correctLengthFilterArrays;

        if (!_lengthGroupedWhiteListedArrays.TryGetValue(item.Length, out correctLengthFilterArrays))
        {
            return false;
        }

        return correctLengthFilterArrays.Any(filterArray => item.SequenceEqual(filterArray));
    }
}

...

public static IEnumerable<int[]> FilterByWhitelist(this IEnumerable<int[]> testArrays, Whitelist whitelist)
{
    foreach (var testArray in testArrays)
    {
        if (whitelist.Contains(testArray))
        {
            yield return testArray;
        }
    }
}

Although by doing this, FilterByWhitelist has more or less become Linq's Where:

var originalList = new List<int[]> { ... };
var whiteList = new Whitelist(new List<int[]> { ... });

var filteredList = originalList
    .Where(arr => whiteList.Contains(arr))
    .ToList();

This way, the pre-grouping of array lengths can be used in many places.

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