Searching a list of an int arrays into another list of int arrays

Question

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).

Answer 1

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.