Hirdetés
- Luck Dragon: Asszociációs játék. :)
- D1Rect: Nagy "hülyétkapokazapróktól" topik
- GoodSpeed: Egy bihari a Hajdúságban
- Brogyi: CTEK akkumulátor töltő és másolatai
- Parci: Milyen mosógépet vegyek?
- sziku69: Fűzzük össze a szavakat :)
- Gurulunk, WAZE?!
- Magga: PLEX: multimédia az egész lakásban
- laskr99: DFI és DFI Lanparty gyűjteményem
- bambano: Bambanő háza tája
-
LOGOUT
Új hozzászólás Aktív témák
-
Radíros
csendes tag
É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... -
Joooe
tag
É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] -
cucka
addikt
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). -
Jester01
veterán
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.) -
cucka
addikt
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] -
Jester01
veterán
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]
én csak a csúcsmátrixot és az éllistát ismerem/használtam.
)
Új hozzászólás Aktív témák
● olvasd el a téma összefoglalót!
- Latitude 7450 14" QHD+ IPS érintő Ultra 7 165U 32GB 512GB NVMe ujjolv IR kam gar
- AKCIÓ! ÚJ! GAMER PC - RTX 5060 8GB - i5 12400F/14400F - 16GB DDR4 - 500GB Nvme SSD
- Lenovo Legion 9 16" 3.2K Mini LED Laptop! i9-13980HX / RTX 4090 / 32GB DDR5 / 2TB NVMe! BeszámítOK
- TUF Gaming F15 FX506HC 15.6" FHD IPS i5-11400H RTX 3050 16GB 512GB NVMe magyar vbill gar
- BONTATLAN Új iPhone 17 PRO MAX Silver - Ezüst 256-512GGB Független 1év Apple G Azonnal átvehető.Deák
- Telefon felváráslás!! iPhone 15/iPhone 15 Plus/iPhone 15 Pro/iPhone 15 Pro Max
- Készpénzes / Utalásos Videokártya és Hardver felvásárlás! Személyesen vagy Postával!
- Nvidia Quadro P400/ P600/ P620/ P1000/ T400/ T600/ T1000 - Low profile (LP) + RTX A2000 6/12Gb
- Bomba ár! Lenovo X1 Carbon 4th: i5-6GEN I 8GB I 512SSD I 14" FHD I HDMI I Cam I W11 I Gari
- AKCIÓ! HP Elitebook 840 G11 üzleti notebook- Intel Core Ultra 5 135U 16GB DDR5 RAM 256GB SSD W11
Állásajánlatok
Cég: NetGo.hu Kft.
Város: Gödöllő
Cég: Promenade Publishing House Kft.
Város: Budapest