Kontejner pro uchování <vzdálenost, objekt> – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Toto vlákno bylo označeno za vyřešené — příspěvek s řešením.
Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Doomista+1
Stálý člen
9. 4. 2016   #1
-
0
-

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

Nahlásit jako SPAM
IP: 2a00:1028:83a0:33ea:1d2d:...–
Na vše stačí iostream...
Reklama
Reklama
Řešení
ondrej39+1
Věrný člen
9. 4. 2016   #2
-
+1
-
Zajímavé
Vyřešeno Nejlepší odpověď

#1 Doomista
Klíč je u tebe vzdálenost, namísto std::map použij std::multimap. V std::map můžeš mít pouze unikátní klíče, klíč jednoznačně identifikuje konkrétní záznam v kontejneru.

IMHO řešíš blbosti. Viz Premature Optimization. Jsem si skoro jistý, že lodí nebudeš mít miliardy, ba ani miliony, v takovém případě tě rozdíl mezi STL kontejnery a nějakou vlastní kolekcí (která by byla extrémně vypiplaná) vůbec nemusí zajímat.

Pokud tě to bude tak trápit, nauč se složitost, pak ji (v podobě paměťové i časové) aplikuj na benchmarky, kde porovnáš STL a vlastní kontejnery a vyber to, co bude pro tebe nejlepší.

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Doomista+1
Stálý člen
9. 4. 2016   #3
-
0
-

#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.

Nahlásit jako SPAM
IP: 2a00:1028:83a0:33ea:1d2d:...–
Na vše stačí iostream...
KIIV+42
God of flame
9. 4. 2016   #4
-
+1
-
Zajímavé

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.

Nahlásit jako SPAM
IP: 94.113.92.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Doomista+1
Stálý člen
9. 4. 2016   #5
-
0
-

#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.

Nahlásit jako SPAM
IP: 2a00:1028:83a0:33ea:1d2d:...–
Na vše stačí iostream...
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 88 hostů

Podobná vlákna

Událost pro nový objekt — založil Radkus

Uchování dat v *.exe — založil Tukan

Kontejner — založil Gadael

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý