0

我有两组已排序的元素，并希望以某种方式将它们合并在一起，以便稍后将其并行化。我有一个简单的合并实现，它具有数据依赖性，因为它使用最大函数和可并行化合并的第一个版本，它使用二进制搜索来查找排名并计算给定值的索引。

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
}

合并算法对两个排序集 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 回答