2. Fórumok
  3. Szoftverfejlesztés
  4. C++ programozás
Keresés

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

  • #4168 dabadab titán Ron Swanson #4165
    Új Válasz #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] :D

    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 :DDD, 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 :D

  • #4167 Drizzt nagyúr Ron Swanson #4165
    Új Válasz #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 #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