我正在做一个关于2D装箱算法的研究。我问过similar question关于PHP性能的问题--打包起来太慢了--现在代码被转换成了C++。
它仍然很慢。因此,我的程序所做的就是分配动态内存块,并用字符'o‘填充它们
char* bin;
bin = new (nothrow) char[area];
if (bin == 0) {
cout << "Error: " << area << " bytes could not be allocated";
return false;
}
for (int i=0; i<area; i++) {
bin[i]='o';
}(对于我的数据集,它们的大小在1kb到30kb之间)
然后,程序检查当前内存块中“x”字符的不同组合。
void place(char* bin, int* best, int width)
{
for (int i=best[0]; i<best[0]+best[1]; i++)
for (int j=best[2]; j<best[2]+best[3]; j++)
bin[i*width+j] = 'x';
}其中一个检查非重叠的函数在运行时会被调用数百万次。
bool fits(char* bin, int* pos, int width)
{
for (int i=pos[0]; i<pos[0]+pos[1]; i++)
for (int j=pos[2]; j<pos[2]+pos[3]; j++)
if (bin[i*width+j] == 'x')
return false;
return true;
}所有其他的东西只需要运行时间的百分之一,所以我需要让这两个人(适合和放置)更快。谁是罪魁祸首?
因为我只有两个选项'x‘和'o',所以我可以尝试只使用一个位,而不是char接受的整个字节。但我更关心的是速度,你认为它会让事情变得更快吗?
谢谢!
更新:我按照MSalters的建议,将int* pos替换为rect pos (best也是如此)。起初我看到了改进,但我用更大的数据集测试了更多,它似乎回到了正常的运行时。我将尝试其他建议的技术,并将与您保持联系。
更新:使用memset和memchr的速度提高了两倍。将'x‘和'o’替换为'\1‘和'\0’没有任何改进。__restrict也帮不上忙。总体而言,我现在对程序的性能感到满意,因为我还对算法本身进行了一些改进。我还没有尝试使用位图并使用-02 (-03)进行编译...再次感谢大家。
发布于 2011-02-12 18:46:44
如果你的基本类型有2个值,我会首先尝试使用bool。然后编译器知道你有两个值,也许能更好地优化一些东西。在可能情况下(例如,fits( bool const*,...)的参数)从添加常量中去掉。
https://stackoverflow.com/questions/4965817
复制相似问题