0

次のような、ある程度クラスター効果のある配列があるとします。

1 2 3 7 8 12 13 16 20 21 22 23

この種のデータを数学的に表現するにはどうすればよいでしょうか? このような他の配列がある場合

1 2 10 11 20 21

これら2つの配列の交点は

1 2 20 21

この種の 2 つの配列の交点を計算するための完全に並列化されたアルゴリズムがある状況にあることに注意してください。数学の慣例でコストを分析したいと考えています。アルゴリズムは、短い配列のすべての要素を長い配列でバイナリ検索することです。

GPU 用のアルゴリズムを設計しましたが、これは非常に高速です。このようなクラスター効果のあるデータでは、アルゴリズムが高速であることがわかります。この種のデータでアルゴリズムを分析したいのですが、これを行う方法がわかりません。

ランダムなプロセスのようなものはありますか、それともコストの期待値を計算するのに役立つものはありますか?

4

2 に答える 2

0

完全に並列化されたアルゴリズムの意味はわかりませんが、配列がソートされているため、時間の複雑さ O(m + n) で順次アルゴリズムを実行できます。ここで、m と n は配列の長さです。

int i = 0, j = 0;
while (i < array1.length && j < array2.length) {
    if (array1[i] == array2[j]) {
        add array1[i] to the intersection list
        ++i;
        ++j;
    } else if (array1[i] < array2[j]) {
        ++i;
    } else {
        ++j;
    }
}

これは、配列に一意の値が含まれていることを前提としています。値が繰り返される可能性がある場合は、何が交差配列を構成するかについて、問題をより適切に定義する必要があります。

アルゴリズムは、一致が見つからない場合に単に i または j をインクリメントするのではなく、二分探索を行うことでおそらくかなり高速化できます。要素が見つからない場合に要素を挿入する場所を報告するバイナリ検索が必要になります。(失敗を報告するだけでは時間の無駄です。)

于 2012-05-25T04:11:09.270 に答える
0

配列を反復処理し、すべてのペア (0,1; 1,2; ...) の違いを見つけます。1 の数を数えて、n-1 で割ります。これにより、連続したペアの割合が得られます。原始的な指標です。

プリミティブ_メトリック: 

values = [1,2,3,4,5,8,9,10]  
values_length = 8  
consecutive = 0  
for i=0 to values_length - 1:  
    consecutive += ((values[i+1] - values[i]) == 1) ? 1 : 0
return consecutive/(values_length-1)
于 2012-05-25T05:13:40.403 に答える