Как оптимизировать мой код?

Question

[Uncle_Savva]

Как оптимизировать этот код? Эта программа является симуляцией броуновского движения.

#include <iostream>
#include <vector>
#include <string>
#include <SFML/Graphics.hpp>
#include <cmath>

using namespace std;
using namespace sf;


int WIDTH = 1920;
int HEIGHT = 1080;

tuple<int> YELLOW = (255, 255, 0);
tuple<int> GREY = (50, 50, 50);

int mSize = 5;
int moveArr[2] { -1, 1 };

class Particle {
public:
	int x;
	int y;
	int speedX;
	int speedY;
	int size = size;
};

vector<Particle> notStayArr;
vector<Particle> stayArr;

int go() {
	for (int i = notStayArr.size() - 1; i >= 0; i--) {
		for (int j = stayArr.size() - 1; j >= 0; j--) {
			if (sqrt(pow(notStayArr[i].x - stayArr[j].x, 2) + pow(notStayArr[i].y - stayArr[j].y, 2)) <= notStayArr[i].size + stayArr[j].size) {
				stayArr.push_back(notStayArr[i]);
				notStayArr.erase(notStayArr.begin() + i);
				break;
			}
		}
	}

	return 0;
}

int main() {
	srand(10);
	for (int u = 0; u <= 6000; u++) {
		Particle newObj = { rand() % WIDTH, rand() % HEIGHT, 0, 0, mSize };
		notStayArr.push_back(newObj);
	}

	Particle stayParticle = {WIDTH/2, HEIGHT/2, 0, 0, mSize};
	stayArr.push_back(stayParticle);

	RenderWindow window(VideoMode(WIDTH, HEIGHT), "SFML Works!");
	while (window.isOpen())
	{
		window.clear(Color(255, 255, 255, 0));

		go();
		// Events
		Event event;
		while (window.pollEvent(event))
		{
			if (event.type == Event::Closed)
				window.close();
		}

		for (int m = 0; m < notStayArr.size(); m++) {
			notStayArr[m].x += moveArr[rand()%2];
			notStayArr[m].y += moveArr[rand()%2];
			
			CircleShape circle(mSize);

			circle.setFillColor(Color(200, 200, 200));
			circle.move(notStayArr[m].x, notStayArr[m].y);
			window.draw(circle);

		}

		for (int m = 0; m < stayArr.size(); m++) {
			CircleShape circle(mSize);

			circle.setFillColor(Color(90, 90, 90));
			circle.move(stayArr[m].x, stayArr[m].y);
			window.draw(circle);
		}
		cout << stayArr.size() << endl;
		window.display();
	}
	return 0;
}

Comments

[Василий Банников]

А где возникает проблема с производительностью, что приходится оптимизировать?

[Uncle_Savva]

Василий Банников, замерял частоту кадров - 5 fps

[Uncle_Savva]

Считается все быстро, но отрисовка подводит.
Думаю, это из-за этой части:

for (int m = 0; m < notStayArr.size(); m++) {
			notStayArr[m].x += moveArr[rand()%2];
			notStayArr[m].y += moveArr[rand()%2];
			
			CircleShape circle(mSize);

			circle.setFillColor(Color(200, 200, 200));
			circle.move(notStayArr[m].x, notStayArr[m].y);
			window.draw(circle);

		}

for (int m = 0; m < stayArr.size(); m++) {
	CircleShape circle(mSize);

	circle.setFillColor(Color(90, 90, 50));
	circle.move(stayArr[m].x, stayArr[m].y);
	window.draw(circle);
}

[Василий Банников]

Uncle_Savva, а профилировал?
Вообще например можно заменить class на struct (хотя я не уверен, чем они в плюсах отличаются)
Можно попробовать вот этот кусок упростить:

for (int i = notStayArr.size() - 1; i >= 0; i--) {
    for (int j = stayArr.size() - 1; j >= 0; j--) {
      if (sqrt(pow(notStayArr[i].x - stayArr[j].x, 2) + pow(notStayArr[i].y - stayArr[j].y, 2)) <= notStayArr[i].size + stayArr[j].size) {
        stayArr.push_back(notStayArr[i]);
        notStayArr.erase(notStayArr.begin() + i);
        break;
      }
    }
  }

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

[GavriKos]

Василий Банников, Uncle_Savva самая примитивная оптимизация по вычислениям - не считать корень для расстояния, а сравнивать квадраты расстояний. Слева убираешь sqrt, справа возводишь в квадрат.

[GavriKos]

Ну и надо что то делать с push_back и erase... Жирноватые операции могут оказаться в цикле

[Uncle_Savva]

GavriKos, а есть аналоги? Я просто только изучаю c++, раньше на питоне делал такую же программку - работала быстрее

[GavriKos]

Uncle_Savva, аналоги чего? пуша и эрейза? Вам не аналоги нужны, а менять сам алгоритмический подход чтобы не делать эти операции, или делать их меньше

Answer 1

[Wataru]

Закоиментируйте попеременно отрисовку всех кругов и вычисления. Смотрите, какие частоты кадров получаете. Может быть, тормозит отрисовка - тут только поменять способ отрисовки поможет.

Answer 2

[res2001]

В свое время оптимизировал нечто похожее на Windows API. Там просто выводил все в контекст в памяти, а затем копировал этот контекст в контекст устройства вывода (окно). Думаю что-то подобное можно соорудить и в SFML.
Так же может поможет другой подход - отключение отрисовки и включение ее после того как все будет нарисовано.
С SFML никогда дела не имел, просто это достаточно общие подходы, на мой взгляд.