1

配列交差の短い関数を作成しましたが、ある関数が他の関数よりも高速である理由を知りたいと思っていました。

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 よりも速いのでしょうか?

（フォーマットが悪くてすみません...正しく貼り付けられないようです）

4

3 に答える 3

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
于 2010-09-08T22:52:31.737 に答える
0

さまざまなテスト ケースを使用すると、上記の結果を逆にして、2 が最速で 1 と 3 が遅いという状況に到達できることがわかると思います。

テストケースの構成を知らずにコメントするのは難しいです.2つの配列内の「交差する」アイテムの位置に依存します.別の場合、配列の反復 / IndexOf のネスト順序によって、パフォーマンスが著しく異なります。

ところで-交点を実行するより良い方法があります-1つまたは他の配列をソートしてBinarySearchを実行することは1つの手段です-Dictionary(Of String、...)または同様のものを使用することは別の方法です-どちらもはるかに優れたパフォーマンスになります。

于 2010-09-08T22:31:00.523 に答える
0

これは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
于 2010-09-09T11:43:15.993 に答える