3

高速な MTF ( http://en.wikipedia.org/wiki/Move-to-front_transform ) の場合、文字を配列内から配列の前に移動する高速バージョンが必要です。

char mtfSymbol[256], front;
char i;

for(;;) { \\ a very big loop 
    ... 
    i=get_i(); \\ i is in 0..256 but more likely to be smaller.

    front=mtfSymbol[i];
    memmove(mtfSymbol+1, mtfSymbol, i);
    mtfSymbol[0]=front;
}

cachegrind が示しているように、memmove では多くの分岐予測ミスが発生しています。

他のバージョンのコード (最初の例の memmove ではなく、これ)

do
{
   mtfSymbol[i] = mtfSymbol[i-1];
} while ( --i );

多くのバイト読み取り/書き込み、条件付き分岐、分岐予測ミスがあります

i は、「適切な」入力に使用される MTF であるため、それほど大きくはありません。BWT (Burrows–Wheeler 変換) 後のテキスト ファイルです。

コンパイラはGCCです。

4

2 に答える 2

0

必要以上に大きなバッファを事前に割り当て、最初の配列を中間のどこかに（またはそのように拡張する必要がない場合は最後に）配置する場合は、追加できますすべての要素を移動するのではなく、配列の先頭のアドレスを変更することによって (制限まで) アイテムを移動します。

明らかに、移動した距離を追跡する必要があるため、既存の割り当ての開始から外れてしまった場合は再割り当てできますが、これはすべての配列エントリを移動するよりも高速です。

于 2010-09-14T16:25:37.063 に答える
0

配列ではなく専用のデータ構造を使用して、順方向変換を高速化することもできます。配列要素の移動を完全に回避するために、リンクされたリストのリストを使用して高速な実装を構築できます。

http://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/MTFT.javaを参照してください。

逆変換の場合、配列はリンクされたリストと同じくらい高速であることがわかります。

于 2013-05-19T06:19:58.687 に答える