[RESOLVED] [2005] Comparing lists

[Bulldog]

Im trying to compare two lists, to find out how which items occur in both lists. I also want to test for duplication within a list.

Now, the obvious way is a loop/compare which works fine for a low number of items. Beyond 10000 items, things slow down much more than a factor of 10. Is there a better way?

        Dim List1 As New List(Of String)
        Dim List2 As New List(Of String)
        Dim List3 As New List(Of String)
        Dim List4 As New List(Of String)

        'Make two lists of 100000 items
        For i As Integer = 0 To 100000 - 1
            List1.Add("A" & i.ToString)
            List2.Add("B" & i.ToString)
        Next
        'Add 100 items known to be in List1 to List2
        'Add 100 duplicates to List1
        For i As Integer = 0 To 100 - 1
            List1.Add("A" & i.ToString)
            List2.Add("A" & i.ToString)
        Next

        Dim start As DateTime = Date.Now
        For Each s As String In List1
            If List2.IndexOf(s) > -1 Then List3.Add(s)
        Next
        Dim duration As TimeSpan = Date.Now - start
        MessageBox.Show(List3.Count & " common items found in " & duration.TotalMilliseconds & "ms")

        start = Date.Now
        For i As Integer = 0 To List1.Count - 1
            If i < List1.LastIndexOf(List1.Item(i)) Then List4.Add(List1.Item(i))
        Next
        duration = Date.Now - start
        MessageBox.Show(List4.Count & " items with duplicates found in " & duration.TotalMilliseconds & "ms")

[vbasicgirl]

Try sorting the lists then use binarysearch. That should improve the speed.

Casey.

[Bulldog]

Thanks.

That made a dramatic improvement from taking "so long I didnt wait for it to finish" to about 4 seconds.

For posterity I modified the code thus;

        List1.Sort()
        List2.Sort()

        Dim start As DateTime = Date.Now
        For Each s As String In List1
            'If List2.IndexOf(s) > -1 Then List3.Add(s)
            If List2.BinarySearch(s) > -1 Then List3.Add(s)
        Next
        Dim duration As TimeSpan = Date.Now - start
        MessageBox.Show(List3.Count & " common items found in " & duration.TotalMilliseconds & "ms")

        start = Date.Now
        For i As Integer = 0 To List1.Count - 2
            'If i < List1.LastIndexOf(List1.Item(i)) Then List4.Add(List1.Item(i))
            If List1.BinarySearch(i + 1, List1.Count - (i + 1), List1.Item(i), Nothing) > -1 Then List4.Add(List1.Item(i))
        Next
        duration = Date.Now - start
        MessageBox.Show(List4.Count & " items with duplicates found in " & duration.TotalMilliseconds & "ms")

[vbasicgirl]

Your welcome.

Just another note, because your lists are sorted, their is no need to use the binarysearch because if their are duplicates in the list then we know they will be side by side.

Casey.