Script taking too long

The arrayGroup below will be containing almost 190,000 int arrays.

so filtering them to retrieve groups of arrays in the array group that have two or more common digits is taking forever.

I am using the linq expression below, any ideas to make this more efficient?

List arrayGroup = new List();

var filteredGroups = arrayGroup

.SelectMany(arr1 => arrayGroup

.Where(arr2 => arr1 != arr2) // Don't compare array to itself

.Select(arr2 => new

{

Source = arr1,

Target = arr2,

Common = arr1.Intersect(arr2).Distinct().Count()

})

)

.Where(match => match.Common >= 2)

.GroupBy(match => match.Source)

.Select(group => group.Key)

.ToList();

For 190,000 arrays, the real bottleneck is the comparison. Optimizing the LINQ expression will not provide significant gains: instead A more scalable approach is to build an inverted index that maps each digit to the arrays containing it. This lets you identify only the array pairs that actually share values, instead of comparing every array against every other array.

Example:

var digitIndex = new Dictionary>();

for (int i = 0; i < arrayGroup.Count; i++)

{

foreach (var digit in arrayGroup[i].Distinct())

{

if (!digitIndex.TryGetValue(digit, out var list))

{

list = new List();

digitIndex[digit] = list;

}

list.Add(i);

}

Once the index is built, generate candidate pairs only from arrays that share at least one digit:

var pairCounts = new Dictionary<(int, int), int>();

foreach (var arrays in digitIndex.Values)

{

for (int i = 0; i < arrays.Count; i++)

{

for (int j = i + 1; j < arrays.Count; j++)

{

var pair = (arrays[i], arrays[j]);

pairCounts.TryGetValue(pair, out int count);

pairCounts[pair] = count + 1;

}

Now any pair with a count >= 2 already has two common digits:

var filteredGroups = pairCounts

.Where(x => x.Value >= 2)

.Select(x => arrayGroup[x.Key.Item1])

.Distinct()

.ToList();

Note: This is a sample implementation for demonstration purposes. Please review and adjust it according to your application's requirements.

1 Reply

Know the answer? Post it — somebody with the same question will find it here.

Sudarshan Hajare3mo ago
For 190,000 arrays, the real bottleneck is the comparison. Optimizing the LINQ expression will not provide significant gains: instead A more scalable approach is to build an inverted index that maps each digit to the arrays containing it. This lets you identify only the array pairs that actually share values, instead of comparing every array against every other array.
Example:
var digitIndex = new Dictionary>();
for (int i = 0; i < arrayGroup.Count; i++)
{
foreach (var digit in arrayGroup[i].Distinct())
{
if (!digitIndex.TryGetValue(digit, out var list))
{
list = new List();
digitIndex[digit] = list;
}
list.Add(i);
}
}
Once the index is built, generate candidate pairs only from arrays that share at least one digit:
var pairCounts = new Dictionary<(int, int), int>();
foreach (var arrays in digitIndex.Values)
{
for (int i = 0; i < arrays.Count; i++)
{
for (int j = i + 1; j < arrays.Count; j++)
{
var pair = (arrays[i], arrays[j]);
pairCounts.TryGetValue(pair, out int count);
pairCounts[pair] = count + 1;
}
}
}
Now any pair with a count >= 2 already has two common digits:
var filteredGroups = pairCounts
.Where(x => x.Value >= 2)
.Select(x => arrayGroup[x.Key.Item1])
.Distinct()
.ToList();
Note: This is a sample implementation for demonstration purposes. Please review and adjust it according to your application's requirements.
0