Re: pls confirm what approach is more efficient
- From: Jan Wielemaker <jan@xxxxxxxxxxxxxxxxxxx>
- Date: 17 Jan 2006 16:10:52 GMT
On 2006-01-17, mneuhaber22@xxxxxxxxxx <mneuhaber22@xxxxxxxxxx> wrote:
> To answer your question, I read in a book about Prolog that tail
> recursion is a good thing because it can be transformed into iteration,
> therefore stack usage is constant. I wasn't able to transform sum2 into
> something more efficient that doesn't consume resources linear to the
> size of the list (example that you provide is wondeful). So I was
> determined to write the that function in a tail recursive fashion no
> matter what. The result was sum1, which upon reflection and upon
> analyzing with 'statistics/0' turns out to be a dud. sum1 cannot be
> made iterative because freeze causes uninstantiated variables to be
> remembered on the stack...
Good. Coroutining can help in making it easier to write an application
that does things at the right moment and thus avoid unnecessary
recomputation. Its generally slower than well carefully crafted code as
freeze isn't free. It must store the frozen goal somewhere and restart
it when the time is ready. In some cases sorting out the proper
scheduling of goals when writing the code is hard or even impossible if
it depends on unknown input. Dynamic scheduling is your friend now, but
its an expensive one. In other words, you trade performance for
high-level writing.
> My problem is this - all my professional life I've known C and C++ and
> have been writing high performance OS kernel and driver code. Now I
> have to write a high performance (realtime) C++ application residing in
> userspace that calls into Prolog for decision support and it's very
> important to me to keep resource usage as small as possible. The big
Good. I do quite a bit of low level C hacking myself. Both have
their merits and the combination can deal with many problems :-)
> challenge is this - if there are several ways to write a function in
> Prolog, how can the most resource efficient implementation be picked
> out?
The issue isn't much different from C/C++. You roughly have to know
what is expensive and what is cheap in Prolog (a profiler helps here)
and know the design patterns that give you the cleanest and fastest
solution. "The Craft of Prolog" by Richard O'Keefe is the book to
read.
> Can all left recursive functions be transformed into right recursive?
Its a question for more theoretical people, but considering that any
recursive procedure can be translated into a non-recursive one the
answer is probably `yes'. In many cases, the result won't get prettier.
Without any doubt, any Prolog program can be translated into a C
program, then you can remove recursion and you'll have a fast but
complicated program :-)
> Can all predicates that consume resources proportionate to the size of
> the input set be rewritten cleverly to consume constant resources?
If the algorithm allows for that in C, you can get it done in Prolog
too.
> If the answer to these questions is no, then what classes of problems
> lend themselves to more efficient rewrite and how?
> I wish I could understand your thinking that led you to write sum/3.
The extra variable is known as `accumulator'. It replaces the variable
you increment (accumulate) destructively in C to do the job. Remember
you can't change the variable value in Prolog! More advanced Prolog
texts will explain the use of accumulators.
Success --- Jan
> Bart Demoen wrote:
>> mneuhaber22@xxxxxxxxxx wrote:
>> > Hello, as I delved deeper into Prolog I encountered coroutining.
>> > The task below is to sum the elements in a list.
>> > Assuming a very large input list, please confirm (or deny) my belief
>> > that sum1 is more efficient because of the tail recursion than sum2.
>> > Efficiency here is defined to mean that less computer resources must be
>> > consumed to arrive at the result.
>> > I promise I will not spam the group with stupid questions unless it's
>> > really important to ask.
>> >
>> > sum1([], S) :- S = 0.
>> > sum1([H|T], S) :- freeze(S1, S is S1 + H), sum1(T, S1).
>> >
>> >
>> > sum2([], S) :- S = 0.
>> > sum2([H|T], S) :- sum2(T, S1), S is S1 + H.
>> >
>>
>> In SICStus Prolog sum2 is about 16 times faster than sum1 and sum2 also
>> consumes less heap and less local stack than sum1.
>>
>> In B-Prolog (which has a notoriously fast freeze/2 mechanism), sum2 is
>> "only" 5 times faster. I didn't measure accurately the heap and local stack
>> consumption, but my bet is that in B-Prolog, the heap consumption is about the same,
>> and the local stack consumption is at least twice as big for sum1 as for sum2.
>>
>>
>>
>> You may ask why that can be.
>> But I will respond with asking: why do you think sum1 is faster or more memory efficient ?
>> And why do you think that sum1 is tail recursive ?
>>
>> Finally, a more efficient sum than sum1 and sum2, and also one which does not need a linear amount
>> of heap or local stack (linear in input list):
>>
>> sum(L,N) :- sum(L,0,N).
>> sum([],N,N).
>> sum([X|R],I,N) :- I2 is I + X, sum(R,I2,N).
>>
>>
>>
>> Cheers
>>
>> Bart Demoen
>
.
- References:
- pls confirm what approach is more efficient
- From: mneuhaber22
- Re: pls confirm what approach is more efficient
- From: Bart Demoen
- Re: pls confirm what approach is more efficient
- From: mneuhaber22
- pls confirm what approach is more efficient
- Prev by Date: Using rules in abductive way
- Next by Date: Re: pls confirm what approach is more efficient
- Previous by thread: Re: pls confirm what approach is more efficient
- Next by thread: Re: pls confirm what approach is more efficient
- Index(es):
Relevant Pages
|
|
