0

我正在做一些实验来比较 Sicstus Prolog 中的不同标签启发式。

但我不断进入“资源错误：内存不足”。

我很确定我在测试代码中做错了什么。

以下代码将复制我的问题：

:- use_module(library(clpfd)).
:- use_module(library(lists)).

atest( R, C ):-
    X is R * C,
    length( M, X),
    domain( M, 0, X),
    all_distinct( M ),

    statistics(walltime, [_,_SinceLast]),
    labeling( [],M ),
    statistics(walltime, [_,SinceLast]),

    write('Labeling time: '), write(SinceLast),write('ms'),nl.


% Testcode for looping through alot of variations and run one test for each variant
t1:-
    Cm = 1000,
    Cr = 1000,
    (
    for(C,0, Cm),
    param([Cm,Cr])
    do
        (
        for(R, 0, Cr ),
        param([C])
        do
            atest( C, R )
        )
    ).

调用 t1 谓词后不久，我收到“资源错误：内存不足”异常。

我想我应该在调用 atest 释放资源后做点什么？

另外：这是测量标记时间的正确方法吗？有没有更好的方法来做到这一点？

4

2 回答 2

2

您没有做任何严格错误的事情，但您正在尝试运行

length(Xs,N), domain(Xs,0,N), all_distinct(Xs), labeling([],Xs).

对于 N 高达 1000000。系统构建深度为 N 的搜索树，并且必须存储变量的中间状态和每个级别的约束系统。对于大 N，这会占用大量内存，并且很有可能在一次运行大 N 时已经出现内存溢出。

第二个问题是您在递归循环中运行基准测试，即您正在有效地创建一个连接

atest(0,0), ..., atest(1000,1000)

并且由于对 atest/2 的每次调用都通过其第一个解决方案成功并保持其搜索状态，这意味着您正在尝试创建一个具有 250500250000 个级别的搜索树...

最简单的改进是通过将代码更改为once(atest(C,R)). 进一步的改进是在故障驱动的循环中运行基准测试

(
    between(0,Cm,C),
    between(0,Cr,R), 
    once(atest(C,R)),
    fail
;
    true
)

这将更快更快地释放内存，并减少由于垃圾收集而导致的测量失真。

于 2014-02-11T01:31:32.280 回答
1

顶层隐藏替代答案

如果您t1在 SICStus 的顶层 shell 上使用一些较小的值进行测试，您可能会得到错误的印象，即t1只有一个答案/解决方案。然而，这种情况并非如此！所以顶层对你隐藏了其他答案。这是 SICStus 顶层中的一种特殊行为，如果查询不包含变量，则不会显示进一步的答案。但是一共有x！许多标签解决方案，x！对于每个测试用例，其他解决方案的时间是一些随机值。您的内存不足是因为对于每个测试用例，Prolog 都会保留记录以继续为每个测试用例生成下一个解决方案。

循环播放

我不建议使用故障驱动循环进行测试，而是使用以下非常相似但更安全的循环：

\+ (
      between(0, Cm, C),
      between(0, Cr, R),
      \+ atest(C, R)
   ).

与失败驱动循环的最大区别在于，当某些和atest/2意外失败时。在失败驱动的循环中，这基本上不会被注意到，而上述构造将失败。CR

forall/2一些系统为此目的提供谓词。

定时

如果您进行计时，最好只使用列表的第一个元素并计算差异：

statistics(walltime, [T0|_]),
Goal,
statistics(walltime, [T1|_]),
D is T1 - T0.

通过这种方式，目标的替代答案将为您提供更有意义的价值。

于 2014-02-11T10:27:31.107 回答