0

行の長さの降順で並べ替えられた文字列の大規模なテキストファイルがあります。すべてを文字列配列にロードし、それぞれに対してLevenshteinを実行し、グループUUIDを作成して、それを配列に入れたいと思います。したがって、2番目の配列はハッシュテーブルになります。ここで、キーは前の文字列のメモリアドレスであり、値はUUIDです。

最高のパフォーマンスを得るために、文字列を反復処理するときにポインタ演算を実行したいと思います。

レーベンシュタイン距離を何十億回も繰り返した後、グループのUUID、コロン、および元のテキストファイルの行だけの内容の別のテキストファイルを入力したいと思います。

私はウィキブックスのレーベンシュタインアルゴリズムを持っています：

template<class T> unsigned int levenshtein_distance(const T &s1, const T & s2) {
    const size_t len1 = s1.size(), len2 = s2.size();
    vector<unsigned int> col(len2+1), prevCol(len2+1);

    for (unsigned int i = 0; i < prevCol.size(); i++)
            prevCol[i] = i;
    for (unsigned int i = 0; i < len1; i++) {
            col[0] = i+1;
            for (unsigned int j = 0; j < len2; j++)
                    col[j+1] = min( min( 1 + col[j], 1 + prevCol[1 + j]),
                                                            prevCol[j] + (s1[i]==s2[j] ? 0 : 1) );
            col.swap(prevCol);
    }
    return prevCol[len2];
}

私はいくつかのC++、いくつかのC、Obj-Cのロードを実行しました。私はWindows7を使用しています。これを行うことをどのように推奨しますか？どんな種類の文字列配列？提供された関数で使用されるテキストファイルからテキスト文字列を変換するにはどうすればよいですか？

文字列がC++で私を混乱させるので、私は基本的にできるだけ多くのヒントを探しています。ああ、C ++もそうです！

ありがとう

4

1 に答える 1

0

完全なアクセス時間については、メモリへの完全な読み取りを打ち負かしてから、シングルパスでインデックスを作成し、ポインターリストを作成し、遭遇する各 CR/LF でヌルターミネーターをハード書き込みするのは難しいでしょう。行番号は、これらすべてのポインターを格納しているコンテナーへのインデックスになります。そのために、std::deque<>.

ブースト:: 連中はこれをさらに進める可能性が高いですが、すばやくアクセスするには、メモリの大きなスタックとそれにインデックスを付ける多数のポインターに勝るものはありません。もちろん、この全体は、メモリに収まることを前提としています。それができない場合、これはかなり複雑になりますが、できる場合 (そしていつでもできると想定できる場合) は、malloc/walk-and-terminate/push-ptr-into-deque はかなりきれいに見えます。本当に煙にするために、各文字列の長さをポインターで保存するのでstd::deque<>、struct { char* ptr; size_t len; }. そうすることで、大量の不要な strlen() などを排除できます。また、何かを null で終了する必要もなくなります。

于 2012-09-15T18:41:04.560 に答える