1

並列ブルート フォース部分文字列検索アルゴリズムを実装しようとしています。各スレッドは開始インデックスと終了インデックスを取得します。4 つのスレッドで実行しているので、各スレッドは作業の 4 分の 1 を実行します。

関数を 1 回実行すると、すべて問題なく動作します (4 つのスレッドで動作します) が、関数は void 型であるため、結果 (部分文字列が大きな文字列内にあるインデックス) をグローバル変数 ' に格納します。 ans'.

int ans = -1;

void bruteForce(string mainString, string subString)
{
    int tid, nthreads;
    #pragma omp parallel private (tid) shared (nthreads, ans)
    {
        tid = omp_get_thread_num();
        nthreads = omp_get_num_threads();
        int j = 0;
        int start = tid * (mainString.size() / nthreads);
        int end = start + mainString.size() / nthreads;

        for(int i = start; i < end; i++)
        {
            if(ans == -1)
            {
                while(j < subString.size())
                {
                    if(mainString[i + j] != subString[j]) break;
                    if(j == subString.size() - 1)
                    {
                        #pragma omp critical
                        {
                            #pragma omp flush
                            ans = i;
                        }
                    }
                    j++;
                }
                j = 0;
            }
        }
    }
}

私がやりたいことは、関数が完了した後または開始する前に「ans」を-1にリセットすることですが、それをしようとすると、メモリマップとバックトレースとともにこのエラーが発生します。

double free or corruption (out): 0xb5b00468 ***

以下の for ループ ショー内で「ans」を -1 に変更できない理由はありますか?

    start = get_timestamp();
    for(int x = 0; x < N; x++)
    {
        show_percent(x, N);
        bruteForce(STRING, WORD);
    }
    end = get_timestamp();
4

2 に答える 2

2

これは ans の変更とは関係ありません。brutForce()の while ループで(i+j)に制限を設ける必要があります。

mainString = "THIS" および subString="XXX" とします。したがって、各スレッドは取得します

T | T | ひ | 私 | 私 | S

最後のスレッドでは、start=3、end=4 です。また、subString.size() = 3;

そのため while ループでは、mainString[i+j] にアクセスしています。ここで、j = 0->2 ==> (i+j) = 3->5 です。

于 2013-04-03T08:08:08.920 に答える