陣列相交函數速度

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

我期望你會發現，不同的測試情況下，你可以扭轉你上面有結果，達成2最快和1 & 3較慢的情況。

如果不知道測試用例的構成就很難評論，它將取決於兩個數組中「相交」項的位置 - 如果這些數據往往靠近前一個數組並更靠近到另一個的結尾，那麼數組迭代/ IndexOf的嵌套順序將具有明顯不同的性能。

順便說一句 - 有更好的方法來執行交集 - 排序一個或其他數組並執行BinarySearch是一種手段 - 使用Dictionary（Of String，...）或類似的是另一個 - 並且要麼導致遠更好的性能。

Answer 3

這是從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