CODEWITHSUNDEEP
vb.net
Kumba
Kumba

Reputation: 2428

Comparing an item in a list against other items in the same list in VB.NET

Simplified, I have a List(Of MyObj), and I want to iterate through that list and compare each element to all other elements in the same list, excluding (if possible) the same element. I have a solution that works, but it's slow and uses double For loops. It may possibly have also summoned Cthulhu from his sleep.

Is there a better approach? Linq, perhaps? Or some fancy algorithm? This below is a sanitized version of what I have:

Dim MyList As New List(Of MyObj)({Obj1, Obj2, Obj3, Obj4, Obj5, Obj6})

If MyList.Count > 0 Then
    For i = 0 To (MyList.Count - 1) Step 1
        For j As Int32 = 0 To (MyList.Count - 1) Step 1
            If MyList(i).GetHashCode = MyList(j).GetHashCode Then
                Continue For
            Else
                If MyList(i).SomeFunction(MyList(j)) Then
                    Call DoSomething()
                End If
            End If
        Next j
    Next i
Else
    ' Error Code Here.
End If

Upvotes: 2

Views: 3546

Answers (3)

Bala R
Bala R

Reputation: 108987

See if this will work

MyList.Select(Function(x) MyList.Except(New () {x}).ToList().ForEach(Sub(y) Do
    If x.SomeFunction(y) Then
        DoSomething()
    End If
End Sub))

Upvotes: 1

Brian Webster
Brian Webster

Reputation: 30865

This will work in O(M*N) where N is ObjCount and M is the number of non-duplicate objects. Your current solution is O(N^2).

  1. You need a Hash Function. You can determine whether GetHashCode will suffice or whether you need to implement Sha1.

  2. Instantiate a HashSet (or HashTable, depending on your Hash Function)

  3. Add each object, if it does not already exist, into the HashSet or HashTable.

  4. For each object in the HashSet, execute SomeFunction() against every other object in the HashSet. If you dump into an array and iterate via indexes, you only have to compare indexes, rather than objects.

    For i as integer = 0 to MyHashResultsArray.Count - 1
  For j as integer = 0 to MyHashResultsArray.Count - 1
    if i <> j then
      MyHashResultsArray(i).DoSomething(j)
    end if
  next
next

Important

This is only a good solution IF there exists a significant amount of duplicates, perhaps a duplicate-level of 10% would be necessary to consider this solution, except for very large values of N. If N gets too large, a re-engineering of the application may be necessary to hopefully avoid the need for M actions against M objects.

Edit

Much of the comment discussion was based upon my misunderstanding of the Author's needs regarding the DoSomething() function.

Upvotes: 1

Will A
Will A

Reputation: 25008

Barring any potential problems with using GetHashCode to check for object equality (best not to do this - it'll only bite you at some point - and it's probably this that has awakened Cthulhu!), your solution is about as fast as it's likely to get.

Sure, you can tweak it, but it will remain O(N^2), that is, the runtime will be of the order of the square of the number of elements in your list. If you double the number of elements, your runtime will increase by a factor of 4.

Upvotes: 1

Related Questions