Efficient findall() processing?

Question

I have the following structure of "facts".

if( conds, score, idx).

Then I expect to have thousands of them. The 'conds' is a conditions that will be evaluated as the facts are processed. For every fact that is true I store the score and the index in a list for further processing. The general idea is to findall/3 facts and then go over them ...

findall([Cond, Q, Ix], clause(if(Cond, Q, Ix), true), Conds)
check(Conds, True_QIxLst) ...

My worry is that findall/3 would gobble all thousand of facts for every run i.e. use too much memory.

How would I do what findall does, but process the conditions one-by-one. I will still process all the conditions, but I would like to use less memory.

As per "mat" suggestion this seem to work out :

is_true(Q,Ix) :-
   if(Cond, Q, Ix),
   check(Cond).

run(QI) :-
   findall([Q,Ix], is_true(Q,Ix), QI).

score 4 · Accepted Answer · answered Feb 04 '18 at 21:31

4

The key to writing efficient Prolog code is to delegate as much work as possible to the engine.

Everything you do explicitly (i.e., within Prolog) will typically be slower than if the same thing is accomplished by the core engine implicitly. If that isn't the case, it means that there is an opportunity for improvement in the core engine.

In your particular case, if findall/3 would use too much memory, consider whether findall/3 is even necessary for your use case.

How about getting out of the way, and delegating it all to Prolog's built-in backtracking?

true_q_ix(Q, Ix) :-
    if(Cond, Q, Ix),
    cond_is_true(Cond).

No findall/3, no nothing: Just plain backtracking, yielding all Q and Ix for which Cond evaluates to true in your interpretation.

Don't do anything! Nothing!

If necessary, you can still wrap this in findall/3, paying its various costs.

answered Feb 04 '18 at 21:31

mat

40,498
3
51
78

how would i collect Q's and Ix's ? i tried with separate rule calling this one, but search always start from the first "if" – sten Feb 04 '18 at 22:40
1

You can collect `Q` and `Ix` for example with `findall/3`: `findall(Q-Ix, true_q_ix(Q, Ix), QIxs)`. This is now limited to all those `Q` and `Ix` where the conditions are actually true. – mat Feb 04 '18 at 23:13
1

Great! Still, the question somehow remains: Do you really need to collect all solutions? Why? In Prolog, you normally state what holds about a solution, and on backtracking, you get solutions that satisfy these conditions. – mat Feb 04 '18 at 23:22
ooo, i need to pick the best Ix based on the Score, so I can execute corresponding actions. – sten Feb 04 '18 at 23:24
1

OK, I see! It is possible to do this with less space. However, collecting all solutions and picking a minimal one is one way to do it too. – mat Feb 04 '18 at 23:26

Efficient findall() processing?

1 Answers1