편집 : 비트와 문자열의 연속적인 위치를 추적하고 후자를 const ref로 전달하기 위해 반복자를 사용하는 것이 주요 변경되었습니다. 이제 시계를 테스트하기 위해 샘플 입력을 여러 번 복사하면 모든 것이 실제로 긴 비트와 문자열 및 심지어 최대 50 줄의 샘플 입력까지 10 초 내에 완료됩니다. 하지만 여전히 제출할 때 CodeEval은 프로세스가 10 초 후에 중단되었다고 말합니다. 내가 언급했듯이, 그들은 입력을 공유하지 않으므로 샘플 입력 작업의 "확장"이 어떻게 진행될 지 확신하지 못합니다. 재귀적인 성능을 향상시키기위한 추가 개선에 대한 생각은 대단히 감사하겠습니다.재귀 적 문자열 변환
참고 : Memoization은 좋은 제안 이었지만 정적 look-up 테이블에 bit-to-char 상관 관계를 저장하는 방법을 모르기 때문에이 경우 구현하는 방법을 이해할 수 없었습니다. 내가 생각한 유일한 것은 비트 값을 해당 정수로 변환하는 것이지만 긴 비트 문자열의 경우 정수 오버플로가 발생할 위험이 있으며 계산하는 데 너무 오래 걸리는 것처럼 보입니다. 여기 memoization에 대한 제안은 크게 감사 할 것입니다.
이것은 실제로 적절한 CodeEval 과제 중 하나입니다. 그들은 중대한 문제를 위해 샘플 입력이나 출력을 공유하지 않지만 출력 "실패 오류"는 단순히 "10 초 후에 중단되었습니다"라고 말하면서 코드가 어딘가에서 멈추게됩니다.
할당은 간단합니다. 단일 명령 행 인수로 파일 경로를 사용합니다. 파일의 각 행에는 공백으로 구분 된 0과 1의 순서와 As와 Bs의 순서가 포함됩니다. 다음 두 규칙에 따라 이진 시퀀스를 문자 시퀀스로 변환 할 수 있는지 여부를 결정해야합니다.
1) 각 0은 비어 있지 않은 As 시퀀스 (예 : 'A', 'AA ','AAA '등)
2) 각 1을 As 또는 B의 비어 있지 않은 시퀀스 (예 :'A ','AA '등 또는'B ' BB '등) (글자가 섞이지는 않음)
제약 조건은 파일에서 최대 50 줄을 처리하고 바이너리 시퀀스의 길이는 [1,150]이고 문자 시퀀스의 길이는 in [1,1000].
가장 확실한 시작 알고리즘은이 작업을 재귀 적으로 수행하는 것입니다. 내가 생각해내는 것은 각 비트마다 다음에 허용되는 문자 그룹 전체를 축소하고, 단축 된 비트와 문자열을 테스트하는 것입니다. 실패하면 한 번에 살해 된 문자 그룹의 문자 하나를 다시 추가하고 다시 호출하십시오.
여기 내 코드가 있습니다. 간결함을 위해 cmd 행 인수 오류 검사를 제거했습니다.|
1 :
샘플 입력 :
#include <iostream>
#include <fstream>
#include <string>
#include <iterator>
using namespace std;
//typedefs
typedef string::const_iterator str_it;
//declarations
//use const ref and iterators to save time on copying and erasing
bool TransformLine(const string & bits, str_it bits_front, const string & chars, str_it chars_front);
int main(int argc, char* argv[])
{
//check there are at least two command line arguments: binary executable and file name
//ignore additional arguments
if(argc < 2)
{
cout << "Invalid command line argument. No input file name provided." << "\n"
<< "Goodybe...";
return -1;
}
//create input stream and open file
ifstream in;
in.open(argv[1], ios::in);
while(!in.is_open())
{
char* name;
cout << "Invalid file name. Please enter file name: ";
cin >> name;
in.open(name, ios::in);
}
//variables
string line_bits, line_chars;
//reserve space up to constraints to reduce resizing time later
line_bits.reserve(150);
line_chars.reserve(1000);
int line = 0;
//loop over lines (<=50 by constraint, ignore the rest)
while((in >> line_bits >> line_chars) && (line < 50))
{
line++;
//impose bit and char constraints
if(line_bits.length() > 150 ||
line_chars.length() > 1000)
continue; //skip this line
(TransformLine(line_bits, line_bits.begin(), line_chars, line_chars.begin()) == true) ? (cout << "Yes\n") : (cout << "No\n");
}
//close file
in.close();
return 0;
}
bool TransformLine(const string & bits, str_it bits_front, const string & chars, str_it chars_front)
{
//using iterators so store current length as local const
//can make these const because they're not altered here
int bits_length = distance(bits_front, bits.end());
int chars_length = distance(chars_front, chars.end());
//check success rule
if(bits_length == 0 && chars_length == 0)
return true;
//Check fail rules:
//1. next bit is 0 but next char is B
//2. bits length is zero (but char is not, by previous if)
//3. char length is zero (but bits length is not, by previous if)
if((*bits_front == '0' && *chars_front == 'B') ||
bits_length == 0 ||
chars_length == 0)
return false;
//we now know that chars_length != 0 => chars_front != chars.end()
//kill a bit and then call recursively with each possible reduction of front char group
bits_length = distance(++bits_front, bits.end());
//current char group tracker
const char curr_char_type = *chars_front; //use const so compiler can optimize
int curr_pos = distance(chars.begin(), chars_front); //position of current front in char string
//since chars are 0-indexed, the following is also length of current char group
//start searching from curr_pos and length is relative to curr_pos so subtract it!!!
int curr_group_length = chars.find_first_not_of(curr_char_type, curr_pos)-curr_pos;
//make sure this isn't the last group!
if(curr_group_length < 0 || curr_group_length > chars_length)
curr_group_length = chars_length; //distance to end is precisely distance(chars_front, chars.end()) = chars_length
//kill the curr_char_group
//if curr_group_length = char_length then this will make chars_front = chars.end()
//and this will mean that chars_length will be 0 on next recurssive call.
chars_front += curr_group_length;
curr_pos = distance(chars.begin(), chars_front);
//call recursively, adding back a char from the current group until 1 less than starting point
int added_back = 0;
while(added_back < curr_group_length)
{
if(TransformLine(bits, bits_front, chars, chars_front))
return true;
//insert back one char from the current group
else
{
added_back++;
chars_front--; //represents adding back one character from the group
}
}
//if here then all recursive checks failed so initial must fail
return false;
}
그들은 내 코드가 올바르게 해결하는, 다음 테스트 케이스를 제공 1010 AAAAABBBBAAAA
2 | 00 AAAAAA
3 | 01001110 AAAABAAABBBBBBAAAAAAA
4 | 1100110 BBAABABBA
올바른 출력 :
1 | 예
2 | 예
3 | 예
4 | 아니
변환이 가능하기 때문에 사본이있는 경우에만 각 바이너리와 문자 시퀀스를 여러 번 복사하고 시계가 어떻게 나타나는지 보았습니다. 매우 긴 비트와 문자열 및 많은 줄까지도 10 초 이내에 끝났습니다.
내 질문은 : CodeEval은 여전히 10 초 이상 실행되지만 입력 내용을 공유하지 않는다고 말하면 누구나이 재귀의 성능을 향상시키기위한 제안 사항이 있습니까? 아니면 전혀 다른 접근 방식일까요?
도움을 주셔서 감사합니다.
'const'참조로 문자열을 전달하여 데이터 구조를 복사하는 데 소요되는 시간을 줄입니다. –
'bits.length()'를 두 번 확인합니다. 함수 호출은 실행하는 데 시간이 걸립니다. 상태가 필요하면 주먹 호출로 변수에 복사하십시오. –