Efficiency question

From: seguso (look_at_in.signature)
Date: 12/16/03

  • Next message: Jan Wielemaker: "Re: Efficiency question" 
    Date: Tue, 16 Dec 2003 12:27:14 GMT

    This is a question about asyntothic complexity, a clear answer of which
    I couldn't find in manuals I have read.

    Suppose I have a predicate file/1, defined by means of facts (not rules):

    file(a).
    file(b).
    file(c).

    Let us assume that the first argument is indexed, which is the default in
    SWI-prolog.

    What is the complexity of the call file(F), where F is bound to an atom?
    is it O(1)? Is it Theta(N), where N is the number of files? Or is it
    Theta(log(N))?

    Now, what changes if we replace file/1 with table/2?

    table(file, a).
    table(file, b).
    table(file, c).

    If I tell prolog to index the second argument of table/2, do I get a
    performance loss? And if I don't?

    Thanks a lot,
    (I am using SWI).

    Maurizio 

    -- 
Best Regards,
Maurizio Colucci
Please remove the uppercase letters "S,P,A,M":
seSgPuAsMo.forever@tin.it
  • Next message: Jan Wielemaker: "Re: Efficiency question"