-2

2 つのリストをトラバースし、両方のリストの要素間の一致に基づいて 2 番目のリストのインデックスを返す効率的な方法を見つけようとしています。次に、インデックスを使用して別の配列からデータを検索するため、2 番目のリストは基本的に配列の位置を保持します。

どちらの List も RowType 型で、

public class RowType 
{
    public int Type; //Acts as a group
    public int SubType; //Specific classification of the type
}

私の現在のアプローチは、最初のリストを反復処理してから、要素ごとに、Type または Type\Subtype の組み合わせを比較して 2 番目のリストを反復処理し、インデックスを取得することです。これは本質的に O(n*m) であり、全体的なパフォーマンスを引き下げています。

List1 には、Type のみが指定されているか、Type と SubType の両方が指定されているRowType 要素の組み合わせを含めることができます。

List2 には、 Type と SubType の両方を持つ要素が含まれています。

以下の例では、T1 と T2 が 2 つのタイプで、R1 から R16 が SubType です。SubType は Type 全体で一意です。したがって、R1 は T1 のサブタイプであり、R1 をサブタイプとする他のタイプはありません。

Input
    List<RowType> list1 = new List<RowType>(){ T1, T2, RT3 }
    List<RowType> list2 = new List<RowType>(){ RT1, RT3, RT6, RT7, RT9 }

    where 
    RT1 -> Type = T1, SubType = R1
    RT3 -> Type = T3, SubType = R3
    RT6 -> Type = T1, SubType = R6
    RT7 -> Type = T2, SubType = R7
    RT9 -> Type = T4, SubType = R9

Expected Output
    0, 1, 2, 3  

Index 0 since T1 is Type for RT1
Index 2 since T1 is Type for RT6
Index 3 since T2 is Type for R7
Index 1 since RT3 matches RT3
4

1 に答える 1

1

最初に元のリストを繰り返し、各エントリをディクショナリに追加します。キーはリスト内の要素で、値はインデックスです。GetHashCodeで適切にオーバーライドする限り、RowTypeを使用できるはずですDictionary<RowType, int>。その後、2 番目のリストを繰り返し、ディクショナリ内の各項目を検索してインデックスを決定します。これにより O(n + m) が生成されますが、明らかにメモリ フットプリントが大きくなります。

于 2013-01-14T23:32:14.513 に答える