1

いくつかの整数の短いソート配列があり、定義済みの定数以上の交差を見つける必要があります。ここにコードがあり、それは私がやりたいことを示しており、言葉で説明できます。問題はSPEEDです。私のコードは非常に遅く動作しています。2000要素の配列（私の遅いマシンでは）で約15秒かかります。もちろん、独自の交差メソッドを実装してコードを並列化することはできますが、改善は非常に限られています。実行時間は N^2 程度に増加し、すでに 500k 配列の場合、非常に長い時間がかかります。では、パフォーマンスを向上させるためにアルゴリズムを書き直すにはどうすればよいでしょうか? 私はc#言語に限定されていません.おそらくCPUまたはGPUには、そのような仕事のための特別な指示があります.

Example:

Input:
1,3,7,8
2,3,8,10
3,10,11,12,13,14

minSupport = 1

Output:

1 and 2: 2, 8
1 and 3: 3
2 and 3: 3, 10

    var minSupport = 2;
    var random = new Random(DateTime.Now.Millisecond);

    // Numbers is each array are unique
    var sortedArrays = Enumerable.Range(0,2000)
    .Select(x => Enumerable.Range(0,30).Select(t => random.Next(1000)).Distinct()
    .ToList()).ToList();
    var result = new List<int[]>();
    var resultIntersection = new List<List<int>>();

    foreach (var array in sortedArrays)
    {
        array.Sort();
    }

    var sw = Stopwatch.StartNew();

    //****MAIN PART*****//

    for (int i = 0; i < sortedArrays.Count-1; i++)
    {
        for (int j = i+1; j < sortedArrays.Count; j++)
        {
            var intersect = sortedArrays[i].Intersect(sortedArrays[j]).ToList();
            if(intersect.Count()>=minSupport)
            {
                result.Add( new []{i,j});
                resultIntersection.Add(intersect);
            }
        }
    }

    //*****************//

    sw.Stop();

    Console.WriteLine(sw.Elapsed);

編集：

2000 要素の古いアルゴリズムでは 15 秒に対して約 9 秒かかります。うーん...もちろん、十分な速さではありません。

//****MAIN PART*****//

    // This number(max value which array can contains) is known
    var maxValue = 1000;

    var reverseIndexDict = new Dictionary<int,List<int>>();

    for (int i = 0; i < maxValue; i++)
    {
        reverseIndexDict[i] = new List<int>();
    }

    for (int i = 0; i < sortedArrays.Count; i++)
    {
        for (int j = 0; j < sortedArrays[i].Count; j++)
        {
            reverseIndexDict[sortedArrays[i][j]].Add(i);
        }
    }

    var tempArr = new List<int>();
    for (int i = 0; i < sortedArrays.Count; i++)
    {
        tempArr.Clear();
        for (int j = 0; j < sortedArrays[i].Count; j++)
        {
            tempArr.AddRange(reverseIndexDict[j]);
        }

        result.AddRange(tempArr.GroupBy(x => x).Where(x => x.Count()>=minSupport).Select(x => new[]{i,x.Key}).ToList());

    }

    result = result.Where(x => x[0]!=x[1]).ToList();


    for (int i = 0; i < result.Count; i++)
    {
        resultIntersection.Add(sortedArrays[result[i][0]].Intersect(sortedArrays[result[i][1]]).ToList());
    }



    //*****************//

編集：

若干改善。

//****MAIN PART*****//

    // This number(max value which array can contains) is known
    var maxValue = 1000;

    var reverseIndexDict = new List<int>[maxValue];

    for (int i = 0; i < maxValue; i++)
    {
        reverseIndexDict[i] = new List<int>();
    }

    for (int i = 0; i < sortedArrays.Count; i++)
    {
        for (int j = 0; j < sortedArrays[i].Count; j++)
        {
            reverseIndexDict[sortedArrays[i][j]].Add(i);
        }
    }



    for (int i = 0; i < sortedArrays.Count; i++)
    {
        var tempArr = new Dictionary<int, List<int>>();

        for (int j = 0; j < sortedArrays[i].Count; j++)
        {
            var sortedArraysij = sortedArrays[i][j];


            for (int k = 0; k < reverseIndexDict[sortedArraysij].Count; k++)
            {
                if(!tempArr.ContainsKey(reverseIndexDict[sortedArraysij][k]))
                {
                    tempArr[reverseIndexDict[sortedArraysij][k]] = new[]{sortedArraysij}.ToList();
                }
                else
                {
                   tempArr[reverseIndexDict[sortedArraysij][k]].Add(sortedArrays[i][j]);
                }

            }
        }


        for (int j = 0; j < reverseIndexDict.Length; j++)
        {
            if(reverseIndexDict[j].Count>=minSupport)
            {
                result.Add(new[]{i,j});
                resultIntersection.Add(reverseIndexDict[j]);
            }
        }

    }

    // and here we are filtering collections

    //*****************//
4

1 に答える 1

0

2つの解決策があります：

  1. 3つのソートされた配列があり、それらの間の交差を見つける必要があると仮定します。最初の配列をトラバースし、最初の配列の要素について2つの配列の残りの部分でバイナリ検索を実行します。2つのリストのそれぞれの二分探索で正の値が得られた場合は、交差のカウンターをインクリメントします。

    result = List
for element in Array1:
    status1 = binarySearch(element, Array2)
    status2 = binarySearch(element, Array2)
    status = status & status
    if status == True:
        count++
        if count == MAX_INTERSECTION:
            result.append(element)
            break

    時間計算量：N * M * Log（N）、
    ここで、
    N=配列内の要素の
    数M=配列の数

  2. このソリューションは、配列内の数値が正の整数である場合にのみ機能します。ソートされたすべての配列の全要素から最大数と最小数を計算します。並べ替えられているので、指定された並べ替えられた配列の開始要素と終了要素を調査することで判断できます。最大数を最大、最小数を最小とします。サイズmax--minの配列を作成し、ゼロで埋めます。3つの配列があるとします。ここで、最初の配列のトラバースを開始し、それぞれのインデックスに移動して、前に作成した配列の値をインクリメントします。以下に述べるように：

    element is 5 in Array 1, the New_array[5]+=1

    ソートされた3つのリストすべてをトラバースし、上記の操作を実行します。最後に、new_arrayをトラバースし、3に等しい値を探します。これらのインデックスは、交差の結果です。

    時間計算量：O（N）+ O（N）+ .. = O（N）
    空間計算量：O（maximum_element-minimum_element）
    ここで、
    N=配列内の要素の数。

于 2012-06-05T09:23:32.953 に答える