Time complexity of built in predicates

Question

I have been working on a small project with prolog. I have been noticing that when removing built in predicates like append(?List1, ?List2, ?List1AndList2)and subtract(+Set, +Delete, -Result) in favor for other alternatives ([Head | List2]when dealing with a list and single element, writing my own predicate for subtracting, etc.)

I was wondering about how optimised built in predicates generally are in prolog? I read that the complexity of subtract is |Delete|*|Set|, and I got quite a significant increase by using:

removeFriendsOfS(S, [Head | Tail], OutputAcc, Output) :-
    relation(S, Head),
    removeFriends(S, Tail, OutputAcc, Output), 
    !.

removeFriendsOfS(S, [Head | Tail], OutputAcc, Output) :-
    not(relation(S, Head)),
    removeFriends(S, Tail, [Head | OutputAcc], Output), 
    !.

Is it recommended to write your own predicates rather than to use the existing ones? I just recently started with prolog so I'm not so experienced yet.

I do not see how this predicate would work, since there is no basecase []. — Willem Van Onsem
Some built-in predicates are written in C "under the hood" and are good performers. However, it's possible that a built-in predicate is more general than you want, and writing one that is less general can perform better at the loss of generality (I'm looking at the cuts you have and thinking this may be the case). Are you sure that you are doing a like-for-like comparison in terms of functionality? — lurker
I seem to have forgotten to include the base case removeFriends(_, [], Output, Output) :- !. — cjerik

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2017-09-29T12:49:34

Is it recommended to write your own predicates rather than to use the existing ones?

Like in (probably) all programming languages, usually it is not a good idea to write your own functions over existing ones, since:

existing ones sometimes are hardcoded in the interpreter, making them faster;
these are tested a huge number of times and thus it is unlikely that there are still bugs in them;
most libraries are contructed by experts: people with good knowledge about efficiency, security, graph theory, computer graphics. As a result they make decisions that perhaps are not the best with respect to efficiency, or another criterion, but with respect to the typical application; and
if new specifications arise, the libraries will be updated, whereas you will have to update your tailor-made algorithm yourself. For list processing this is not very likely. But if you would for instance write a HTTP server yourself, then in the future the HTTP protocol might change turning your application deprecated.

The reason why Result = [Head|Tail] is preferable over append([Head], Tail, Result) is because, as the name already suggests - append/3 appends two lists int another list. Since Head is not a list, you construct one here: by writing [Head], you have actually written implicitly [Head|[]]. So constructing a 1-element list is (almost) as expensive as constructing a cons [Head|Tail]. Then append/3 will construct a new cons which will take some time as well and furthermore a call itself is expensive. So when prepending a list Tail with an element Head, [Head|Tail] is the straightforward way to do that.

The reason why your removeFriendsOfS/3 is faster is because it does something else than subtract/3: it filters the list based on a predicate. Prolog has a predicate for this as well exclude/3. For example:

:- use_module(library(apply)).

removeFriendsOfS(S, List, Out) :-
    exclude(relation(S), List, Out).

This works in O(n×k) with k the time of a relations(S,X) query.

Time complexity of built in predicates

1 Answers