代码速度问题

Question

我有一个解决方案的问题，它很快变得很慢。

下面的代码确定 "rules" 的数组是否有效 - 例如

rules_valid([rule(2,[1,2,3]), rule(2,[1,2,3])],[])

这应该是错误的，因为不可能从列表中 select 4 (2+2) 个不同的数字，并且

rules_valid([rule(2,[1,2,3]), rule(2,[3,4,5])],[])

因此是正确的。

对于非常小的查询，这执行得很好，但很快就会变慢。如果可能的话，任何人都可以指出如何加速此代码的方向。

rules_valid([], _).
rules_valid( [ rule(RequiredUserNumber, UserIds) | RemainingRules ], UsedUserIds) :-
    n_users_from_rule(RequiredUserNumber, UserIds, UsedUserIds, UpdatedUsedUserIds),
    rules_valid(RemainingRules, UpdatedUsedUserIds).

n_users_from_rule(0, _, UsedUserIds, UsedUserIds).
n_users_from_rule(RequiredUserNumber, UserIds, UsedUserIds, UpdatedUsedUserIds) :-
    0 < RequiredUserNumber,
    UpdatedRequiredUserNumber is RequiredUserNumber - 1,
    select(UserId, UserIds, UpdatedUserIds),
    not(member(UserId, UsedUserIds)),
    n_users_from_rule(UpdatedRequiredUserNumber, UpdatedUserIds, [ UserId | UsedUserIds ] , UpdatedUsedUserIds ).

更新

因此，为这部分逻辑切换到 CLPFD 会使该部分更快。但是，我似乎无法全神贯注于如何让我的应用程序的其余部分也使用 CLPFD，以便它适用于整个应用程序。

我有一个用户请求列表：

userRequest(UserId, PrioritizedRequestList) 
request(State, PeriodList)
period(FromDay, ToDay)
i.e.
userRequest( 1 , [request(State,[period(1,5)]),request(State,[period(1,2),period(1,5)])] )

然后我有一个规则组列表，它是我的问题的结构，包裹在

ruleGroup(Day, [rules])

所以我要做的是将 userRequest 的状态更改为已批准，即我接受第一个请求并批准它，因此从与请求重叠的日期的所有规则组中删除 userId，因为该用户不再当天就能完成规则

我很难理解如何更新这些域以从中删除用户。

问题是我一直在处理列表而不是域，并且围绕它们有很多逻辑我也必须更改。

Answer 1

查看 CLP(FD) 约束。许多 Prolog 系统，包括 SICStus Prolog 和 SWI，都带有一个强大的约束，称为 all_distinct/1：这是真的 iff 给定列表中的所有变量都可以赋值 不同的个整数。

例如，让我们根据 CLP(FD) 陈述您的第一个查询：

?- length(Ls, 4), Ls ins 1..3, all_distinct(Ls).
false.

由此可见，没有可接受的解决方案。

在第二种情况下，我们得到：

?- length(Ls, 4), Ls ins 1..5, all_distinct(Ls).
Ls = [_G3409, _G3412, _G3415, _G3418],
_G3409 in 1..5,
all_distinct([_G3409, _G3412, _G3415, _G3418]),
_G3412 in 1..5,
_G3415 in 1..5,
_G3418 in 1..5.

即，一个在声明上等同于原始查询的残差程序，在这种特殊情况下，我们从中知道确实有一个解决方案。（注意：这在这里是可能的，因为 all_distinct/1 实现了域一致性。）

因此，在您的规则验证中，您可以编写使用 CLP(FD) 约束来检测不一致的代码，这通常比单纯的方法更有效。我把实现这个翻译作为一个简单的练习。

代码速度问题

Speed issue with code

prolog

clpfd