Prolog query arrangement on efficiency

Hello, I had just read the paper " Research Report AI-1989-08
Efficient Prolog: A Practical Guide" by Michael A. Covington

Here is a portion from the paper of inefficiency reason that I had
also experienced today because of the query arrangement.


Searching takes time, and an efficient program must search
efficiently. In a
knowledge base that lists 1000 gray objects but only 10 horses, the
query
?- horse(X), gray(X).

can be 100 times as fast as the alternative
?- gray(X), horse(X).
because it narrows the range of possibilities earlier.


But I still don't get it, isnt't that at whichever arrangments the
total trial or execution of the query is 1000 times 10 (10000) ? How
does
?- horse(X), gray(X).
Make it more efficient ?


Thanks

Keenlearner wrote:
> Hello, I had just read the paper " Research Report AI-1989-08
> Efficient Prolog: A Practical Guide" by Michael A. Covington
>
> Here is a portion from the paper of inefficiency reason that I had
> also experienced today because of the query arrangement.
>
>
> Searching takes time, and an efficient program must search
> efficiently. In a
> knowledge base that lists 1000 gray objects but only 10 horses, the
> query
> ?- horse(X), gray(X).
>
> can be 100 times as fast as the alternative
> ?- gray(X), horse(X).
> because it narrows the range of possibilities earlier.
>
>
> But I still don't get it, isnt't that at whichever arrangments the
> total trial or execution of the query is 1000 times 10 (10000) ? How
> does
> ?- horse(X), gray(X).
> Make it more efficient ?

There are actually two reasons involved, of which the first has the
greater impact:

1. The effect of a Prolog implementation technique called indexing.
It essentially means that tests are implemented more efficiently than
simply trying all possibilities. In your case that means that
a query like
?- gray(1000).
will finish very quickly because it requires only a constant time
table lookup. But if you write instead
?- gray(X), X=1000.
then this will essentially take linear time, because the gray(X) call
will succeed once for every gray item, and only then we test whether
it is the required one (this is usually called generate-and-test).

The gray(X),horse(X) query has one generater-style call to gray(X),
and then 1000 test-style calls to horse(X), while the horse(X),gray(X)
query has one generator-style call to horse(X) and only 10 test-style
calls to gray(X), and is therefore roughly 100 times faster.


2. If you eliminate the effect of indexing, e.g. by comparing the queries
?- horse(X), gray(Y), X=Y.
and
?- gray(X), horse(Y), X=Y.
you will still see a difference, but it is less dramatic. The reason lies
in the shape of the search trees. The first one has a root node with 10
descendants, each of which has 1000 descendants, giving 10000 leaves.
The second has a root with 1000 descendants, each of which has 10 descendants,
giving 10000 leaves as well. The difference is only in the number of
internal nodes, but these involve certain costs during Prolog execution,
which you can observe.


-- Joachim

> The gray(X),horse(X) query has one generater-style call to gray(X),
> and then 1000 test-style calls to horse(X), while the horse(X),gray(X)
> query has one generator-style call to horse(X) and only 10 test-style
> calls to gray(X), and is therefore roughly 100 times faster.

This explanation, especially the keywords test-style make me
understand that.

>*The first one has a root node with 10
> descendants, each of which has 1000 descendants, giving 10000 leaves.
> The second has a root with 1000 descendants, each of which has 10 descendants,
> giving 10000 leaves as well.

I had been thinking about both of them having the same number of
leaves, so I thought there must be not difference on the efficiency of
both arrangements.

But I got it now,

Thank you very much,
William