如何为某些微积分密集型代码获得最快的迭代？

Question

上下文

我正在使用QLinkedList存储我写的一些类.
事实是我必须在这个列表上进行很多迭代.
很多我的意思是我编写的程序进行无限演算(好吧,你仍然可以手动停止它),我需要通过每次迭代的QLinkedList.

问题

问题不在于我是否在这个列表上进行了多次迭代.

这是我正在分析我的代码,我发现1/4的时间花在QLinkedList :: end()和QLinkedList :: begin()函数上.

示例代码

我的代码如下:

typedef QLinkedList<Particle*> ParticlesList;  // Particle is a custom class

ParticlesList* parts = // assign a QLinkedList

for (ParticlesList::const_iterator itp = parts->begin(); itp != parts->end(); ++itp)
{
    //make some calculus
}

就像我说的那样,这段代码经常被调用,它花了很多时间在parts-> begin()和parts-> end()上.

题

那么,问题是如何减少这个列表迭代所花费的时间？

可能的解决方案

这里有一些我想过的解决方案,请帮我选择最好的或者再提一个:)

• 使用经典的C数组://对不起这个错误

Particle** parts = // assing it something
for (int n = 0; n < LENGTH; n++)
{
    //access by index
    //make some calculus
}

这应该是快速的吗？

• 也许使用Java风格的迭代器？
• 也许用另一个容器？
• 阿斯姆？开玩笑......或者也许？

谢谢你的未来答案!

PS:我已经阅读了有关何时发布的stackoverflow帖子,所以不要担心;)

编辑:

该列表已修改

对不起,我想我忘记了最重要的,我会写完整个函数而不剥离:

typedef std::vector<Cell*> Neighbours;
typedef QLinkedList<Particle*> ParticlesList;

Neighbours neighbours = m_cell->getNeighbourhood();
Neighbours::const_iterator it;

for (it = neighbours.begin(); it != neighbours.end(); ++it) 
{
    ParticlesList* parts = (*it)->getParticles();
    for (ParticlesList::const_iterator itp = parts->begin(); itp != parts->end(); ++itp)
    {
        double d = distanceTo(*itp); // computes sqrt(x^2 + y^2)
        if(d>=0 && d<=m_maxForceRange)
        {
            particleIsClose(d, *itp); // just changes 
        }
    }
}

为了确保我完整,整个代码在循环中被调用^^.

所以是的,列表被修改,它在内循环中.所以没有办法预先计算它的开头和结尾.

而且,列表需要通过逐个插入在每个大的迭代(我的意思是在最顶层的循环中)构建.

调试模式

是的,我确实在调试模式下进行了分析.而且我认为这句话是明智的,因为代码在Release中的速度提高了2倍.列表的问题消失了.

感谢所有人的回答,并为此对不起^^

Answer 1

如果您在调试模式下进行性能分析,很多编译器都会禁用内联.begin()和end()时间很高可能不是"真实的".方法调用时间远远高于等效的内联操作.

我在完整代码中注意到的其他内容,你在内循环中做了一个sqrt.根据硬件架构,它们可能相当昂贵.我会考虑更换以下代码:

 double d = distanceTo(*itp); // computes sqrt(x^2 + y^2) 
 if(d >= 0 && d <= m_maxForceRange) 

有:

 double d = distanceToSquared(*itp); // computes x^2 + y^2
 if(d >= 0 && d <= m_maxForceRangeSquared)

我在代码中完成了这项工作,我正在进行碰撞检测,它有时会带来明显的改进.测试是等效的,并且节省了很多对sqrt的调用.与优化一样,测量以验证它是否提高了速度.