Производительность статических массивов с переменным размером при запуске
Я написал программу для сотовых автоматов, которая хранит данные в матрице (массиве массивов). Для матрицы 300 * 200 я могу достичь 60 или более итераций в секунду, используя статическое выделение памяти (например, std::array).
Я хотел бы создавать матрицы разных размеров без перекомпиляции программы каждый раз, то есть пользователь вводит размер, а затем начинается моделирование для этого размера матрицы. Однако, если я использую динамическое выделение памяти, (например, std::vector), имитация падает до ~ 2 итераций в секунду. Как я могу решить эту проблему? Один из вариантов, к которому я прибегнул, — это предварительно выделить статический массив, больший, чем я ожидаю, что пользователь выберет (например, 2000 * 2000), но это кажется расточительным и все же ограничивает выбор пользователя в некоторой степени.
Мне интересно, могу ли я
а) выделить память один раз, а потом как-то «заморозить» ее для обычной производительности статического массива?
б) или выполнять более эффективные операции на std::vector? Для справки я только выполняю matrix[x][y] == 1 а также matrix[x][y] = 1 операции над матрицей.
В соответствии с этот вопрос / ответ, нет никакой разницы в производительности между std::vector или используя указатели.
РЕДАКТИРОВАТЬ:
Я переписал матрицу, в соответствии с предложением UmNyobe, чтобы он представлял собой единый массив, доступ к которому осуществляется через matrix[y*size_x + x], Используя динамическое распределение памяти (измеряется один раз при запуске), я удваиваю производительность до 5 итераций в секунду.
Согласно комментарию PaulMcKenzie, я скомпилировал сборку релиза и получил требуемую производительность (60 и более итераций в секунду). Тем не менее, это основа для большего, поэтому я все еще хочу количественно оценить преимущества одного метода над другим, поэтому я использовал std::chrono::high_resolution_clock время каждой итерации и обнаружил, что разница в производительности между динамическими и статическими массивами (после использования матричного представления одного массива) должна быть в пределах погрешности (450 ~ 600 микросекунд на итерацию).
Однако производительность во время отладки представляет собой небольшую проблему, поэтому я думаю, что я оставлю оба и переключусь на статический массив при отладке.
Решение
Для справки я только выполняю
matrix[x][y]
- Красный флаг! Ты используешь
vector<vector<int>>для вашей матрицы
представление? Это ошибка, так как строки вашей матрицы будут далеко
отдельно в памяти. Вы должны использовать один вектор размераrows x cols
и использоватьmatrix[y * row + x] - Кроме того, вы должны следовать подходу, где вы индексируете сначала по строкам, а затем по столбцам, т.е.
matrix[y][x]скорее, чемmatrix[x][y], Ваш алгоритм также должен обрабатываться таким же образом. Это связано с тем, что сmatrix[y][x](x, y) и (x + 1, y) — один блок памяти друг от друга, в то время как с любыми другими элементами механизма(x,y)а также(x + 1, y),(x, y + 1)гораздо дальше.
Даже если происходит снижение производительности от std :: array до std :: vector (так как массив может иметь свои элементы в стеке, что быстрее), приличный алгоритм будет работать с одинаковой величиной, используя обе коллекции.
Другие решения
Других решений пока нет …