CODEWITHSUNDEEP
prologclpfd
Torben Pi Jensen
Torben Pi Jensen

Reputation: 870

Speed issue with code

I have an issue with a solution, which very fast becomes slow.

The code below determines if an array of "rules" are valid - and example could be 

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

which should be false as it is not possible to select 4 (2+2) distinct numbers from the lists, and 

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

is hence true.

For very small queries this performs fine, but it becomes slow very fast. Can anyone point me in a direction of how to speed up this code, if possible.

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 ).

UPDATE

So, switching to CLPFD for this piece of logic makes that part much faster. But, I cannot seem to wrap my head around how to make the rest of my application use CLPFD also so it will work for the whole application.

I have a list of userRequests: 

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)])] )

and then I have a list of rule groups which is the structure from my problem wrapped in a 

ruleGroup(Day, [rules])

So what I do is to change the state of a userRequest to approved is that I take the first request and approve it, and hence removing the userId from all ruleGroups that has the day overlapping the request because that user no longer is able to fulfill the rule that day.

I have big troubles seeing how I can update these domains removing the user from them.

The issue is that I have been working on lists and not domains, and have a lot of logic around them I have to change as well.

Upvotes: 3

Views: 106

Answers (1)

mat
mat

Reputation: 40768

Check out CLP(FD) constraints. Many Prolog systems, including SICStus Prolog and also SWI, ship with a powerful constraint called all_distinct/1: It is true iff all variables from the given list can be assigned distinct integers.

For example, let us state your first query in terms of CLP(FD):

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

From this, we see that there is no admissible solution.

In the second case though, we get:

?- 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.

i.e., a residual program that is declaratively equivalent to the original query, and from which in this particular case we know that there is indeed a solution. (Note: This is possible here because all_distinct/1 implements domain consistency.)

Hence, in your rule validation, you can write code that uses CLP(FD) constraints to detect inconsistencies, which is typically much more efficient than naive approaches. I leave implementing this translation as an easy exercise.

Upvotes: 4

Related Questions