.net - .net arraylist に同じ値を持つ 2 つ以上の項目があるかどうかを確認するためのパフォーマンスに最適なコードは何ですか?

Question

値を持つアイテムが配列リストに存在するかどうかを確認したくありません。

配列リストに同じ値を持つ同じアイテムが何回出現するかを取得するためのパフォーマンスに最適なコードを知りたいです。

私は次のようなことができます

For Each s As string In myArrayList
[...]
Next

しかし、それのより良いコードはありますか?

Answer 1

で特定の要素が何回繰り返されているかを確認したいようですArrayList。その場合は、次のことを試してください

Dim table As New Dictionary(Of String, Integer)
For Each s As String in myArrayList
  Dim count As Integer = 0
  If table.TryGetValue(s, count) Then
    table(s) = count + 1
  Else 
    table(s) = 1
  End If
Next

For Each pair in table 
  If pair.Value >= 2 Then
    Console.WriteLine(pair.Key)
  End If
Next

注: これは、Visual Studio 2005 以降を使用していることを前提としています。そうでない場合はお知らせください。2003年対応の回答を提供します

Answer 2

SortArrayList最初に使用しますBinarySearch。別のコレクションを作成したり、アイテムをルックアップするために既存のものを完全にループしたりする必要がないため、これは Dictionary アプローチよりもさらに優れたパフォーマンスを提供するはずです。

もちろん、これはエレガントで読みやすいコードとは言えませんが、高速です(10 MM のルックアップで約 2 秒)。

Dim letters = New ArrayList() From {"A", "B", "C", "D", "A", "C", "E", "cC", "C", "E", "A", "c", "C", "F", "C"}
letters.Sort() ' just needed once and only if it's not already sorted 
Dim lookupItem = "C"
Dim itemCount = 0 ' correct result: 5 (case-sensitive) 
Dim index = letters.BinarySearch(lookupItem)
If index > -1 Then
    Dim nextIndex = index
    While letters(nextIndex).Equals(lookupItem)
        itemCount += 1
        nextIndex += 1
    End While
    If index > 0 Then
        ' look into the other direction since BinarySearch 
        ' does not necessarily return the first index 
        ' in this example index is 6 instead of 5
        Dim prevIndex = index - 1
        While letters(prevIndex).Equals(lookupItem)
            itemCount += 1
            prevIndex -= 1
        End While
    End If
End If

の型をvalue実装するIComparableか、に渡すことができるカスタム Comparer を定義する必要があることに注意してくださいBinarySearch。

ところで、 an の代わりに、ArrayLista などの強力なタイド ジェネリック リストを使用する必要がありますList(Of String)。

---

編集：私はすでにジェネリックについて言及しているので、便利な拡張メソッドですでにラップされているLists別のアプローチを紹介します：Lists(Of T)

Public Module ListExtensions
    <Runtime.CompilerServices.Extension()> _
    Public Function ItemCount(Of T)(ByVal sortedList As List(Of T), item As T) As Int32
        Dim count = 0
        Dim index = sortedList.BinarySearch(item)
        Dim nextIndex = index
        If index > -1 Then
            While nextIndex < sortedList.Count AndAlso sortedList(nextIndex).Equals(item)
                count += 1
                nextIndex += 1
            End While
            If index > 0 Then
                Dim prevIndex = index - 1
                While prevIndex > 0 AndAlso sortedList(prevIndex).Equals(item)
                    count += 1
                    prevIndex -= 1
                End While
            End If
        End If
        Return count
    End Function
End Module

これで、任意の種類のリスト内の任意のオブジェクトの itemcount をどこでも取得できます。たとえば、いくつかの測定値を含むaList(Of String)と aです。List(Of Integer)

Const chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
Dim rnd As New Random()
Dim letters = Enumerable.Range(1, 100000).Select(Function(i) chars(rnd.Next(0, chars.Length)).ToString).ToList
Dim letterTime = New Stopwatch
letterTime.Start()
letters.Sort()
For i = 1 To 100000
    Dim count = letters.ItemCount("C")
Next
letterTime.Stop()

Dim numbers = Enumerable.Range(1, 100000).Select(Function(i) rnd.Next(100000)).ToList()
Dim numberTime = New Stopwatch
numberTime.Start()
numbers.Sort()
For i = 1 To 100000
    Dim count = numbers.ItemCount(4711)
Next
numberTime.Stop()

' measure the LINQ Where-Extension

Dim letterTimeWhere = New Stopwatch
letterTimeWhere.Start()
For i = 1 To 100000
    Dim count = letters.Where(Function(str) str.Equals("C")).Count()
Next
letterTimeWhere.Stop()

Dim numberTimeWhere = New Stopwatch
numberTimeWhere.Start()
For i = 1 To 100000
    Dim count = numbers.Where(Function(int) int = 4711).Count()
Next
numberTimeWhere.Stop()

100000 項目のリストで 100000 文字列/整数を検索した結果。

Dim time = String.Format("String(Binary): {0} Numbers(Binary): {1} String(LINQ): {2} Numbers(LINQ): {3}", letterTime.Elapsed.ToString, numberTime.Elapsed.ToString, letterTimeWhere.Elapsed.ToString, numberTimeWhere.Elapsed.ToString)
' String(Binary): 00:00:05.2602861 Numbers(Binary): 00:00:00.0350816 
' String(LINQ)  : 00:04:56.8772996 Numbers(LINQ)  : 00:01:43.2139190 
' => Binary 55 x faster                => Binary 2950 x faster

注Where:すべての項目をループする必要があり、検索を最適化BinarySearchできるため、 LINQ 比較は確かに不公平です。完全を期すために。

---

ちなみに @JaredParsDictionaryは、リストに重複が多い場合にはるかに高速です (そのため、手紙のサンプルのように Dictionary が小さいサイズになっています。

String(Dict)  : 00:00:00.0224329     Numbers(Dict): 00:00:00.0216544

私は敗北を認めます;）

拡張としての彼の辞書は次のとおりです。

<Runtime.CompilerServices.Extension()> _
Public Function ToCountLookup(Of T)(ByVal list As List(Of T)) As Dictionary(Of T, Int32)
    Dim table As New Dictionary(Of T, Integer)
    For Each s As T In list
        Dim count As Int32 = 0
        If table.TryGetValue(s, count) Then
            table(s) = count + 1
        Else
            table(s) = 1
        End If
    Next
    Return table
End Function    

そして、この方法でそれを使用できます。そのキーが含まれていない可能性があるTryGetValueため、必要です。Dictionary

Dim letterLookuptable = letters.ToCountLookup()
For i = 1 To 100000
    Dim count = 0
    letterLookuptable.TryGetValue("C", count)
Next

Dim intLookuptable = numbers.ToCountLookup()
For i = 1 To 100000
    Dim count = 0
    intLookuptable.TryGetValue(4711, count)
Next