Complexité temporelle des prédicats intégrés

Question

J'ai travaillé sur un petit projet avec prolog. J'ai remarqué que lorsque l'enlèvement construit en prédicats comme append(?List1, ?List2, ?List1AndList2) et subtract(+Set, +Delete, -Result) en faveur d'autres alternatives ([Head | List2] lorsqu'ils traitent avec une liste et un seul élément, écrire mon propre prédicat pour soustraire, etc.)

Je me demandais comment optimiser construit en prédicats sont généralement en prolog? Je lis que la complexité des Soustraire est |Delete|*|Set|, et je suis tout à fait une augmentation significative en utilisant:

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

est-il recommandé d'écrire vos propres prédicats plutôt que d'utiliser ceux qui existent déjà? J'ai récemment commencé avec prolog, donc je ne suis pas encore expérimenté.

Answer 1

Est-il recommandé d'écrire ses propres prédicats plutôt que d'utiliser ceux qui existent déjà?

Comme dans (probablement), tous les langages de programmation, il est généralement pas une bonne idée d'écrire vos propres fonctions sur celles qui existent déjà, depuis:

• ceux existants sont parfois codés en dur dans l'interpréteur, ce qui les rend plus rapide;
• ils sont testés un grand nombre de fois et il est donc peu probable qu'ils contiennent encore des bogues;
• la plupart des bibliothèques sont construites par experts: personnes ayant de bonnes connaissances en efficacité, sécurité, théorie des graphes, infographie. En conséquence, ils prennent des décisions qui ne sont peut-être pas les meilleures en ce qui concerne l'efficacité ou un autre critère, mais en ce qui concerne l'application typique; et
• Si de nouvelles spécifications apparaissent, les bibliothèques seront mises à jour, alors que vous devrez mettre à jour vous-même votre algorithme sur mesure. Pour le traitement de la liste, ce n'est pas très probable. Mais si vous voulez par exemple écrire vous-même un serveur HTTP, le protocole HTTP pourrait changer dans le futur en rendant votre application obsolète.

La raison pour laquelle Result = [Head|Tail] est préférable à append([Head], Tail, Result) est parce que, comme son nom l'indique - append/3deux listes Ajoute int une autre liste. Puisque Head n'est pas une liste, vous en construisez une ici: en écrivant [Head], vous avez réellement écrit implicitement [Head|[]]. Construire une liste de 1 élément est donc (presque) aussi cher que de construire une [Head|Tail]. Alors append/3 construira un nouveau contre qui prendra du temps aussi et de plus un appel lui-même est cher. Donc, lorsque vous préfixez une liste Tail avec un élément Head, [Head|Tail] est le moyen le plus simple de le faire. La raison pour laquelle votre removeFriendsOfS/3 est plus rapide est qu'il fait autre chose que subtract/3: il filtre la liste en fonction d'un prédicat. Prolog a un prédicat pour cela ainsi exclude/3. Par exemple:

:- use_module(library(apply)). 

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

Cela fonctionne dans O (n × k) avec k le temps d'une requête relations(S,X).