NERD2 문제 TLE, scanf 관련 질문입니다.

  • zzerross
    zzerross

    NERD2

    문제를 풀고 있는데, TLE 극복을 못하던 중에,

    아무리 분석을 해봐도 로직에서의 Big O를 못찾고,

    구간 별 측정을 해보니, scanf()에서 시간을 많이 소요하는 거 같습니다.

    입력 관련 AOJ글들을 찾아보니,
    scanf()가 그래도 빠른 입력인 거 같은데요. 더 빠른 방법이 있을려나요?

    정말 로직 상에 문제가 있는 건지 답답해서 질문드려봅니다.

    로직, 코딩 상으로 아래의 것들을 변경해서 측정해보 았는데 차이가 없더라구요.

    • treep node의 new 할당 -> 정적 배열로 변경
    • treep insert에서 split, merge없이 삽입되도록 변경 및 pliority 조절

    성능 측정:

    Visual studio 2012

    • release mode
      ...
      555740
      725022
      398417
      728733
      total: 1388ms
      scanf: 1279ms

    • debug mode
      555740
      725022
      398417
      728733
      total: 7098ms
      scanf: 6160ms

    코드는

    #include <stdio.h>
    
    #define dbg
    #define clk
    
    #ifdef dbg
    #define pr printf
    #else
    #define pr
    #endif
    
    #ifdef clk
    #include <time.h>
    
    clock_t _c[4];
    
    #define millis(c) c // ((c / CLOCKS_PER_SEC) * 1000.0)
    #define clki() for (int i = 0; i < 4; i++) _c[i] = 0
    #define clk0(i) (_c[i] = clock())
    #define clk1(i) (_c[i+1] += (clock() - _c[i]))
    #define clkp(s, i) pr("%s: %10dms", s, millis(_c[i+1]))
    #else
    #define clki()
    #define clk0(i)
    #define clk1(i)
    #define clkp(s, i)
    #endif
    
    #define sz 50000
    
    int rnd() {
        static int s = 7654321;
    
        return s = (s * 2 + 3) % 9876543;
    }
    
    int max(int x, int y) { return x > y ? x : y; }
    
    class dt {
    public:
        int x, y;
    
        bool operator<(dt& d) { return x < d.x; }
        bool operator>(dt& d) { return x > d.x; }
        bool operator<=(dt& d) { return x <= d.x; }
        operator int() { return x; }
    
        void dmp() {
    #ifdef dbg
            pr("%d,%d,", x, y);
    #endif
        }
    } dt[sz];
    
    template <typename K>
    class tr {
    public:
        K* k;
        int p, c;
        tr *l, *r;
    
        tr(K* k = NULL) { init(k); }
    
        tr& init(K* k = NULL) {
            this->k = k;
            p = rnd();
            c = 1;
            l = r = NULL;
    
            return *this;
        }
    
        static int cnt(tr* t) { return t ? t->c : 0; }
    
        tr* updt() { c = 1 + cnt(l) + cnt(r); return this; }
    
        tr& splt(tr* t) {
            if (t) {
                if (*k < *t->k) {
                    t->l = splt(t->l).r;
                    r = t->updt();
                } else {
                    t->r = splt(t->r).l;
                    l = t->updt();
                }
            }
    
            return *this;
        }
    
        static tr* mrg(tr* l, tr* r) {
            if (!l) return r;
            if (!r) return l;
    
            if (l->p > r->p) {
                l->r = mrg(l->r, r);
                return l->updt();
            } else {
                r->l = mrg(l, r->l);
                return r->updt();
            }
        }
    
        static tr* inst(tr* t, tr* n) {
            tr s;
    
            s.init(n->k).splt(t);
    
            return mrg(mrg(s.l, n), s.r);
        }
    
        static tr* rmv(tr* t, K& k, tr** b = NULL) {
            if (k < *t->k) {
                t->l = rmv(t->l, k);
            } else if (k > *t->k) {
                t->r = rmv(t->r, k);
            } else {
                tr* r = mrg(t->l, t->r);
    
                if (b) *b = t;
    
                return r;
            }
    
            return t->updt();
        }
    
        tr& lth(int n) {
            if (n < cnt(l))
                return l->lth(n);
            else if (n > cnt(l))
                return r->lth(n - cnt(l) - 1);
    
            return *this;
        }
    
        static tr* upr(tr* t, K& k) {
            if (!t) return NULL;
    
            if (k < *t->k) {
                tr* u = upr(t->l, k);
                return u ? u : t;
            } else {
                return upr(t->r, k);
            }
        }
    
        static tr* lwr(tr* t, K& k) {
            if (!t) return NULL;
    
            if (k <= *t->k) {
                return lwr(t->l, k);
            } else {
                tr* l = lwr(t->r, k);
                return l ? l : t;
            }
        }
    
        static int hgt(tr* t, int h = 0) {
            if (!t) return h;
    
            return 1 + max(hgt(t->l, h), hgt(t->r, h));
        }
    
        void dmp() {
    #ifdef dbg
            k->dmp();
    
            if (l) pr("(%d", *l->k); else pr("(-");
            if (r) pr(",%d) ", *r->k); else pr(",-) ");
    #endif
        }
    
        static void dmp(tr* t) {
    #ifdef dbg
            if (!t) return;
    
            dmp(t->l);
            dmp(t->r);
    
            t->dmp();
    #endif
        }
    };
    
    typedef tr<class dt> td;
    
    td tp[sz];
    int tc, nr;
    
    int nrd(td*& t, class dt& d) {
        td* u = td::upr(t, d);
    
        if (u && d.y < u->k->y)
            return false;
    
        return true;
    }
    
    void rmv(td*& t, class dt& d) {
        class dt k = d;
    
        for (td *l; l = td::lwr(t, k);) {
            k.x = l->k->x;
    
            if (l->k->y < d.y)
                t = td::rmv(t, *l->k);
        }
    }
    
    int main() {
        clki();
    
        clk0(0);
    
        for (scanf("%d", &tc); tc-- > 0;) {
            td *t = NULL;
            int c = 0;
    
            scanf("%d", &nr);
    
            for (int i = 0; i < nr; i++) {
                class dt& d = dt[i];
    
                clk0(2);
                scanf("%d %d", &d.x, &d.y);
                clk1(2);
    
                if (nrd(t, d)) {
                    td* n = &tp[i].init(&d);
    
                    t = td::inst(t, n);
    
                    rmv(t, d);
                }
    
                c += td::cnt(t);
            }
    
            printf("%d\n", c);
        }
        clk1(0);
    
        clkp("total", 0); pr("\n");
        clkp("scanf", 2); pr("\n");
    
        return 0;
    }
    


    10년 전
9개의 댓글이 있습니다.
  • Being
    Being

    입력의 문제가 아니라 로직에 문제가 있어 무한루프를 도는 것으로 보입니다.


    10년 전 link
  • Being
    Being

    아 무한루프는 아니고 그냥 매우 느린 것 같네요...


    10년 전 link
  • zzerross
    zzerross

    이새벽에도 안주무시고, 답변 감사합니다. ^^

    자료구조 호출부 측정해보고,

    scanf만의 수행 시간을 아래 코드에서 잰 것이긴 한데...

    clk0(2);
            scanf("%d %d", &d.x, &d.y);
            clk1(2);

    저 입력부가 느린게 아니라, 자료 구조 내에서 아니면, 로직에서 느린 부분이 있어 보이신다는 얘기 신거죠?


    10년 전 link
  • Being
    Being

    네. 코드를 읽을 여유가 없어서 채점 데이터로 돌려 봤습니다. (저는 지금 미국이기는 합니다...)


    10년 전 link
  • JongMan
    JongMan

    전역 rmv() 함수에 문제가 있습니다.


    10년 전 link
  • zzerross
    zzerross

    어제 밤에 문제가 발견되어 한번 수정한 것인데...다시 봐야 겠네요..
    답변 감사합니다


    10년 전 link
  • zzerross
    zzerross

    JongMan 님 조언을 참고해서 추석 지나고 그 함수를 이틀째 다시 보고 있는데, TLE해결이 않되네요...ㅜ.ㅡ

    1) 전역 rmv()에서 "지배되는 점을 찾는 것, td::lwr()" 과 실제 "삭제하는 것, td::rmv()"이 두번 탐색을 야기시킬 것 같긴 한데,

    하나로 합쳐보는 작업도 도통 잘 않되네요.
    treap 구현을 일반적인 형태로 유지하고 싶기도 하구요.

    2) 작은 random data들로 꽤나 다시 검증 해보긴 했습니다만,
    혹시 전역 rmv()의 문제가 성능이 아니라, 답이 잘못나오게 되는 것을 말씀하신 걸까요?

    3) STL없이 treap을 구현하는 것이 성능 상 한계가 있는 건지,


    10년 전 link
  • Being
    Being

    코드를 들여다본 것은 아닙니다만, STL의 사용 여부와 treap의 성능은 무관할 것 같네요. 전에 코드를 돌려 보았을 때의 속도를 기준으로 생각하면, 시간 복잡도 자체에 문제가 있을 것 같은데 확실치는 않습니다.


    10년 전 link
  • zzerross
    zzerross

    드디어...찾았습니다...

    최다 실패를 기록했지만, 처음으로 가장 빠른 답안에 랭크되어 기쁘네요.

    조언해주신, JongMan님, Being님께
    감사하는 마음, 반성하는 마음으로 오답 정리해봅니다. ㅜ.ㅡ

    1)종만님 지적해 주신,
    전역 rmv()에서 불필요한 검사를 했던 것이 주요 포인트 였습니다.
    조금이라도 능력것 풀어보려고,
    책의 코드를 자세히 보지 않으려고 하는데,
    항상 쉽지 않네요.
    2)그 다음으로 treap insert를 split & merge로 구현했다가,
    TLE를 극복해보자, priority에 따라 leaf에 달아주기만 하도록 했는데,
    계속 insert되는 경우엔,
    이게 더 성능저하를 가져와서,
    전역 rmv() 수정 후에도 TLE를 야기시켰네요.
    3)new를 하는 것과 않하는 것이 100ms 정도 차이나네요.


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.