Új hozzászólás Aktív témák

• #2415 Joooe tag gaben #2404

  Új Válasz 2006-12-10 18:00:28 #2415

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Joooe

  tag

  válasz gaben #2404 üzenetére

  Nem tudom milyen makrókat (#define) használsz, de azokra is figyelj oda, mi történik a behelyettesítéskor...

• #2414 Joooe tag Radíros #2410

  Új Válasz 2006-12-10 17:49:44 #2414

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Joooe

  tag

  válasz Radíros #2410 üzenetére

  i = (int) d;
  
  Ugyanez pascalban:
  i:=integer(d);
  
  Ha jól emlékszem ehhez túros pacalban kellett még egy {$R-} direktíva.
  

• #2402 Joooe tag Radíros #2401

  Új Válasz 2006-12-09 07:30:41 #2402

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Joooe

  tag

  válasz Radíros #2401 üzenetére

  Nem az input benyalása a megoldás asszem, elvileg megfelelő pufferrelést séróból meg kéne hogy oldja egyszeri folyamatos végigolvasás esetén.
  Maga az is műveletigényes egy kicsit, hogy a szöveges formában tárolt számokból összeállítani az inteket.
  
  De érdekes, ezt tudja valaki miért lehet lassabb?
  <fstream>-mel:
  ifstream be;
  be.open(''be.txt'');
  
  int n,m,p;
  be >> n;
  be >> m;
  be >> p;
  p--;
  
  int honnan, hova;
  for (int i=0; i<m; i++)
  {
  be >> honnan;
  be >> hova;
  honnan--;
  hova--;
  // itt csinálunk valamit
  }
  be.close();
  
  <stdio.h>-val:
  
  int n,m,p;
  FILE* be = fopen(''be.txt'',''rt'');
  
  fscanf(be,''%d %d %d'',&n,&m,&p);
  p--;
  
  int honnan, hova;
  for (int i=0; i<m; i++)
  {
  fscanf(be,''%d %d'',&honnan, &hova);
  honnan--;
  hova--;
  // itt csinálunk valamit
  }
  fflush(be);
  fclose(be);
  
  
  Az utóbbi kb. fele-haramada idő alatt végez egy 1 megás szövegfájllal.
  Nem nagyon szoktam STL filekezelést használni, gondolom ennyire nyomorék nem lehet, mit szúrok el?
  
  
  [Szerkesztve]

• #2400 Joooe tag Radíros #2395

  Új Válasz 2006-12-09 05:11:43 #2400

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Joooe

  tag

  válasz Radíros #2395 üzenetére

  ''Visszavonom!!!
  
  10000 csúcssal és 64 bit gépi szószélességgel számolva:
  157 * 10^8 * 14 ~ 300 GHz-es proci kellene 1mp futásidőhöz
  (szekvenciálisan, csővezeték és cimzésműveletek elhanyagolva)''
  Valószínűleg pontatlanul idézte a feladatot a kérdező, és csak egy konkrét csúcson átmenő köröket kell vizsgálni.Így nincs szükség a teljes tranzitív lezárt meghatározására.
  Ezt azért gonodlom, mert én is egy hasonló feladatot csináltam (na nem magamnak, hál'isten az alga csak a távoli múltból dereng már nekem )
  
  Az algoritmus érdemi részének futási idejét sikerült olyan 0,015 s-re csökkenteni ezzel a módszerrel még a leghúzósabb inputokon is. (AMD 3200 procin, párhuzamosítás nélkül)
  
  Ami viszont iskolai szivatás a dologban: bizonyos teszt inputok esetén ha semmi mást nem csinál a program, csak kb. be >> szam; módszerrel standard folyamműveletekkel végigolvassa az inputot (De ezen kívül tényleg semmit nem csinál, nem konstruál gráfot, nem vizsgál feltételeket, stb.) már az kifut a futási időlimitből az inputok egy részén
  
  [Szerkesztve]

• #2399 Joooe tag cucka #2398

  Új Válasz 2006-12-09 04:52:43 #2399

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Joooe

  tag

  válasz cucka #2398 üzenetére

  Most gyorsan átlapoztam a K&R-t de nem látom annak garanciáját, hogy ez így működni fog. Ilyen méretekben valószínűleg működik, mert a hardver adottságaiból adódóan defaultból int-ként végzi el a számolást és aztán annak ''int-té castolásakor'' ugye nem történik semmi, tehát marad a helyes eredmény.
  
  De ha ugyanezt az elvet követjük amit alkalmaztál, és ugyanakkor kevésbé vasbarát méretekig növeljük a dolgot:
  unsigned __int64 mix32(unsigned __int32 h, unsigned __int32 l)
  {
  return (h << 32) + l;
  }
  
  esetben már túlcsordul.
  
  unsigned __int64 mix32(unsigned __int32 h, unsigned __int32 l)
  {
  return ((__int64)h << 32) + l;
  }
  
  Így viszont jó.
  
  Lehet hogy működik, de én biztosabbnak érzem mindig explicit módon castolni ilyen bites játszadozásoknál:
  unsigned int assign16(unsigned char LD, unsigned char HD)
  {
  return ((unsigned int)HD << 8 | (unsigned int)LD) >> 3;
  }
  
  De ha ez csak az én ''szám íze'' szerint van így akkor bocsi
  
  
  [Szerkesztve]

• #2396 Joooe tag cucka #2392

  Új Válasz 2006-12-08 18:12:58 #2396

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Joooe

  tag

  válasz cucka #2392 üzenetére

  nem tudom hogy működik ez a kód egyes fordítók lelkivilága szerint, meg most így hirtelen a szabványt sem hasítom, de nekem gyanús, hogy a kifejezés egyik oldala az unsigned char marad a kiértékelés során, és így a 256-tal szorzás mondjuk úgy egy kisebb túlcsordulást okoz
  
  Én még nem találkoztam olyan implementációval (tudom hogy van) ahol az int ne 32 bit lenne

• #2387 Joooe tag k.t.a. #2386

  Új Válasz 2006-12-08 11:48:33 #2387

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Joooe

  tag

  válasz k.t.a. #2386 üzenetére

  Igen
  szam >> 3;

• #2385 Joooe tag Gerghu #2380

  Új Válasz 2006-12-08 05:02:36 #2385

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Joooe

  tag

  válasz Gerghu #2380 üzenetére

  Én inkább egy bitmátrixot tartanék megfelelőnek erre a feladatra.
  A memóriában az is elfér (10000^2/8 = kb. 12 MB)
  Bár elgondolkodtató, hogy ez a megközelítés nem használja ki az élek relatíve alacsony számát.
  
  Ami gyorssá teheti a megvalósítást, hogy ha a mátrix azt mutatja, hogy az i-edik csúcsból elérhető a j-edik, akkor a j-edik sort hozzá VAGY-oljuk az i-edik sorhoz, ezzel tovább bővítve az i-ből elérhető csúcsok listáját, azokkal ami j-n keresztül elérhető.
  
  Ez mindenféle implementációban elvégzendő művelet, hogy megvizsgáljuk, hogy mi van ha arra megyünk, de azt hiszem így tudjuk leggyorsabban megtenni. Így processzortól függően egyetlen művelet során nagyon sok (64?) csúcsra történik meg a vizsgálat.
  
  Az még egy kicsit elgondolkodtató, hogy mikor végeztünk, hiszen ezt többször el kell végezni, de ha végeztünk, akkor azokat a csúcsokat listázzuk amire mátrix[i,i]=1, azaz elérhető magából maga, azaz tagja valamely irányított körnek.
  
  
  
  [Szerkesztve]
  
  [Szerkesztve]

Új hozzászólás Aktív témák