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.
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 aList<int[]>
which containsarr
6 times, as each member of the first parameter matches each member of the second parameter. Is this the intention? \$\endgroup\$