0

並べ替えられた要素の 2 つのセットがあり、後で並列化できるようにそれらをマージしたいと考えています。最大関数と、バイナリ検索を使用してランクを見つけ、特定の値のインデックスを計算する並列化可能なマージの最初のバージョンを使用するため、データの依存関係を持つ単純なマージ実装があります。

getRank 関数は、指定された針以下の要素の数を返します。

#define ATYPE int

int getRank(ATYPE needle, ATYPE *haystack, int size) {
    int low = 0, mid;
    int high = size - 1;
    int cmp;
    ATYPE midVal;

    while (low <= high) {
        mid = ((unsigned int) (low + high)) >> 1;
        midVal = haystack[mid];
        cmp = midVal - needle;

        if (cmp < 0) {
            low = mid + 1;
        } else if (cmp > 0) {
            high = mid - 1;
        } else {
            return mid; // key found
        }
    }

    return low; // key not found
}

マージ アルゴリズムは、2 つの並べ替えられたセット a、b で動作し、結果を c に格納します。

void simpleMerge(ATYPE *a, int n, ATYPE *b, int m, ATYPE *c) {
    int i, l = 0, r = 0;

    for (i = 0; i < n + m; i++) {
        if (l < n && (r == m || max(a[l], b[r]) == b[r])) {
            c[i] = a[l];
            l++;
        } else {
            c[i] = b[r];
            r++;
        }
    }
}

void merge(ATYPE *a, int n, ATYPE *b, int m, ATYPE *c) {
    int i;
    for (i = 0; i < n; i++) {
        c[i + getRank(a[i], b, m)] = a[i];
    }
    for (i = 0; i < m; i++) {
        c[i + getRank(b[i], a, n)] = b[i];
    }
}

多くの要素があり、並列化できる場合、マージ操作は非常に遅くなりますが、simpleMerge は並列化できなくても常に高速です。

だから私の質問は、並列マージのためのより良いアプローチを知っていますか？

4

2 に答える 2

0

マージ関数で使用されるアルゴリズムは、漸近解析が最適です。複雑さはO（n + m）です。I / OはO（n + m）を取るため、より良いアルゴリズムを見つけることはできません。

于 2013-01-12T15:54:46.867 に答える
0

機能の複雑さsimpleMerge:

O(n + m)

機能の複雑さmerge:

O(n*logm + m*logn)

これについてあまり考えずに、それを並列化するための私の提案は、getRank 関数に似たものを使用して、そこから単純なマージを使用して、各関数の中央付近にある単一の値を見つけることです。それは可能ですO(n + m + log m + log n) = O(n + m)（たとえ、中間付近の値を見つけるために、いくつかの、しかし一定量のルックアップを行ったとしても）。

于 2013-01-12T16:04:12.803 に答える