Prolog，测试标记启发式 [英] Prolog, testing labeling heuristics

问题描述

我正在进行一些实验，以比较 Sicstus Prolog 中的不同标记启发式方法.

I'm working on some experiments for comparing different labeling heuristics in Sicstus Prolog.

但我不断进入资源错误:内存不足".

But I keep getting into 'Resource error: insufficient memory'.

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

I'm pretty sure I'm doing something wrong in my testcode.

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

The following code will replicate my problem:

:- 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 谓词后不久，我收到资源错误:内存不足"异常.

A short time after I call the t1 predicate, I get a 'Resource error: insufficient memory' exception.

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

I guess I should do something after I call atest to release resources?

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

Also: Is this the correct way to measure labeling-time? Any better way to do this?

推荐答案

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

You are not doing anything strictly wrong, but you are trying to run

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

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

for N up to 1000000. The system constructs a search tree with depth N, and has to store intermediate states of the variables and the constraint system for each level. This takes a lot of memory for large N, and it is quite possible that you get a memory overflow already for a single run with large N.

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

The second issue is that you are running your benchmarks in a recursive loop, i.e. you are effectively creating a conjunction

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

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

and since each call to atest/2 succeeds with its first solution and keeps its search state around, this means you are trying to create a search tree with 250500250000 levels...

最简单的改进是通过将代码更改为 once(atest(C,R)) 来减少第一个解决方案后的每次搜索.进一步的改进是在故障驱动循环

The simplest improvement is to cut each search after the first solution by changing your code to once(atest(C,R)). A further improvement is to run the benchmarks in a failure-driven loop

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

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

which will free memory sooner and faster, and reduce distortion of your measurements due to garbage collection.

这篇关于Prolog，测试标记启发式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！