Új hozzászólás Aktív témák
-
dabadab
titán
válasz
Ron Swanson #4165 üzenetére
"Kis mennyiségű adatnál szépen le is fut, de ha mondjuk N = több ezer, akkor nem fut le 0,2s alatt...
"
Ó, hát erre egyszerű a megoldás, a lista tetejéről válassz valamit: [link]
Komolyabbra fordítva a szót, az a gondod, hogy kb. a vendégek számának négyzetével nő az elvégzendő számítások mennyisége. A megoldás az, ha találsz ennél kisebb ordójú algoritmust. Első blikkre ilyen lehet az, ha a vendégeket nem direktben hasonlítod össze egymással, hanem az időintervallummal machinálsz.
Például csinálsz egy listát, amiben olyan elemek vannak, amik állnak egy időpontból, a már ott lévő vendégek számából és az abban az időpillanatban érkezett vendégek számából és simán ezen a listán mész végig minden egyes vendégre.
Ez egyébként továbbra is algoritmikus kérdés, nem C++ - specifikus.
Hogy ontopic legyek, a C++ kódod valami egészen rettenetes és elavult, szóval fogadni mernék, hogy ezt a magyar (felső)oktatás keretében tanultad
, szerintem azt is érdemes jobb átnézni:
1. TVendegek:
Minek az a T? Most komolyan? Mitől lesz bárkinek is jobb attól, hogy az összes osztály neve T-vel kezdődik, mint "type" (sőt, "típus"). Szóval legyen inkább Vendegek.
Miért Vendegek? Egyetlen vendég adatait tárolja, nem többét, szóval legyen inkább Vendeg.
És persze kódot szigorúan angolul írunk, szóval a végleges változat az a Guest.2. erkezes / tavozas
Ha már név: itt pont van értelme annak, hogy jelöljük, hogy ezek adattagok, szóval m_arrive, m_leave
Adattagokat csak kivételes esetben érdemes kirakni publikba, ez meg semmiképpen sem az, szóval legyenek csak private-ok (és a private tagokat érdemes a publicok mögé rakni, mert így jobban olvasható a kód: az elején ott van a mindenkit érdeklő rész, a class API-ja, az implementáció meg elfér hátul).3. TVendegek(const int E, const int T):
A constok itt elég feleslegesek (érték szerit átadott primitívekről van szó), a nevek meg lehetnek nyugodtan beszédesek, a C++-ban a scope-ok miatt az is tök jól működik, hogyC::C(int x) : x(x) {}
De mivel a tagok neve pont az előbb kapott egy m_ előtagot, amúgy se lenne névütközés legyen inkábbGuest(int arrive, int leave)
....
és most mennem kell, majd folytatom, addig a többiek úgyis belekötnek abba, amit írtam
-
Drizzt
nagyúr
válasz
Ron Swanson #4165 üzenetére
Szerintem itt van az idealis megoldas, a 3 kozul a kozepso. De elkepzelhetonek tartom teljesen mas megkozelitesek is hasonloan gyorsak lehetnek. [link]
A te megoldasod o(n2) - nek nez ki. -
mgoogyi
senior tag
válasz
Ron Swanson #4165 üzenetére
Pontos feladatleírás?
for (i = 1; i < vendegek.size(); i++) {
Itt 0-tól kéne indulni, az első vendég is lehet a megoldás.
A TVendegek osztályt átnevezném Vendeg-re, mert az egy darab vendég szerintem.A feltöltésnél add át a vektornak a ctor-ba a méretét, hogy a push_back-nél elkerüld az átméretezést.
Ha kevés benne a hely, újrafoglal magának helyet és másolgat. De várhatóan nem ezen múlik.A kódodnál viszont valszeg a dupla for ciklusnál lehet fogni sokat, az teszi négyzetessé a futási idejét a bemenet méretétől függően. Ez a feladat gyakorlatilag annyi, hogy melyik zárt intervallumnak van a legtöbb metszete a többivel.
Én valami olyasmit csinálnák, hogy rendezném a vendégeket érkezési sorrendben (/távozásiban ) és végigmennék rajtuk lineárisan és jegyezném, hogy most jött valaki, most elment, és azt nézném, hogy mikor voltak a legtöbben.
Oké, most esestt le. Nem kell a vendégeket rendezni, külön az érkezési idejüket egy tömbbe teszed, külön a távozásit és párhuzamosan haladsz a kettőn két külön indexszel. Ha a soron követő két szám között az érkezési <=, akkor növelsz a számlálón, ha meg nem, akkor csökkentesz. Ennek a számlálónak a maximumát keresed és egy vendéget, aki akkor ott volt.
Ez már elég erős tipp szerintem. Lényeg, hogy az egymásba ágyazott ciklusokkal nem fogod tudod megoldani elég gyorsan, csak lineárisan mehetsz végig a vendégek dolgain.
Új hozzászólás Aktív témák
● ha kódot szúrsz be, használd a PROGRAMKÓD formázási funkciót!
- Intel Core i5 / i7 / i9 "Alder Lake-Raptor Lake/Refresh" (LGA1700)
- The Division 2 (PC, XO, PS4)
- Eredeti játékok OFF topik
- Gyúrósok ide!
- Autós topik
- Elektromos rásegítésű kerékpárok
- Maximum 320 Hz-et képes magából kipréselni a Philips dual mode-os monitora
- exHWSW - Értünk mindenhez IS
- Xbox Series DevMode Emulátor
- Gitáros topic
- További aktív témák...
- Lenovo ThinkPad L590 / Intel CORE i5 / 8gb ram / 256gb SSD / FHD kijelző / Windows 11
- Lenovo Yoga 370 szép állapotú 24 hónap jótállás
- HIBÁTLAN iPhone 14 256GB Midnight - 1 ÉV GARANCIA - Kártyafüggetlen, MS2290, 92% Akkumulátor
- Samsung Galaxy A53 5G - 128 GB - fekete - (130)
- HIBÁTLAN iPhone 14 256GB Midnight - 1 ÉV GARANCIA - Kártyafüggetlen, MS2289, 90% Akkumulátor
- Kingmax 1x2GB DDR2 800 RAM eladó
- Nintendo Switch bazár (Okosított Nintendo Switch konzolok, játékok, tartozékok)
- ÚJ Lenovo LOQ 15IRX9 - QHD 165Hz - i7-13650HX - 16GB - 1TB - RTX 4060 - Win11 - 3 év garancia
- Lenovo ThinkPad X13 G2 multitouch
- Csere-Beszámítás! RGB Számítógép PC játékra! R5 5600X / RTX 3060Ti 8GB / 32GB DDR4 / 500GB SSD
Állásajánlatok
Cég: Promenade Publishing House Kft.
Város: Budapest
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest