파이썬 리스트가 C++ array에 비해 용량을 훨씬 많이 차지하나요?

  • rlakim5521
    rlakim5521

    BLOCKGAME

    아직 파이썬으로 푸신 분이 없어서 파이썬으로 풀어보았는데, 로컬에서 예제는 답을 출력하지만 제출하면 메모리 초과가 납니다.

    의심이 가는 부분은 cache와 block 부분인데, 파이썬의 리스트는 C나 C++의 배열 구조와 근본적으로 다른가요?(링크드 리스트로 짜여졌다거나...)

    # BLOCKGAME
    # Jaekyoung Kim (rlakim5521@naver.com)
    
    global cache
    global blocks
    MAX_INDEX = 33554432
    
    def play(int_board):
        ret = cache[int_board]
        if(ret != -1):
            return ret
        ret = 0
        for block in blocks:
            if(int_board & block == 0):
                if(play(int_board | block) == 0):
                    ret = 1;
                    break;
        cache[int_board] = ret
        return ret
    
    # Main function
    if __name__ == "__main__":
        cache = [-1 for _ in xrange(MAX_INDEX)]
    
        blocks = []
    
        #   . .
        #   # #
        for row in xrange(5):
            for col in xrange(4):
                blocks.append(3 << (row * 5 + col))
    
    
        #   . #
        #   . #
        for row in xrange(4):
            for col in xrange(5):
                blocks.append(33 << (row * 5 + col))
    
        #   # .
        #   # #
        for row in xrange(4):
            for col in xrange(4):
                blocks.append(67 << (row * 5 + col))
    
    
        #   . #
        #   # #
        for row in xrange(4):
            for col in xrange(4):
                blocks.append(35 << (row * 5 + col))
    
        #   # #
        #   . #
        for row in xrange(4):
            for col in xrange(4):
                blocks.append(97 << (row * 5 + col))
    
        #   # #
        #   # .
        for row in xrange(4):
            for col in xrange(4):
                blocks.append(98 << (row * 5 + col))
    
        for _ in range(int(raw_input())):
    
            # Input
            int_board = 0
            for row in xrange(5):
                line = raw_input()
                for col in xrange(5):
                    int_board = int_board << 1
                    if(line[col] == '#'):
                        int_board = int_board | 1
    
            # Output
            if(play(int_board)==1):
                print "WINNING"
            else:
                print "LOSING"
    


    8년 전
2개의 댓글이 있습니다.
  • free-lunch
    free-lunch

    getsizeof로 체크해보니, cache가 297,842,208 byte가 나오네요.
    MAX_INDEX로 cache를 초기화한게 문제인듯 싶습니다.

    python list 구조에 대해서는 아래 블로그를 참고하시면 도움이 될 것 같습니다.
    https://medium.com/@cookatrice/why-python-is-slow-looking-under-the-hood-7126baf936d7#.3vd4s7276


    8년 전 link
  • rlakim5521
    rlakim5521

    친절한 답변 감사합니다^^


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