Kontejner pro uchování <vzdálenost, objekt> – C / C++ – Fórum – Programujte.com

Ahoj,

pokouším se dát dohromady jednoduchý program, v rámci kterého mám lodě, definované IDčkem, XY souřadnicemi a úhlem (úhel je jen kvůli budoucí funkcionalitě). Jedna z lodí je hráč, a zbytek lodí bych rád dostal do nějakého kontejneru seřazené podle toho, jak jsou daleko od hráče. Taky bych rád, aby výsledný program byl co nejrychlejší, na paměti nesejde.

V rámci jistého nadšení z kontejnerů a jmenovitě <map> jsem napsal program:

#include <iostream>
#include <map>
#include <ctime>

using namespace std;

struct Ship {
	int id;
	float x, y, a;
};

int main() {
	srand(time(0));								// Cisteni random
	Ship actor = {-1, 0.f, 0.f, 0.f};			// Lod hrace
	map<float, Ship> drawpipe;					// Asociativni pole, indexem je vzdalenost ke hraci
	
	Ship *ships = new Ship[100];				// Pole lodi
	for (int i = 0; i < 100; i++) {				// Iniciace id, nahodnych souradnic, uhel zatim nic
		ships[u].id = i+1;
		ships[i].x = rand() % 1000 - 500.f;
		ships[i].y = rand() % 1000 - 500.f;
		ships[i].a = 0.f;
	}
	
	float dist;									// Pomocna promenna pro vypocet vzdalenosti
	for (int i = 0; i < 100; i++) {
		dist = (ships[i].x - actor.x) * (ships[i].x - actor.x) + (ships[i].y - actor.y) * (ships[i].y - actor.y);
		//drawpipe.push(dist, ships[i]);		// Pridej objekt do pole na pozici danou vzdalenosti
	}
	
	for(auto &object, drawpipe) {				// Pro vsechny prvky kontejneru drawpipe vypis, jak se budou vykreslovat
		cout << "Object " << object.second.id << " at [" << object.second.x << ", " << object.second.y "] with distance " << object.first << endl;
	}
	
	return 0;
}

Nicméně pak mi došlo, že vlastně nevím, jak uložit do drawpipe objekty způsobem, se kterým s nimi chci pracovat. Online dokumentace mi moc nepomohla.

V podstatě mám 2 otázky:

1. Vyplatí se použít na takovýto program kontejnery, nebo jsou zbytečně pomalé? Pokud se to vyplatí, který kontejner mám použít, resp. jak mám do map přidat objekty takovým způsobem, aby dva objekty se stejným klíčem byly za sebou a nepřepsaly se?
2. Pokud se to nevyplatí, a já to budu programovat na nejnižší možné úrovni, co je rychlejší: vytvořit si pole struktur <objekt, vzdálenost> a aplikovat na něj mergesort (pochopitelně vylepšený o insert sort) nebo se patlat se spojovým seznamem (předpokládám, že tahle varianta určitě není nejrychlejší)

Co jsem se tak začetl, tak map je realizována binárním stromem, ale co se týče stromů, tak nejsem příliš zběhlý v jejich vyvažování. Navíc potřebuju, aby vytvoření pole bylo maximálně rychlé, jakákoli další práce s ním už bude jenom čtení (a to nikoliv náhodné, ale vždycky projet celé pole od začátku do konce). 

Díky moc předem za všechny rady

#2 ondrej39
Jsem si vědom premature optimization, ale právě vím, že pokud v budoucnu bude mít moje aplikace nějaký bottleneck, pak to bude právě zde. Za normálních okolností bych si to naimplementoval přes manuální dynamickou správu paměti, ale vzhledem k blížícímu se Ludum Dare jsem se chtěl pro zrychlení naučit kontejnery a zajímalo mě, jaký vlastně mají dopad na výkon.

A máš pravdu, miliony objektů (snad) mít nebudu, spíše by to bylo v řádu jednotek tisíců (za předpokladu, že bych na LD programoval zrovna to, kvůli čemu provádím tohle malé kontejnerové cvičení).

Každopádně díky moc, multimap dělá přesně to, co jsem potřeboval.

Pokud se ti ty pozice nemeni, tak asi ani s multimapou problem nebude... Ale jak se ti zacnou menit a budes muset pokazde preusporadat celou mapu, tak nakonec skoncis u vectoru, protoze prochazeni mapy/multimapy po prvcich je "drahe". Obzvlaste, pokud bude dat hodne a bude se casto zahazovat datova cache procesoru.

U vectoru by pak bylo dulezite kolikrat bys podle vzdalenosti hledal a kolikrat se to mezi tim cele preusporadalo. Pokud bys mel jedno preusporadani a tisice hledani, tak bys to proste seradil a hledal "binarne". Pokud by vychazelo casteji preusporadani, tak bych razeni snad i uplne vynechal a hledal sekvencne.

#4 KIIV
Asi jsem měl uvést v původním postu více informací o tom, co jsem původně zamýšlel, napravím to teď:
V rámci 2D prostoru mi jde o určení toho, kdo je vůči hráči v jak daleko a podle toho mít objekty seřazené (protože s tím pak budou probíhat další výpočty). Objekty po sobě mohou střílet a mohou se hýbat, nehledě na to, že hráč se může hýbat taky. Tím pádem v každém snímku musím vzdálenosti všech objektů přepočítat, případně zahrnout nové objekty.

Když pominu režii na alokaci/uvolnění paměti, tak vytvořit mapu na začátku každého snímku a její následné zahození na konci snímku mi nezní jako až tak špatný nápad, protože stejně musím pro každý prvek nejdříve spočítat vzdálenost a poté, co jsou všechny prvky spočteny, tak musím seznamem projít znovu a seřadit ho.

V počítání složitostí nejsem až takový expert, abych dokázal odhadnout, kolik řádově potřebuju operací, pokud bych chtěl do existujícího seznamu přidávat nové prvky, odebírat ty, které "umřely" a ještě je mezi sebou prohazovat kvůli seřazení. Každopádně můj laický odhad, je, že bych se tímhle stylem mohl nejhůře dostat na O(n2), zatímco vytvoření/seřazení seznamu má jako nejdražší operaci řazení s náročností O(nlogn).

První přístup by v rámci své práce musel neustále alokovat/uvolňovat paměť (což by ten druhý mohl obejít alokací dostatečně velkého bloku paměti) kvůli vkládání objektů a navíc aby uměl vkládat v konstantním čase, tak by musel být implementován jako spojový seznam, který je oproti poli pomalejší na projití a navíc bych v něm musel chodit pouze sekvenčně.

Takhle když si to rozeberu, tak mi přijde, že nejvýhodnější je mít staticky velké pole o dostatečné velikosti, na začátku framu si ho naplnit, přepsat předchozí data a seřadit. Na to můžu použít vector, ale stále neumím přijít na to, zda když tím polem budu stejně potom procházet už jenom jednou za snímek, zda multimap není schopná vytvořit to pole rychleji, než vector spojený se sortem.