alswnsalstmd   1년 전

처음 제출했을때에는

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이코드를 쓰지않아서 시간초과가 났었는데 쓰니까 496ms로 통과가 됐습니다. 근데 그게 이렇게 많이 차이나나 궁금해서 찾아보다가 cin으로 입력을 받으면 cout 출력 버퍼를 플러시 하게되서 cin이 많을수록 시간도 많이 차이난다는걸 알게되었습니다. 그래서 고민하다가 버퍼링출력을 찾아 보게 되었고 아래 코드로 수정했습니다.
#include <iostream>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
string str;
int x;
int s = 0;
string result = "";
while (n--)
{
cin >> str;

if (str == "add") {
cin >> x;
s |= (1 << (x - 1));
}
else if (str == "remove") {
cin >> x;
s &= ~(1 << (x - 1));
}
else if (str == "check") {
cin >> x;
(s & (1 << (x - 1)) ? result+="1\n" : result+="0\n");
}
else if (str == "toggle") {
cin >> x;
s ^= (1 << (x - 1));
}
else if (str == "all") {
s = (1 << 20) - 1;
}
else if (str == "empty") {
s = 0;
}
}
cout << result;
return 0;
}
그런데 메모리 초과가 발생했습니다. 최악의 입력의 경우 result 에만 6000001 바이트가 들어가서 메모리 초과가 발생한것 같습니다. 그럼 이런경우에는 시간을 더 줄일수 없는건지 궁금합니다.

dongwanpianist   1년 전

현 시점에서 이미 해당 코드를 더 손보셔서 추가 제출(98509018)을 통해 질문이 해결된 것 같지만,

스스로 추가 제출시 개선하신 내용은

  • std::string 대신 char[] 사용 (즉 C++식의 class가 아닌 C식의 char배열로서의 구식 NULL-terminated string)
  • 더불어 입력받은 영어단어 문자열의 첫번째 문자 혹은 첫 두 문자만 비교하기.
  • std::istream (cin), std::ostream (cout) 대신 scanf, printf 사용.

으로 보입니다. 그런데 코드를 이런 식으로 쓰면 사실상 C 코드죠? C++가 아니라.... C++에서 돌아가는 합법적인 C++코드이긴 한데 말이죠..

여기서 최적화를 위해 더 제안할 수 있는 점은 (완전한 정답이란 건 없습니다. 그냥 아이디어가 필요하신 것 같아서 제안만 드립니다.)

  • 입력 명령을 받는 변수 (std::string str): char c1, c2; 이렇게 문자 공간 딱 두 개만 사용하여 두 글자를 입력받아 분기를 처리하고, 그 후 나머지는 '\n'이 입력될 때까지 복사하지 않고 싸그리 무시하는 기능을 사용해보세요. cin.ignore(최대버퍼크기, 끝나는문자) 함수입니다. 이 문제에서는 7글자 안으로 끝날게 확실하니 구현은 cin >> c1 >> c2; cin.ignore(8, '\n');처럼 쓸 수 있겠네요.
  • 29번 줄: "1\n", "0\n"이라는 string literal은 그 자체로 NULL-terminated string이라서 각각 char[3] mystring001 = {'1', '\n', '\0'}, char[3] mystring002 = {'0', '\n', '\0'} 이런 식의 구조를 가집니다. 이런 문자열이 cout으로 들어가면 언제 끝날 지 모르니 '\0'이 나올 때까지 한글자 한글자 전달하며 loop를 실행합니다. 이런 과정을 없애기 위해서 짧은 문자열의 경우 그냥 따옴표 하나만 써서 문자 하나씩 전달할 수 있습니다. 문자열을 간단한 문자로 바꾸면 cout << (s & (1 << (x - 1)) ? '1' : '0') << '\n'; 이렇게 공통되는 '\n'을 뒤로 뺄 수 있습니다. char[](string)대신 단순한 char 자료형이 cout으로 가면 찰나의 순간 정도라도 더 빠르게 처리할 수 있습니다. 이게 쌓이고 쌓이면 유의미한 시간이 되겠네요.
  • 메모리 초과가 된 코드에서 std::string result의 길이가 커지며 발생하는 문제:
    std::string의 길이가 가변적으로 늘어나는 원리는 std::vector와 동일하다고 알고 있습니다. 즉 2의 배수를 넘어갈 때마다 새로운 공간을 할당하여 통째로 이사를 시킵니다. 예를 들어 char[8] "1234567" 에서 문자 하나 '8'을 더하면 char[16]이라는 새로운 공간을 만들고 "1234567"을 모두 복사하고 '8'을 붙이는 작업을 거칩니다. 그정도 되면 string을 다양한 길이로 넣었다 뺐다 하는 연산이 자유롭기 때문인데, 문자열 공간을 가급적 짧게 유지하여 최척화하며 동시에 append연산에 따라 늘어나기도 해야하는 이중적인 문제를 std::string에서는 이렇게 다루는 것입니다. char[65536]에서 char[131072]로 늘어날 때는 또 시간이 얼마나 걸릴지, 그것보다 2배 더 늘릴 땐 또 시간이 얼마나 걸릴지 생각해보세요. 이렇게 특정 길이마다 전체 복사를 하는 시간을 줄이기 위해서 std::string과 std::vector에 공통적으로 reserve(크기)라는 함수가 있으니 문자열을 선언하자마자 큰 숫자를 주어 불필요한 깨작깨자 복사과정을 피할 수 있습니다. 이 공간 크기는 capacity()함수로 읽을 수 있습니다. 그리고 계속 std::string을 사용하고 싶으시다면 중간에 일정 길이에 도달했을 때마다 cout으로 보내고 비워버리는 동작을 추가하시기 바랍니다. 출력 자동화 함수를 따로 만드는 것이죠.
  • std::string 말고 다른 클래스 가능성:
    메모리 초과가 된 코드를 보니 왜 그런 식으로 코드를 바꾸려 하셨는지 잘 알겠습니다. CLI의 출력기능 특성상 std::ostream이 '\n'을 감지하면 자동으로 지금까지 내부에 차곡차곡 쌓은 stream을 화면밖으로 flush()하며 스크린을 업데이트하고 stream 내부를 싹 비우는 과정을 거칩니다. 그것이 바로 stream과 flush의 원리입니다. 반대로 말하면, '\n'이 나오기 전까진 flush하지 않습니다. (예를 들어 cout << A+B << segfault_error << '\n'; 이런 코드의 중간에 에러가 발생하여 프로그램이 종료되면, A+B연산까지는 하지만 아직 '\n'에 도착하지 않아서 해당 줄 전체가 flush되지 않아서 A+B의 결과가 화면에 뜨지 않고 종료됩니다.) 이걸 활용하면, '\n'을 할때마다 매번 flush에 시간을 할애하는 std::ostream을 쓰지 않고 다른 방법을 찾을 수 있습니다. 대표적으로 <sstream> 헤더가 주는 클래스인 std::stringstream 혹은 std::ostringstream입니다. 구현은 std::stringstream myoutput; 이렇게 정의하시고 myoutput << 결과 << '\n' << 연산결과 << '\n'; 이렇게 std::cout 대신 myoutput에 차곡차곡 쌓으신 후에 나중에 단 한번의 전달, std::cout << myoutput; 하시면 됩니다. 이 과정에서 위의 문제처럼 메모리 초과가 발생한다면 마찬가지로 중간에 일정 길이에 도달했을때마다 cout으로 flush하고 stringstream을 비우는 작업을 여러번 나눠서 할 수 있겠습니다. 이건 java언어의 java.lang.StringBuilder와 비슷한 작동입니다. java언어 사용자들은 출력할 때 이렇게 쌓았다가 한번에 풀어버리는 동작을 즐겨 사용한답니다.

뭔가 착착 정리해서 채찍피티 같지만 정성들여 모든 글자 작성했으니 꼭 주의깊게 읽어주세요.

alswnsalstmd   1년 전

한글자 한글자 정성들여 답변해주셔서 감사합니다. 

말해주신 방법들 한번 사용해서 해보겠습니다.

정말 감사합니다!

댓글을 작성하려면 로그인해야 합니다.