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

• #2391 Radíros csendes tag Gerghu #2380

  Új Válasz 2006-12-08 16:53:51 #2391

  Ú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

  

  Radíros

  csendes tag

  válasz Gerghu #2380 üzenetére

  És (#2385) Joooe üzenetére...
  
  Ez a bitmátrix egy csúcs-szomszédsági mátrix,
  amely azt mondja meg az M[i,j] elemben, hogy
  az i-edik csúcsból vezet-e él a j-edik csúcsba.
  (Pl. ha igen: magas a bit, ha nem, akkor alacsony)
  
  Ha ezt érted élmátrix alatt, akkor a szkópban lehet
  a következő megoldás is:
  1. állítsd elő a mátrix tranzitív lezártját
  2. a tranzitív lezártból könnyen jönnek
  az erős komponensek egy rendezésre
  visszavezethető halmaz-osztályozással
  
  Sajnos a tranzitív lezárt számítása n^3 * log n műveletigényű,
  viszont könnyen párhuzamosítható és a hw-be épített
  bitműveleteket is jól kihasználja.
  (Az én logikám szerint ezt a legegyszerűbb implementálni.)
  
  Ha valaki felcsigázódott szívesen részletezem...
  

• #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]

• #2381 Jester01 veterán Gerghu #2380

  Új Válasz 2006-12-07 15:27:17 #2381

  Ú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

  

  Jester01

  veterán

  válasz Gerghu #2380 üzenetére

  És ez le fog futni 0.3s alatt? Főleg java-ban?

• #2379 Jester01 veterán Gerghu #2378

  Új Válasz 2006-12-07 14:45:19 #2379

  Ú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

  

  Jester01

  veterán

  válasz Gerghu #2378 üzenetére

  Ha elárulnád a pontos feladatot akkor lehet, hogy tudnánk annyit segíteni, hogy mégis meg tudd csinálni.

• #2377 cucka addikt Gerghu #2374

  Új Válasz 2006-12-07 08:32:48 #2377

  Ú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

  

  cucka

  addikt

  válasz Gerghu #2374 üzenetére

  c-ben gondolkozva:
  
  a 10ezer csúcs miatt célszerű éllistával ábrázolni, ott pedig nem probléma a memórialimit.
  csúcsoknak lefoglalod előre a memóriát, akkor ugye tömbként kezeled, és a tömb indexe fogja megmutatni az illető csúcs ''nevét''. minden csúcsból kiindul egy lista, ami tartalmazza az éleket. egy élnek van végpontja, ami egy int és rákövetkező csúcsa, ami egy csúcsra mutató pointer, vagyis egy csúcs mérete nagyjából 12byte, össszes csúcs így 240kbyte-ot foglal. ha nagyon szorít az időlimit, akkor eltárolhatod minden csúcsnál az utolsó élre mutató pointert, így a beszúrás n idő helyett 1 idő alatt megtörténik.
  
  az élmátrix az egyébként micsoda? én csak a csúcsmátrixot és az éllistát ismerem/használtam.
  
  listákról minden könyvben olvashatsz, de a gúgle is sok hasznos találatot dob, főleg ha angolul keresel. ennek fényében nem értem, mi a probléma a file-ból való lista felépítéssel. (kulcsszó: linked list).

• #2376 Jester01 veterán Gerghu #2374

  Új Válasz 2006-12-07 02:40:30 #2376

  Ú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

  

  Jester01

  veterán

  válasz Gerghu #2374 üzenetére

  Hacsak egyéb ok nincs rá akkor a gráfot egyszerûen csomópontokkal és belõlük induló élekkel ábrázoljuk:
  
  class Node
  {
  public:
  vector<Node*> Edges;
  };
  
  Ez nálam mérve 12 byte csomópontonként, az kemény 120kB. A 200000 pointer az 800kB. A legrosszabb vector overhead-del számolva is belefér 2 megába az egész (64 bites gépen max. dupla ennyi).
  
  Ha valami egyéb információt is el kell tárolni a csomópontokról/élekrõl akkor az persze erre még rájön, de azt semmiképp nem úszod meg.
  
  (Az éleknek az egyszerûség kedvéért nem csináltam külön osztályt.)

• #2308 Jester01 veterán Gerghu #2305

  Új Válasz 2006-11-25 23:28:40 #2308

  Ú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

  

  Jester01

  veterán

  válasz Gerghu #2305 üzenetére

  Most látom, hogy a fõ probléma a replaceEkezet fvben a default: break; sor lehet.
  Emiatt az elsõ nem ékezetes betûnél abbahagyja a konverziót.

• #2306 cucka addikt Gerghu #2305

  Új Válasz 2006-11-25 23:04:17 #2306

  Ú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

  

  cucka

  addikt

  válasz Gerghu #2305 üzenetére

  a for ciklusod magjában semmi nem függ az i ciklusváltozótól. gyakorlatilag csak akkor fog kicserélni bármit is a függvény, ha az illető string egyetlen ékezetes betűből áll.
  a ciklusban az a string helyett az a[ i ]-t nézegesd inkább.
  
  megj: a replaceEkezet(''áőéóü'') sem működik, csak mivel nem tárolod el a visszatérési értékét, ezt nincs honnan tudd. meg egyáltalán semmi értelme ezt a függvényt meghívni így. (megcsináltatsz vele valamit, az eredményt meg kidobod.. király )
  
  [Szerkesztve]

• #2301 Jester01 veterán Gerghu #2300

  Új Válasz 2006-11-20 14:58:45 #2301

  Ú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

  

  Jester01

  veterán

  válasz Gerghu #2300 üzenetére

  Használd az strcoll függvényt, ha van.
  Kézzel pl. úgy lehet csinálni, hogy felsorolod egy tömbbe a betűk ábécérendbeli pozícióját és onnan rendezel.
  
  int abc[] = { ... ide kell felsorolni a pozíciókat ... };
  int i;
  for(i = 0; abc[a[ i ]] == abc[b[ i ]] && a[ i ] != 0; i++);
  
  (utf-8 esetén még finomítani kell)
  
  [Szerkesztve]

• #2283 BullSoft tag Gerghu #2282

  Új Válasz 2006-11-14 19:46:08 #2283

  Ú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

  

  BullSoft

  tag

  válasz Gerghu #2282 üzenetére

  például láncolt listát

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