CODEWITHSUNDEEP
c#.netloopsiteration
wondergoat77
wondergoat77

Reputation: 1825

Nested while loop alternatives

I have some code i wrote that follows this basic pattern below. I am looking to see if there are better, more concise or better performing ideas to accomplish the same goal it is going for. the goal is to compare items in one list to items in another and perform an action if they match. the only way i have gotten it to work is the idea below, but i am new to c# and .net and am not sure if there are better ways. 

list A
list B
int counter;
int counter2;
while (counter < comparison item)
{
    while (counter2 < comparison item 2)
    {
        if (A[counter] == B[counter2])
        {
            // do stuff
        }
        counter2++;
    }
    counter++;
}

Upvotes: 2

Views: 1420

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726799

This two-loop construct is simple, but it is not performant. The problem is the number of comparisons: if the first set has N items and the second has M, then there would be N*M comparisons. With 1,000 items in each set, we're talking about 1,000,000 comparisons.

A better approach would be to hash the items of the first set, and then search the hash for the items from the second set. Since hashing is done in amortized constant time, you can do this in M+N operations, or about 2,000 for two sets of 1,000 items each:

var setA = new HashSet<int>(listA);
foreach (var b in listB) {
    if (setA.Contains(b)) {
        ...
    }
}

LINQ library lets you do this in even fewer lines of code:

foreach (var ab in listA.Intersect(listB)) {
    ...
}

Upvotes: 3

Daniel Imms
Daniel Imms

Reputation: 50229

If you don't need to change the lists then you should use a foreach loop.

foreach (var itemA in A)
{
    foreach (var itemB in B)
    {
        if (itemA == itemB) {}
    }
}

If you do need to change the lists then you should use a for loop.

for (var i = 0; i < A.Count; i++) 
{
    for (var j = 0; j < B.Count; j++)
    {
        if (A[i] == B[j]) {}
    }
}

If the two lists are sorted you can do this much more efficiently by going through the lists in order.

int i = 0;
int j = 0;

while (A.Length <= i && B.Length <= j)
{
    if (A[i] == B[j]) 
    {
        // items are equal
        i++;
        j++;
    }
    else if (A[i] > B[j]) // Comparison of the ordered value, could be a property on the item.
    {
        j++; // increment B's counter
    }
    else
    {
        i++; // increment A's counter
    }
}

Upvotes: 1

Related Questions