rascal - 为什么这段 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 duplicate\n\t<i1>\n\t<i2>\n\t<i3>\n\t<i4>\n\t<i5>\n\t<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 duplicate\n\t<S1>\n\t<S2>\n\t<S3>\n\t<S4>\n\t<S5>\n\t<S6>"); 
        } 
        default: 
            return; 
    } 
}

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

此外，您使用 fail 是否有原因？这是要继续寻找吗？