c++ - 递归字符串转换

Question

编辑:我做了主要更改，使用迭代器跟踪位和字符串中的连续位置，并通过 const ref 传递后者。现在，当我多次将示例输入复制到自身上以测试时钟时，对于非常长的位和字符串甚至多达 50 行的示例输入，一切都在 10 秒内完成。但是，当我提交时，CodeEval 说该过程在 10 秒后中止。正如我所提到的，他们不共享他们的输入，所以现在样本输入的“扩展”起作用了，我不确定如何进行。非常感谢任何关于额外改进以提高我的递归性能的想法。

注意:记忆化是一个很好的建议，但我不知道在这种情况下如何实现它，因为我不确定如何在静态查找表中存储位到字符的相关性。我唯一想到的是将位值转换为相应的整数，但是对于长位串来说，这有整数溢出的风险，而且计算起来似乎需要很长时间。对于此处的记忆化的进一步建议也将不胜感激。

这实际上是适度的 CodeEval 挑战之一。他们不共享中等挑战的样本输入或输出，但输出“失败错误”只是说“10 秒后中止”，所以我的代码在某处挂起。

任务很简单。您将文件路径作为单个命令行参数。文件的每一行将包含一系列 0 和 1 以及一系列 A 和 B，以空格分隔。你要根据以下两条规则判断二进制序列是否可以转化为字母序列:

1) 每个0都可以转换为As的任意非空序列(如'A'、'AA'、'AAA'等)

2) 每个 1 都可以转换为 As 或 B 的任何非空序列(例如，'A'、'AA' 等，或 'B'、'BB' 等)(但不是混合的字母)

约束条件是最多处理文件中的 50 行，二进制序列的长度为 [1,150]，字母序列的长度为 [1,1000]。

最明显的起始算法是递归执行此操作。我想到的是对于每一位，首先折叠整个下一个允许的字符组，测试缩短的位和字符串。如果失败，一次从被杀死的角色组中添加一个角色，然后再次调用。

这是我的完整代码。为简洁起见，我删除了 cmd 行参数错误检查。

#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;
}

他们给出了以下测试用例，我的代码正确解决了这些用例:

示例输入:

1| 1010 AAAABBBBAAAA

2| 00 AAAAAA

3| 01001110 AAAABAAABBBBBBAAAAAAA

4| 1100110 BBAABABBA

正确的输出:

1|是的

2|是的

3|是的

4|否

由于转换是可能的，当且仅当它的拷贝存在时，我尝试将每个二进制和字母序列多次复制到自身上，并查看时钟如何运行。即使对于非常长的位和字符串以及许多行，它也能在 10 秒内完成。

我的问题是:由于 CodeEval 仍然说它的运行时间超过 10 秒，但他们不分享他们的输入，是否有人有任何进一步的建议来提高此递归的性能？或者可能是一种完全不同的方法？

预先感谢您的帮助!

Answer 1

这是我发现的:

通过常量引用传递
字符串和其他大型数据结构应通过常量引用传递。
这允许编译器将指针传递给原始对象，而不是复制数据结构。

调用函数一次，保存结果
您正在调用 bits.length()两次。您应该调用一次并将结果保存在常量变量中。这允许您在不调用函数的情况下再次检查状态。

对于时间紧迫的程序来说，函数调用是昂贵的。

使用常量变量
如果您不打算在赋值后修改变量，请使用 const在声明中:

const char curr_char_type = chars[0];

const允许编译器执行更高阶的优化并提供安全检查。

改变数据结构
由于您可能在字符串中间执行插入，因此您应该为字符使用不同的数据结构。 std::string数据类型可能需要在插入后重新分配并将字母进一步向下移动。使用 std::list<char> 插入速度更快因为链表只交换指针。可能会有折衷，因为链表需要为每个字符动态分配内存。

在字符串中保留空间
当您创建目标字符串时，您应该使用一个构造函数来为最大大小的字符串预分配或保留空间。这将防止 std::string从重新分配。重新分配的成本很高。

不要删除
你真的需要删除字符串中的字符吗？ 通过使用开始和结束索引，您可以覆盖现有字母而不必删除整个字符串。 部分删除是昂贵的。完全删除不是。

如需更多帮助，请在 StackExchange 上发布代码审查。