Optimiziranje Problem

Pozdrav, 

Radim neku igru i tokom igre treba obradjivati VELIK broj upita raznih tipova.

Imate relativno velik niz brojeva, u najgorem slucaju moze imat 10000 elemenata, svakih ~10 sekundi stigne oko 1000000 (10^6) upita.

Upiti mogu bit ovog tipa, poredani po ucestalosti: 

1) Koji je najveci broj u intervalu [x, y], dakle na indeksima x, x+1, x+2 ... y, koji je najveci broj, odnosno kako to moje naivno rjesenje radifor(int i = x; i <= y; i++) m = max(m,a[i]);

2)Koliko postoji negativnih brojeva na intervalu [x, y], moje naivno rjesenje for(int i = x; i <= y; i++) c += (a[i]<0);

3)Umetni neki broj ne neko mjesto. 

4) Neki interval premjesti na kraj niza. da upit kaze, (2, 4), i imamo niz brojeva, 1, 2, 3, 4, 5, 6. Tada interval 1, | 2, 3, 4, | 5, 6, premjestimo na kraj == > 1, 5, 6, 2, 3, 4

5) Izbrisi broj sa neke pozicije. (tada se dva preostala dijela spoje)

Buduci da za obradu svakog od ovih slucajeva meni treba O(n) operacija, program mi na momente zbilja sporo radi, jer ceka obradu.

Prijatelj mi je sugerirao kako upit drugog tipa odgovoriti u O(1). Tj. da posumiram broj negativnih brojeva, i imam niz broj[x], odnosno koliko je negativnih bilo od pocetka do x. Tada je broj negativnih u intervalu broj[y] - broj[x-1]. Al svaki put kad napravim neki od ostala dva upita, moram jos O(n) operacija napravit da bi mogao to ponovno koristit.

Molim vas, bilo kakve prijedloge o ubrzanjima mi recite, ili sugerirajte kako nesto pravilno i pametno napraviti. 

Hvala 

 to nije bitno, neki pristup ili algoritam moze biti implementiran u svakom jeziku.

to mi je jasno, samo me zanimalo u kojem jeziku radi igru, to je sve ;)

Da imam visedretvenost, ali veliki dio programa mora cekati na izvrsavanje ovih upita.

Upiti (tipov) dolaze ispremjesano i svi se odvijaju na pocetnom nizu i mijenjaju ga. Nakon svakog upita potrosim jos malo vremena na spremanje nekog dijela podataka (ovo traje zaista kratko).

Sto se tice koda, nije bas moguce to napravit, jer ovo je dosta pojednostavljeni proglem koji imam. 

Opet nemam dovoljno podataka ali nije više niti bitno. Napravio sam dolje improvizaciju koja ne pretendira biti niti fraktal stvarnih problema i kompleksnosti koda.

Zapravo je tu samo iz jednog razloga. Na tvoje pitanje odgovorio je gore Buda s bin.stablom koje se da implementirati u kojekakvu problematiku te daje odlične rezultate (najbolje u predefiniranim stanjima s masom stvari koje ti trenutrno ne trebaju već samo čupaš par najbitnijih -> ako imaš kakvu grafiku vidi obavezno tu tematiku jer od recimo 5000 poligona crtaš samo 500 po frejmu , ostalo ti guši fps...)

Ma htio sam ti reći sljedeće , često nema zlatnog metka za riješavati razne situacije.Nema headera u c++ (cpu_optimiziraj_to_što_prije_i_kako_god_znaš.h). Svi alati su tu no potrebno ih je slagati često vlastoručno te vremenom i iskustvom puno stvari postaje rutina tako da nemaš u svakom frejmu čeking cijele scene jer imaš ajmo reći 15 aktivnih flagova.Ako se jedan aktivira on postaje rupa u daljnji check njemu podložnih slave flagova itd.. Uglavnom radiš samo one podatke koji ti trebaju , ostalo je na ledu.

Čitaj dalje po raznim forumima , wiki , pitaj , kombiniraj sam ....

U stilu gore napisanog molim te da i shvatiš ovaj snippet koji slijedi. Nije riješenje tvog problema već samo poticaj na bilo-kakvo riješenje koje je bolje od prvobitnog.Zatim slijedi bolje od toga i stvar se kotura sama od sebe + edukacija i zainteresiranost.

http://ideone.com/Cvu6lp

Gibam s posla tako da sam sklepao kod bez nekih provjera ali shvatit ćeš bit

#include <iostream>

#include <algorithm>

typedef unsigned int uint32;

using namespace std;

/*GLOBAL*******neki niz od 0 - 100*/

uint32 data[] = { 27 , 18 , 0 ,3 , 5 , 4 , 6 , 7 , 8 , 14 };

/**********************************/

class NumberManager  {

public:

  NumberManager() {} 

  ~NumberManager() {} 

  uint32* getMaxNum(uint32* begin , uint32 end);

  uint32 getMaxValue() const {return *maxValue;}

  void swapValues( uint32* first , uint32* second);

protected:

   void update();

private:

   /*daj flagove na bitne vrijednosti*/

   uint32* maxValue;

};

void NumberManager::swapValues( uint32* first , uint32* second)

{

   ptrdiff_t shift;

   if(second == maxValue)

   {

     shift = first - second;

   }

   if(first == maxValue )

   {

     shift = second - first;

   }

   swap( *first , *second ); 

   maxValue += shift;

}

void NumberManager::update()

{

   /* operacija 1

   /* operacija 2

   /* operacija ...*/

}

bool maxTwoUint32(uint32 i, uint32 j) 

{ 

  /* static int counter;

   cout<< "loop : " << counter++ << endl; */

   return i<j; 

}

uint32* NumberManager::getMaxNum(uint32* begin , uint32 end)

{

   maxValue = max_element(begin , begin+end , maxTwoUint32);

   return maxValue;

}

bool oddValue (uint32 val)

{ 

   return ((val%2)==1); 

}

int main() 

{

   NumberManager numManager;

   /* frame 1 INITIALIZATION****************************************************/

   uint32* result = numManager.getMaxNum(data , 10);

   cout<< "FRAME 1\nOvdje po onome kako si predstavio problem imaš \n" 

     << "unsorted array pa time i O(n) limitacije kod trazenja\n"

     << "najveceg broja" << endl; 

   cout<< "najveci broj : " << *result << "\n\n" << endl;

   /***************************************************************/

   /*frame 2 CHANGE******************************************************/

   for(uint32 i=0 ; i<10 ; i++)

   {

     data[i] += 83;

   }

   /*ova operacija koja slijedi je nepotrebna dalje jer 

   ako je na indexu 9 (u ovom slučaju broj 19) bio najveći broj

   , bit će i dalje nakon operacija mnozenja i zbrajanja tako

   da u ovom frameu nije potreban checking*/

   result = numManager.getMaxNum(data , 10);

   cout<< "FRAME 2\nnajveci broj nakon sto je na svaki broj u data \n" <<

      "dodan 83 je : " << *result << endl;

   for(uint32 i=0 ; i<10 ; i++)

   {

     cout<< data[i] << endl;

   }

   /***************************************************************/

   /* znaci prilagoditi main algoritme da uopce ne provjeravaju   */                            

   /* ishode koji su unaprijed logikom znani            */                      

   /***************************************************************/

   /*frame 3 CHANGE_AGAIN******************************************************/

   numManager.swapValues( data , data+2 );

   cout<< "\n\nFRAME 3\n";

   for(uint32 i=0 ; i<10 ; i++)

   {

     cout<< data[i] << endl;

   }

   cout<< "swap nultog i 2 index-a" << endl;

   cout<< "najveci broj : " << numManager.getMaxValue() 

     << " s direktnim pristupom" << endl;   

   /*******************************************************************/

   /* imas odmah dohvat na max_element koji gore pratis u samoj klasi */

   /* bez rolanja kroz sve elemente                   */

   /*******************************************************************/

   /**********************/

   /* itd...        */

   /**********************/

   return 0;

}

Napravit ces stablo sa implicitnim kljucem, tj. neces imat kljuc kao usporedbu, vec ces jednostavno pretpostavit da svaki broj koji stavljas je veci od ovih prije. Tada jednostavno gledajuci koliko je manjih od nekog elementa, kaze ti njegovu poziciju u nizu. 

Efektivno ti trebaju dvije funkcije, split i merge. Tj. podijeli neko stablo na dva, i stopi dva stabla u jedno. Nakon sto napravis split, u rootu ti ostanu sve potrebne informacije, napr, broj negativnih i maksimum.

Ukoliko implementiras Splay stablo imat ces brutalne rezultate, jer ono ce ti puno toga pljunuti u O(1).