为什么这个Rascal模式匹配代码要占用这么多内存和时间

Question

我正试图在Rascal中编写一段我认为非常简单的代码：测试列表A是否包含列表B。

从一些非常基本的代码开始创建字符串列表

public list[str] makeStringList(int Start, int End)
{
    return [ "some string with number <i>" | i <- [Start..End]];
}
public list[str] toTest = makeStringList(0, 200000); 

我的第一次尝试受到了导师中排序示例的"启发"：

public void findClone(list[str] In,  str S1, str S2, str S3, str S4, str S5, str S6)
{
    switch(In)
    {
        case [*str head, str i1, str i2, str i3, str i4, str i5, str i6, *str tail]:   
        {
            if(S1 == i1 && S2 == i2 && S3 == i3 && S4 == i4 && S5 == i5 && S6 == i6)
            {
                println("found duplicatent<i1>nt<i2>nt<i3>nt<i4>nt<i5>nt<i6>");
            }
            fail;
         }   
         default:
            return;
    }
}

不是很漂亮，但我希望它能起作用。不幸的是，代码运行了大约30秒，然后因"内存不足"错误而崩溃。

然后我尝试了一个更好看的替代方案：

public void findClone2(list[str] In, list[str] whatWeSearchFor)
{
    for ([*str head, *str mid, *str end] := In)
    if (mid == whatWeSearchFor)
        println("gotcha");
} 

具有大致相同的结果（在内存耗尽之前似乎运行了更长的时间）

最后，我用for循环尝试了一种"好的旧"C风格的方法

public void findClone3(list[str] In, list[str] whatWeSearchFor)
{
    cloneLength = size(whatWeSearchFor);
    inputLength = size(In);
    if(inputLength < cloneLength) return [];
    loopLength = inputLength - cloneLength + 1;
    for(int i <- [0..loopLength])
    {
        isAClone = true;
        for(int j <- [0..cloneLength])
        {
            if(In[i+j] != whatWeSearchFor[j])
                isAClone = false;
        }
        if(isAClone) println("Found clone <whatWeSearchFor> on lines <i> through <i+cloneLength-1>");   
    }
}

令我惊讶的是，这一款很有魅力。没有内存不足，并在几秒钟内得到结果。

我知道我的前两次尝试可能创建了很多临时字符串对象，这些对象都必须进行垃圾收集，但我不敢相信唯一有效的解决方案是最好的解决方案。

任何建议都将不胜感激。

我的相关eclipse.ini设置是

-XX:MaxPermSize=512m
-Xms512m
-Xss64m
-Xmx1G

Answer 1

我们需要看看为什么会发生这种情况。请注意，如果您想使用模式匹配，这可能是一种更好的编写方法：

public void findClone(list[str] In,  str S1, str S2, str S3, str S4, str S5, str S6) {
    switch(In) {
        case [*str head, S1, S2, S3, S4, S5, S6, *str tail]: {
            println("found duplicatent<S1>nt<S2>nt<S3>nt<S4>nt<S5>nt<S6>"); 
        } 
        default: 
            return; 
    } 
}

如果你这样做，你就可以利用Rascal的匹配器直接找到匹配的字符串，而你的第一个例子中任何字符串都会匹配，但你需要使用一些单独的比较，看看匹配是否代表了你想要的组合。如果我在110145到110150上运行这个，它需要一段时间，但可以工作，而且它似乎不会超出你分配给它的堆空间

此外，您使用fail是否有原因？这是为了继续搜索吗？

Answer 2

正如Mark Hills所说，这是一个算法问题。在Rascal中，一些短代码仍然可能包含许多嵌套循环，几乎是隐含的。基本上，在列表中的模式侧使用的新鲜变量上的每个*拼接运算符都会生成一个级别的循环嵌套，除了最后一个，它只是列表的其余部分。

在findClone2的代码中，您首先生成子列表的所有组合，然后使用if构造对其进行筛选。所以这是一个正确的算法，但可能很慢。这是您的代码：

void findClone2(list[str] In, list[str] whatWeSearchFor)
{
    for ([*str head, *str mid, *str end] := In)
    if (mid == whatWeSearchFor)
        println("gotcha");
}

您可以看到它在In上有一个嵌套循环，因为它在模式中有两个有效的*运算符。因此，代码在O(n^2)中运行，其中n是In的长度。即，对于In列表的大小，它具有二次运行时行为。In是一个很大的列表，所以这很重要。

在下面的新代码中，我们在生成答案时首先进行过滤，使用更少的代码行：

public void findCloneLinear(list[str] In, list[str] whatWeSearchFor)
{
    for ([*str head, *whatWeSearchFor, *str end] := In)
        println("gotcha");
} 

第二个CCD_ 11操作符不生成新循环，因为它不是新鲜的。它只是将给定的列表值"粘贴"到模式中。所以现在实际上只有一个有效的*，它生成一个循环，这是head上的第一个循环。这个使算法在列表上循环。第二个*测试whatWeSearchFor的元素是否都在head之后的列表中（这在whatWeSearchFor的大小上是线性的，然后最后一个*_刚好完成列表，允许更多的东西跟随

有时知道克隆在哪里也很好：

public void findCloneLinear(list[str] In, list[str] whatWeSearchFor)
{
    for ([*head, *whatWeSearchFor, *_] := In)
        println("gotcha at <size(head)>");
} 

Rascal还没有一个优化编译器，它可能会在内部将您的算法转换为等效的优化算法。因此，作为一名Rascal程序员，你仍然需要知道循环对算法复杂性的影响，并知道*是循环的一个非常短的符号。