3

对于快速 MTF（http://en.wikipedia.org/wiki/Move-to-front_transform），我需要更快的版本将 char 从数组内部移动到它的前面：

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

您还可以使用专用数据结构而不是数组来加速正向变换。可以使用链表列表构建快速实现，以避免数组元素完全移动。

请参阅http://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/MTFT.java

对于逆变换，事实证明数组与链表一样快。

于 2013-05-19T06:19:58.687 回答
0

如果您预先分配的缓冲区比您需要的大，并将您的初始数组放在中间的某个位置（或者在最后，如果您永远不必以这种方式扩展它），那么您可以追加通过更改数组的起始地址而不是移动所有元素来获取项目（达到限制）。

您显然需要跟踪您已经移动了多远，因此如果您确实脱离了现有分配的开始，您可以重新分配，但这仍然应该比移动所有数组条目更快。

于 2010-09-14T16:25:37.063 回答