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

• #4168 dabadab titán Ron Swanson #4165

  Új Válasz 2018-11-21 23:44:17 #4168

  Ú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

  

  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, hogy
  C::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ább
  Guest(int arrive, int leave)

  ....

  és most mennem kell, majd folytatom, addig a többiek úgyis belekötnek abba, amit írtam

• #4167 Drizzt nagyúr Ron Swanson #4165

  Új Válasz 2018-11-21 23:38:47 #4167

  Ú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

  

  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.

• #4166 mgoogyi senior tag Ron Swanson #4165

  Új Válasz 2018-11-21 23:25:37 #4166

  Ú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

  

  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