Как я могу получить самую быструю итерацию для кода с интенсивным исчислением?

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 
        }
    }
}

И чтобы убедиться, что я полон, весь код вызывается в цикле ^^.

Так что да, список изменен и находится во внутреннем цикле. Таким образом, нет никакого способа предварительно вычислить начало и конец этого.

И, кроме того, список должен составляться на каждой большой итерации (я имею в виду в самом верхнем цикле), вставляя одну за другой.

Режим отладки

Да, действительно, я профилировал в режиме отладки. И я думаю, что это замечание было разумным, потому что в выпуске код работал в 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.Как всегда с оптимизацией, измерьте, чтобы проверить, улучшает ли это скорость.

Answer 2

Предварительные вычисления конечного итератора помогут, если ваш компилятор недостаточно умен, чтобы понять, что он const, и, следовательно, вычисляет его каждый раз в цикле.Вы можете сделать это, как показано ниже:

const ParticlesList::const_iterator itp_end = parts->end();

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

Я не могу понять, почему parts->begin(); занимает так много времени, его следует использовать только один раз.Однако, если этот цикл находится внутри другого цикла, вы можете сделать что-то вроде этого:

const ParticlesList::const_iterator itp_begin = parts->begin();
const ParticlesList::const_iterator itp_end = parts->end();

for (...)
{
  for (ParticlesList::const_iterator itp = itp_begin; itp != itp_end; ++itp)
  {
      //make some calculus
  }
}

Но я не могу себе представить, что это будет иметь слишком большое значение (если ваш внутренний список не очень короткий), ноне должно причинить большого вреда.

С другой стороны, связанный список, возможно, не самая быстрая структура данных для ваших целей.Связанные списки наиболее полезны, когда вам часто нужно вставить элементы в середину списка.Если список составлен, а затем исправлен, вам, вероятно, лучше использовать std::vector.std::vector также может быть лучше, даже если вам иногда нужно только добавлять / удалять элементы с конца (не с начала или по середине).Если вам нужно добавить / удалить начало / конец (но не середину), рассмотрите std::deque.

Answer 3

Контейнеры Qt совместимы с алгоритмами STL, такими как std::for_each.

Попробуйте что-то вроде этого:

std::for_each( parts->begin(), parts->end(), MyParticleCalculus );

, где MyParticleCalculus - функтор, содержащий ваше исчисление.

Qt также имеет свой собственный foreach, но, по-видимому, это просто макрос для скрытия итераторов, поэтому он, вероятно, не даст вам никакого выигрыша в производительности.

(Правка: я рекомендую std::for_each в соответствии с рекомендацией Скотта Мейера в «Эффективном STL»: «Предпочитать вызовы алгоритма рукописным циклам.» )

Answer 4

Если вам абсолютно необходима грубая скорость, вы должны измерить каждый возможный выбор и сохранить самый быстрый.

Похоже, список остается неизменным, пока вы итерируете его. Я бы попытался сохранить конец списка в локальной переменной.

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

ParticlesList* parts = // assign a QLinkedList
ParticlesList::const_iterator end = parts->end();

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