быстрый контейнер с переменным размером C++

Я делаю шахматный движок и ударил кирпичную стену с оптимизацией. После использования профилировщика я обнаружил, что генерация движения является самым большим фактором. Когда я подошел поближе, оказалось, что большая часть времени, генерирующего ходы, была потрачена на вызов std :: vector.push_back (move), когда я нашел ход.быстрый контейнер с переменным размером C++

Есть ли способ быстро создать контейнер C++ с динамическим размером? Это не может быть массив фиксированного размера, так как я не знаю заранее, сколько будет произведено ходов (хотя обычно их меньше 50).

Есть ли у кого-нибудь опыт в этом вопросе? При необходимости я напишу свой собственный контейнер, но я чувствую, что должен быть стандартный способ сделать это.

источник

2014-01-13 Lukas Schmit

Ответы должны привести вас в правильном направлении. Иногда проблема с профайлерами заключается в том, что вы видите только, какие методы чаще всего вызываются, а не почему, возможно, вы можете уменьшить количество push_backs в целом, прежде чем пытаться оптимизировать контейнер. Вы также можете посмотреть здесь, чтобы получить информацию о вставке и ее сложности: http: // www.cplusplus.com/reference/vector/vector/push_back/ – Excelcius

Насколько велик «переезд»? Является ли стоимость копирования в вектор? –

Движение действительно должно соответствовать 32 битам, хотя вы должны иметь 'class Move', который обертывает это в гораздо более приятном интерфейсе. Даже с этим интерфейсом 'Move :: Move (Move const &') 'все равно будет просто копией' long'. – MSalters

Позвонить std::vector::reserve() с соответствующими размерами до следующих push_back() звонков, чтобы избежать повторного выделения памяти снова и снова.

источник

2014-01-13 05:41:35 timrau

Не резервировал бы больше, чем мне нужно, в результате векторного результата, чтобы съесть много памяти? –

Да, вы должны торговать между временем выполнения, чтобы перераспределить память и дополнительное потребление памяти. Убедитесь, что вы не зарезервируете _much_ больше, чем вам нужно. Кроме того, после всех push_backs вы можете сжать дополнительную память с помощью [Shrink-to-fit idiom] (http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Shrink-to-fit). – timrau

О, так с C++ 11 я мог бы использовать shrink_to_fit(), как только закончил мой push_back()? –

Вы можете использовать std::vector и вызвать его метод reserve в соответствующих местах.

источник

2014-01-13 05:42:05

Векторный :: заповедник() помогает. Вы можете попытаться профилировать и увидеть распределение количества ходов и попытаться зарезервировать оптимальное количество заранее. Не беспокойтесь о потерях памяти, потому что, когда у вас есть 32 - 50 ходов, зарезервированная память может быть 64, и есть отходы в 14 - 32. Таким образом, резервировать память объемом 8 или даже 16 может не занимать гораздо больше памяти.
Нужно ли вам перемещаться по индексу? почему бы не использовать std :: list?
Или вы можете попробовать push_back shared_ptr для перемещения, а затем зарезервировать некоторое количество заранее, будет меньше отходов памяти.

источник

2014-01-13 06:00:55 user534498

Вы пробовали профилировать std::deque? Если у вас нет требования, чтобы объекты были распределены смежным образом, то это могло бы быть оптимальным решением. Он обеспечивает постоянную вставку и стирание времени спереди; обычно std::deque предпочтительнее, если вам нужно вставить или стереть на обоих концах последовательности.

Вы можете прочитать информацию в GotW 54.

источник

2014-01-13 06:06:39 legends2k

Я использую this method of profiling.

Меня не удивляет, что push_back - это большой таймер, и reserve должен исправить это.

Однако, если вы профиль снова, вы можете найти что-то другое, это большой таймер, например, звонки на new и delete для ваших move объектов.

Устраните это (пулом) и сделайте это снова. Теперь что-то еще будет большим.

Каждый раз, когда вы делаете это, вы получаете коэффициент ускорения, и эти факторы умножают на, пока вы не будете действительно довольны результатом.

источник

2014-01-13 15:06:08

быстрый контейнер с переменным размером C++

ответ

Смежные вопросы