[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Using Emacs Lisp for script writing

From: Pascal J. Bourguignon
Subject: Re: Using Emacs Lisp for script writing
Date: Tue, 22 Dec 2009 16:36:56 +0100
User-agent: Gnus/5.101 (Gnus v5.10.10) Emacs/22.3 (gnu/linux)

Cecil Westerhof <address@hidden> writes:

> I'll try to keep that in mind. But compiling the regular expression made
> a big difference. Also, I remember someone telling me that lists are not
> very efficient. 

See?  This is what we meant when we told you that you need to know
more before trying to optimize things out!

Adding an element to a list or removing one is O(1) (when it's the
first element of the list).  Doing the same with a vector is O(n).
With a tree it'll be O(log(n)), and with a hash-table, it will be O(1)
amortized, that is, the constant factors will kill you.

Now of course if your algorithm is not adding or removing the first
element of the data structure, the time complexities and constant
factors will be different.

So either you have a partial memory, or the someone who told you that
lists are not very efficient did the same error most people do, that
is forgetting the conditions of application.

> What should I use instead? Or will I found that out in
> Practical Common Lisp?

Practical Common Lisp is only the first step.  There is a lot of
literature to read and programs to write to learn what has to be

Browse the cliki:

> Another question. The BBDB and also the example in Practical Common Lisp
> use lists for the database. Is this not inefficient? 

No, not in those conditions of application.

> Would a real database not be better. Not that I want to burn me at
> the moment on databases. ;-)

A real database would be overkill to store five records.  Just
"opening" the database would takes hundreds times more of cycles than
pushing onto a list, and don't you know the speed differential between
memory write and disk writes?

Remember this is a "simple database", a small example given to give a
taste of lisp before even introducing the Syntax of lisp!

But the most important thing you should have learnt from this chapter,
is not that it used lists to store the records, but that the storing
of the records was abstracted away with a add-record function.  That
means that all the programs presented in this chapter will work the
same once you hook a disk based database under add-record instead of
the simple list  (See SICP).

__Pascal Bourguignon__           

"Specifications are for the weak and timid!"

reply via email to

[Prev in Thread] Current Thread [Next in Thread]