Ошибка скорости с кодом

Question

У меня проблема с решением, которое очень быстро становится медленным.

Приведенный ниже код определяет, является ли массив «правил» действуют - и примером может быть

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

, который должен быть ложным, поскольку это не возможно, чтобы выбрать 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). 

---

UPDATE

Таким образом, переход на CLPFD для этой части логики делает эту часть гораздо быстрее. Но я не могу представить себе, как сделать остальную часть моего приложения, используя CLPFD, так что он будет работать для всего приложения.

У меня есть список 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)])]) 

, а затем у меня есть список групп правил, который является структурой из моей проблемы, завернутая в

ruleGroup(Day, [rules]) 

Так что я делаю, измените состояние одобрения userRequest на то, что я беру первый запрос и одобряю его и, следовательно, удаляю userId из всех групп правил, у которых есть день, перекрывающий запрос, потому что этот пользователь больше не может выполнить правило в тот день.

У меня большие проблемы, видя, как я могу обновить эти домены, удаляя пользователя из них.

Проблема в том, что я работаю над списками, а не доменами, и у них много логики вокруг них, я тоже должен меняться.

Answer 1

Проверьте ограничения CLP (FD). Многие системы Prolog, в том числе SICStus Prolog, а также SWI, поставляются с мощным ограничением all_distinct/1: true 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) для обнаружения несоответствий, что обычно намного эффективнее, чем наивные подходы. Я оставляю реализацию этого перевода как легкое упражнение.