메모리 절약 vs 빠른 속도

  • 2000spot
    2000spot

    메모리 절약을 하면 물론 속도에도 긍정적인 영향을 줄 수 있지만 제가 궁금한 것은 아래와 같습니다.

    메모리 절약을 위해 동적할당을 이용하는 것이 좋을까요?
    아니면 낭비되는 공간이 많더라도 최대한 낭비되는 공간이 적게 추측하여서 정적배열을 사용하는 것이 좋을까요?
    문제는 어떻게해서든 풀리겠지만 알고리즘 문제를 풀 때 어떤 방법이 효율적일지에 대해 궁금해서 질문 올립니다.


    4년 전
5개의 댓글이 있습니다.
  • wookayin
    wookayin

    짧은 답변: 걱정마시고 동적배열 쓰시면 됩니다.

    긴 답변:
    가령 n=10만 정도의 문제를 푼다고 합시다. int a[100000]; 와 같은 정적 배열 써도 되고, vector<int> a; 처럼 동적 배열 써도 메모리 사용량은 사실 큰 차이가 없습니다. 속도차이가 있긴 하지만 최적화가 잘 되기 때문에 특별한 경우를 제외하면 무시할 만한 수준이고요.

    적어도 프로그래밍 대회나 알고리즘 문제풀이에 한정한다면, 메모리나 속도를 그렇게까지 심각하게 걱정하지는 않아도 됩니다. 물론 메모리도 적게 쓰면 좋고 속도도 빠르면 좋겠지만, 일단 기본적으로는 제한 메모리(128MB 정도)나 시간제한(수 초) 안에 들어오기만 하면 되니까요. 이 제한을 만족시키기 위해 가끔은 메모리도 줄여야하고 속도 최적화도 열심히 해야하지만, 그건 메모리와 시간 조건이 빡빡할 때 이야기이고 대부분의 경우는 크게 신경을 쓰지 않아도 되며 (대부분은 알고리즘이나 복잡도 차이에서 결정되고) 적어도 동적배열과 정적배열의 차이에서 발생하는 문제는 아닙니다.

    저는 개인적으로는 오히려 말씀하신 기준이 아닌, 효율적이고 간결한 코드를 어떻게 작성할 수 있는가가 더 중요한 문제라고 봅니다. 프로그래밍 대회 그리고 일반적인 프로그래밍에서도, 저런 자잘한 micro-optimization 을 잘하는 것보다는 버그 가능성이 적은 코드를 얼마나 빠르게 정확하게 알아보기 쉽게 작성하느냐가 더 중요합니다. 그러다가 속도나 메모리에 크리티컬한 부분이 있다면 그 부분을 집중하여 최적화를 하시면 되겠죠. 이러한 관점에서 동적배열은 많은 장점을 갖고 있습니다. 가령 잘못된 index를 참조할 때 에러가 나기 때문에 잘못된 프로그램의 로직을 빨리 잡을 수 있고, 동적 배열들을 사용하게 되면 STL vector 와 같은 각종 컨테이너의 객체지향적인 특성들 덕분에 코드를 깔끔하게 유지하는 데에도 도움이 됩니다. 참고로 동적배열을 쓰라고 말씀드렸을 때에는 STL의 vector 같은 것을 사용하는게 좋다는 의미이지, malloc()new int[] 를 말하는건 아닙니다. 이런 low-level 동적 배열들을 직접 사용하지는 마세요)


    4년 전 link
  • 2000spot
    2000spot

    아 그럼 동적배열은 STL을 사용할 때 사용하고 malloc나 new를 사용하는 동적할당은 사용하지 말란 말씀이군요? low-level 동적할당을 왜 사용하면 안되나요?? 잘못사용했을 때 위험해서 그런건가요?


    4년 전 link
  • astein
    astein

    low-level 동적할당을 사용하는 경우에 메모리 해제를 하지 않아서 발생하는 메모리 초과, 또는 잘못된 인덱스 참조로 인한 메모리 침범이 일어났을 때 예상하지 못한 동작 등 예외상황이 발생하는 경우의 디버깅이 쉽지 않기 때문입니다.


    4년 전 link
  • 2000spot
    2000spot

    네 감사합니다^^


    4년 전 link
  • Being
    Being

    예를 들어 std::vector의 경우 amortized O(1)이고, 메모리 할당 알고리즘들도 대체로 O(1)로 간주해도 되므로 동적 할당을 하더라도 상수배 느리거나 빨라질 뿐입니다. 상수배 속도에 영향을 받는 문제들도 물론 가끔 있습니다만, 틀리지만 빠른 코드 <<<<<<<<<< 맞지만 느린 코드 << 맞고 빠른 코드임에는 변함이 없습니다.


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