問題タブ [lcs]

openMP を使用して、 Longest Common Subsequenceアルゴリズムの並列バージョンを作成しています。

順次バージョンは次のとおりです (正しく動作します)。

重要な部分はスコア マトリックスを埋めることであり、これは私が主に並列化しようとしている部分です。

それを行う 1 つの方法 (私が選んだ方法) は、逆対角線で行列を埋めて、左、上、左上の依存関係が常に満たされるようにすることです。簡単に言うと、対角線 (3 番目のループ、以下の変数i )を追跡し、スレッドがその対角線を並行して埋めます。この目的のために、私はこのコードを書きました：

最初の 2 つのループ (最初の行と列) は正しく機能し、スレッドはバランスの取れた方法でセルを埋めます。

マトリックスを（斜めに）埋めようとすると、何もうまくいきません。デバッグしてみたのですが、どうやらスレッドが勝手に動いて書き込んでいるようです。

最初の 2 つのループではまったく問題がなかったので、何が問題なのかわかりません。

何か案が？

PSマトリックスに斜めにアクセスすることは非常にキャッシュにやさしくなく、スレッドのバランスが崩れる可能性があることは知っていますが、今ではそれが機能するだけで済みます。

PS #2 役に立つかどうかはわかりませんが、私の CPU には最大 8 つのスレッドがあります。

使用によって与えられた 2 つのテキストの最長共通部分列の長さを取得するために、次のコードを記述しましたC#が、大きな文字列では機能しません。手伝っていただけませんか。私は本当に混乱しています。

2 つのシーケンス/文字列の lcs を見つける方法は知っていますが、lcs は、サブシーケンスが連続している必要があるという制限を課していません。私は次のようにそれを試しました

wherelongest_stringは配列内の最長の文字列を返し、s[1:]最初の文字から始まる s のスライスを意味します。

サーバーのハードウェア仕様についてはわかりませんが、これをjavascriptのブラウザー内とgolangの両方で実行しました。リモートサーバーでは、lccsへの各呼び出しを独自のゴルーチンに配置しました。これらのルーチンの並列化。

どちらの場合も、私のニーズには遅すぎました。これをスピードアップする方法はありますか？

必要に応じて、動的プログラミングO(m * n)、接尾辞ツリーO(m + n)、接尾辞配列O(nlog^2 n)を使用して、最長共通部分文字列を計算していました。最近、 O(n)で実行されるSuffix Automatonを学びました。これは非常に印象的です。

最長共通部分文字列の長さを簡単に計算できるコードを書くことができます。例えば：

そして、これはコードです：

しかし今、長さではなく、最長の共通部分文字列自体を出力する必要があります。しかし、コードを変更することはできません:(このコードを変更して、最も長い共通部分文字列を出力するにはどうすればよいですか?

http://www.iaeng.org/publication/WCE2010/WCE2010_pp499-504.pdfで説明されている最長共通部分列問題の並列アルゴリズムを実装しようとしています。

しかし、4 ページの式 6 の変数 C に問題があります。

この論文では、3 ページの最後で C を次のように言及しています。

C as C[1 : l] を有限のアルファベットとする

ABCDEFこれが何を意味するのかはわかりませABQXYEFんABCDEFQXY。しかし、私の 2 つの文字列がオブジェクトのリストである場合 (例の一致テストは ですobj1.Name = obj2.Name)、私の C はここにあるでしょうか? 2つの配列の単なるユニオンですか？

の繰り返しlcsは次のとおりです。

それがなぜなのか教えていただけますi-1かj-1？なぜL[i,j] = L[i-1,j-1]正しくないのですか？