Скорость пересечения массива

Question

Я написал короткую функцию для пересечения массива и хотел знать, почему одна функция быстрее другой.

1)

Dim list2() As String 'Assume it has values'
Dim list2length As Integer = list2.length

Function newintersect(ByRef list1() As String) As String()
    Dim intersection As New ArrayList
    If (list1.Length < list2length) Then
        'use list2'
        For Each thing As String In list2
            If (Array.IndexOf(list1, thing) <> -1) Then
                intersection.Add(thing)
            End If
        Next
    Else
        'use list1'
        For Each thing As String In list1
            If (Array.IndexOf(list2, thing) <> -1) Then
                intersection.Add(thing)
            End If
        Next
    End If
    Return intersection
End Function

2)

Dim list2() As String 'Assume it has values'
Dim list2length As Integer = list2.length

Function newintersect(ByRef list1() As String) As String()
    Dim intersection As New ArrayList
    If (list1.Length > list2length) Then 'changed >'
        'use list2'
        For Each thing As String In list2
            If (Array.IndexOf(list1, thing) <> -1) Then
                intersection.Add(thing)
            End If
        Next
    Else
        'use list1'
        For Each thing As String In list1
            If (Array.IndexOf(list2, thing) <> -1) Then
                intersection.Add(thing)
            End If
        Next
    End If
    Return intersection
End Function

3)

Dim list2() As String 'Assume it has values'
Dim list2length As Integer = list2.length

Function newintersect(ByRef list1() As String) As String()
    For Each thing As String In list1
        If (Array.IndexOf(list2, thing) <> -1) Then
            intersection.Add(thing)
        End If
    Next
    Return intersection
End Function

Так что для моего тестового примера 1 занимает 65 секунд, 3 - 63 секунды, а 2 на самом деле занимает 75 секунд. Кто-нибудь знает, почему 3 самый быстрый? И почему 1 быстрее, чем 2?

(извините за плохое форматирование ... не могу вставить его правильно)

Answer 1

Это не большая разница. Кроме того, не похоже, чтобы методы давали одинаковый результат, поэтому сравнивать производительность бессмысленно, верно?

Во всяком случае, Array.IndexOf - не очень эффективный способ поиска предметов, и он плохо масштабируется. Вы должны получить значительное улучшение, если вместо этого будете использовать коллекцию на основе хеш-ключа, что-то вроде этого:

Function newintersect(ByRef list1 As String(), ByRef list2 As String()) As String()
  Dim smaller As HashSet(Of String)
  Dim larger As String()
  If list1.Length < list2.Length Then
    smaller = New HashSet(Of String)(list1)
    larger = list2
  Else
    smaller = New HashSet(Of String)(list2)
    larger = list1
  End If
  Dim intersection As New List(Of String)
  For Each item As String In larger
    If smaller.Contains(item) Then
      intersection.Add(item)
    End If
  Next
  Return intersection.ToArray()
End Function

Answer 2

Это из документации MSDN

    Dim id1() As Integer = {44, 26, 92, 30, 71, 38}
    Dim id2() As Integer = {39, 59, 83, 47, 26, 4, 30}

    ' Find the set intersection of the two arrays.
    Dim intersection As IEnumerable(Of Integer) = id1.Intersect(id2)

    For Each id As Integer In intersection
        Debug.WriteLine(id.ToString)
    Next

Answer 3

Я ожидаю, что вы обнаружите, что с различными тестовыми примерами вы можете изменить результаты, которые вы имели выше, и достичь ситуации, когда 2 быстрее, а 1 и 3 медленнее.

Трудно комментировать беззная состав тестового примера, он будет зависеть от расположения «пересекающихся» элементов в двух массивах - если они имеют тенденцию быть ближе к фронту в одном массиве и ближе к концу другого, чем порядок размещенияитерации массива / IndexOf будет иметь заметно отличающуюся производительность.

Кстати - есть лучшие способы выполнения пересечения - сортировка одного или другого массива и выполнение BinarySearch - это одно из средств - использование словаря (Of String,...) или похожий другой - и любой из них приведет к гораздо лучшей производительности.