Необходимо ускорить код C ++, включающий мультииндекс и поиск в Unonordered_multimap

StackOverflow https://stackoverflow.com/questions/4808957

Вопрос

Я ищу стратегии для ускорения модели на основе агента, основанной на объектах класса Host, указатели, которые хранятся в многоиндексном контейнере Boost. Я использовал акулу, чтобы определить, что подавляющее большинство времени потребляется функцией calcSI():

enter image description here

Функция calcSI() должен вычислить для каждого экземпляра класса Host определенные вероятности, которые зависят от атрибутов других случаев класса Host. Анкет (Существует приблизительно 10 000-50 000 случаев Host, и эти расчеты выполняются для каждого хозяина примерно в 25 600 раз.)

Если я правильно интерпретирую профиль, большую часть времени, проведенного в calcSI() идет к Host::isInfectedZ(int), что просто подсчитывает случаи чего -то в повышении безупорядки InfectionMap:

struct Infection {
public:
  explicit Infection( double it, double rt ) : infT( it ), recT( rt ) {}
  double infT;
  double recT;
};
typedef boost::unordered_multimap< int, Infection > InfectionMap;

Все члены Host содержать InfectionMap carriage, а также Host::isInfectedZ(int) просто считает количество Infections связанный с конкретным int ключ:

int Host::isInfectedZ( int z ) const {
  return carriage.count( z );
}

  1. У меня проблемы с поиском информации о том, насколько дорого count Функция предназначена для неупорядоченных мультимапа Boost. Должен ли я увеличить накладные расходы, добавив к Host отдельный двухмерный массив для отслеживания количества экземпляров каждого ключа (т.е. Infections связан с каждым int)?

  2. Мне интересно, будет ли более крупный структурный пересмотр мультииндекса Boost Multi-Index, например, устранение одного или двух менее необходимых индексов составных ключей, более полезным. Фоновое обслуживание мультииндекса не появляется в Profiler, что (возможно, глупо) заставляет меня беспокоиться, что это может быть большой. У меня есть 8 индексов в мультииндексе, большинство из которых упорядочено_non_unique.

  3. Есть ли другие вещи, с которыми я должен быть обеспокоен, которые могут не появиться в профилировщике, или я упускаю большой результат от профилятора?

Параллелизация и многопоточное calcSI() к сожалению, не варианты.

Обновлять: Может быть полезно знать, что InfectionMap carriage Редко имеет более 10 пар и обычно имеет <5.

Обновление 2: Я попробовал стратегию, предложенную в #1 выше, давая каждый Host массив int carriageSummary[ INIT_NUM_STYPES ], что индексируется возможными значениями z (Для большинства симуляций существует <10 возможных значений). Значение каждого входа отслеживает изменения, внесенные в carriage. Анкет А Host::isInfectedZ( int z ) Функция сейчас читается:

int Host::isInfectedZ( int z ) const {
  //return carriage.count( z );
  return carriageSummary[ z ];
}
И время, посвященное этой функции появляется Чтобы значительно упасть-я сейчас не могу сделать точное сравнение:enter image description here Очевидно, что использование массива является громоздким, но в порядке для небольших диапазонов z. Анкет Будет ли какой -то другой контейнер (т.е. не безупорядая) будет более эффективным для больших диапазонов?

Хотелось бы также с удовольствием с изменением мультииндекса.

Это было полезно?

Решение

Как вы предложили в #1, попробуйте поддерживать массив подсчета кареток рядом с хостом :: Carriage Unoromeded_multimap и сохраните их обоих «синхронизированными». Ваш хост :: isInfectedz затем использовал бы (надеюсь) более быстрый массив подсчета перевозки:

int Host::isInfectedZ( int z ) const {
  return carriageCount[ z ];
}

Если диапазон целых чисел, которые можно передать в ISINFECTICE, велик, то используйте ассоциативный массив для вашего количества перевозки.

Вы можете использовать Std :: Map или Boost :: Неупопорядочен для ассоциативного массива. Для поиска первая имеет логарифмическую временную сложность, а второй имеет постоянную временную сложность. Но так как этот ассоциативный массив, как правило, был бы очень маленьким, карта Std :: на самом деле может быть быстрее. Std :: Map также может занять меньше места накладных расходов. Попробуйте оба и запустите свой профилировщик, чтобы увидеть. Моя ставка на std :: map. :-)

РЕДАКТИРОВАТЬ:

Увидев ваш ответ на мой комментарий, я бы посоветовал использовать обычный массив фиксированного размера для количества перевозки. Забудьте о ассоциативном массиве.

Edit2:

Вы можете выкатиться

typedef boost::unordered_multimap< int, Infection > InfectionMap;

и раскажите свой собственный рукописный класс InfectionMap, поскольку вы имеете дело с такими небольшими индексами.

Ответ на обновление № 2:

Рад видеть, что вы добились улучшения. Я сомневаюсь, что вы найдете контейнер, который «менее громоздкий», чем фиксированный массив, скажем, 16 целых чисел. Контейнеры STL и Boost выделяют память в кусочках и в конечном итоге будут столь же большими, как ваш массив фиксированного размера, даже если у них мало элементов.

Вы можете быть заинтересованы в Boost :: Array, который завершает stl-подобный интерфейс вокруг фиксированного массива в стиле C. Это облегчит «смену» вашего массива фиксированного размера для STD :: Vector или Std :: Map.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top