This and some other slow list operations (like nconc) make
lists practically unusable for any time-demanding dynamic data
processing. Of course, I can define my-list data type, but in
that case, I will lose lot of nice operations defined on lists,
like subst.
So, my question is - what are you doing to make lists
reasonably fast in practice?
Majorinc wrote:
> This and some other slow list operations (like nconc) make
> lists practically unusable for any time-demanding dynamic data
> processing. Of course, I can define my-list data type, but in
> that case, I will lose lot of nice operations defined on lists,
> like subst.
>
> So, my question is - what are you doing to make lists
> reasonably fast in practice?
Calling length on a list is a bit of a red flag for efficiency. There's
no way you could possibly use a hash table or something? Consider:
CL-USER> (defvar h (make-hash-table :size 1024 :values #\h))
H
CL-USER> (loop for x from 0 to 1024 do (setf (gethash x h) x)) ;yes
GP, I know I just used loop...
NIL
CL-USER> (defun bazzle (ht)
(dotimes (i 10000)
(set 'out (hash-table-size ht))))
BAZZLE
CL-USER> (compile 'bazzle)
BAZZLE
NIL
NIL
CL-USER> (time (bazzle h))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 1 msec
; space allocation:
; 1 cons cell, 0 other bytes, 0 static bytes
NIL
As for lists: using RPLACA and RPLACD helps
CL-USER> (let ((a '(1 2))
(b '(8 9)))
(psetf (cdr a) (cdr b)
(cdr b) (cdr a))
(values a b))
(1 9)
(8 2)
CL-USER> (defun bar (a b)
(dotimes (i 100000) (psetf (cdr a) (cdr b)
(cdr b) (cdr a))))
BAR
CL-USER> (compile 'bar)
BAR
NIL
NIL
CL-USER> (time (bar '(1 2 3 4) '(0 9 8 7)))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 4 msec
; space allocation:
; 2 cons cells, 0 other bytes, 0 static bytes
as opposed to
CL-USER> (defun bar1 (a b)
(dotimes (i 100000) (let ((head-a (pop a))
(head-b (pop b)))
(push head-a b)
(push head-b a))))
BAR1
CL-USER> (compile 'bar1)
BAR1
NIL
NIL
CL-USER> (time (bar1 '(1 2 3 4) '(0 9 8 7)))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 20 msec user, 0 msec system
; cpu time (total) 20 msec user, 0 msec system
; real time 18 msec
; space allocation:
; 200,002 cons cells, 0 other bytes, 0 static bytes
NIL
or even
CL-USER>
(defun baz (vec-a vec-ab)
(dotimes (i 100000) (let ((head-a (vector-pop vec-a))
(head-b (vector-pop vec-b)))
(vector-push head-a vec-b)
(vector-push head-b vec-a))))
BAZ
CL-USER> (defvar q (make-array 10 :fill-pointer 5 :initial-element
#\q))
Q
CL-USER> (defvar w (make-array 10 :fill-pointer 5 :initial-element
#\w))
W
CL-USER> (compile 'baz)
CL-USER> (time (baz q w))
; cpu time (non-gc) 60 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 60 msec user, 0 msec system
; real time 69 msec
; space allocation:
; 2 cons cells, 0 other bytes, 0 static bytes
NIL
Nick
ps
is there anyway these examples could be flawed do to some sort of smart
compiler optimization with pointless iterative constructs? The 200,002
cones for the dotimes 100,000 two pops in bar1 makes me think not...
From: Wade Humeniuk
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <faPxf.93991$6K2.9914@edtnps90>
Majorinc wrote:
> This and some other slow list operations (like nconc) make
> lists practically unusable for any time-demanding dynamic data
> processing. Of course, I can define my-list data type, but in
> that case, I will lose lot of nice operations defined on lists,
> like subst.
>
> So, my question is - what are you doing to make lists
> reasonably fast in practice?
>
That is why CL has other sequence types. Vector and Array have
constant time operation for LENGTH. Also SUBSTITUTE works
on ARRAYS.
Switch your data to be arrays instead of LISTS.
Wade
In article <····················@edtnps90>,
··················@telus.net says...
> Majorinc wrote:
> > This and some other slow list operations (like nconc) make
> > lists practically unusable for any time-demanding dynamic data
> > processing. Of course, I can define my-list data type, but in
> > that case, I will lose lot of nice operations defined on lists,
> > like subst.
> >
> > So, my question is - what are you doing to make lists
> > reasonably fast in practice?
> >
>
> That is why CL has other sequence types. Vector and Array have
> constant time operation for LENGTH. Also SUBSTITUTE works
> on ARRAYS.
>
> Switch your data to be arrays instead of LISTS.
But I need them to grow dynamically. Would it be fast with
arrays?
Majorinc, Kazimir <·······@chem.pmf.hr> wrote:
> >
> > That is why CL has other sequence types. Vector and Array have
> > constant time operation for LENGTH. Also SUBSTITUTE works
> > on ARRAYS.
> >
> > Switch your data to be arrays instead of LISTS.
>
> But I need them to grow dynamically. Would it be fast with
> arrays?
Lisp offers "adjustable" arrays, although you usually must declare them
to be adjustable at array creation time. An adjustable array can be
dynamically expanded, through ADJUST-ARRAY or VECTOR-PUSH-EXTEND. The
specific performance characteristics are going to depend on
implementation/platform details. A typical choice would be to expand
the array by some constant factor when the actual allocation limit is
reached, but a poor implementation could expand a single element at a
time.
This issue is not Lisp specific. The performance tradeoffs between
arrays and linked lists should be basic Computer Science 101 material.
Arrays have poor performance characteristics when one must do such
things as "insert an element at the middle".
In some cases, LENGTH does not need to be precise. One can check in
O(M), for instance, that a list is at least M elements long, even if
the length of the list N >> M.
Majorinc wrote:
> In article <····················@edtnps90>,
> ··················@telus.net says...
> > Majorinc wrote:
> > > This and some other slow list operations (like nconc) make
> > > lists practically unusable for any time-demanding dynamic data
> > > processing. Of course, I can define my-list data type, but in
> > > that case, I will lose lot of nice operations defined on lists,
> > > like subst.
> > >
> > > So, my question is - what are you doing to make lists
> > > reasonably fast in practice?
> > >
> >
> > That is why CL has other sequence types. Vector and Array have
> > constant time operation for LENGTH. Also SUBSTITUTE works
> > on ARRAYS.
> >
> > Switch your data to be arrays instead of LISTS.
>
> But I need them to grow dynamically. Would it be fast with
> arrays?
That's where that data structure class you took comes in. (Or maybe you
only need, say, the length of a list, in which case you can simply keep
it around and update it incrementally [bad pun])
For example, if you want persistence, growability, O(1) [amortised]
cons, head, rest *and O(1) average, O(log n) worst case, random
access*, VLists look like a good idea.
http://en.wikipedia.org/wiki/VList. Unfortunately, most functions that
work on sequences don't seem to have an argument to specify how to
advance to the next subsequence. However, once you've prototyped your
code by using lists and built-in functions, it shouldn't be hard to
adapt it to use a more appropriate data structure.
So the answer seems to be to use the data structure that fits your
needs best, and that simply takes some research.
Paul Khuong
In article <1137167622.307233.131700
@o13g2000cwo.googlegroups.com>, ·······@gmail.com says...
>
> So the answer seems to be to use the data structure that fits your
> needs best, and that simply takes some research.
OK, but this is not satisfactory. Today, it is expected that
high level PL supports important data structures out of the
box. If Lisp's, say widgets and sockets lag behind mainstream
of the moment, OK, who cares?! But if Lisp, the language with
great AI background and even named by "lisp processing" lags
even in lists support, it rises concerns.
In article <1137180852.244781.237950
@f14g2000cwb.googlegroups.com>, ·······@hotmail.com says...
> Buahhaha. What an asshole.
Listen, asshole, fuck with your mother, not with me.
From: Zach Beane
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <m3d5ivdhw9.fsf@unnamed.xach.com>
Majorinc, Kazimir <·······@chem.pmf.hr> writes:
> In article <1137180852.244781.237950
> @f14g2000cwb.googlegroups.com>, ·······@hotmail.com says...
>
> > Buahhaha. What an asshole.
>
> Listen, asshole, fuck with your mother, not with me.
This being January, it's premature to announce "Troll of the Year"
awards. Please, save some of this for the critical sweeps week in
November!
Zach
In article <··············@unnamed.xach.com>, ····@xach.com
says...
> This being January, it's premature to announce "Troll of the Year"
> awards. Please, save some of this for the critical sweeps week in
> November!
Strange response. You're wrong.
<Majorinc>; "Kazimir" <·······@chem.pmf.hr> wrote in message ·······························@news.carnet.hr...
> In article <1137180852.244781.237950
> @f14g2000cwb.googlegroups.com>, ·······@hotmail.com says...
>
>> Buahhaha. What an asshole.
>
> Listen, asshole, fuck with your mother, not with me.
You don't know what you're talking about, you're abusive,
and you react poorly when your own words are given back to
you. Undergrad, right?
--
Geoff
Majorinc wrote:
> In article <1137167622.307233.131700
> @o13g2000cwo.googlegroups.com>, ·······@gmail.com says...
>
> >
> > So the answer seems to be to use the data structure that fits your
> > needs best, and that simply takes some research.
>
> OK, but this is not satisfactory. Today, it is expected that
> high level PL supports important data structures out of the
> box. If Lisp's, say widgets and sockets lag behind mainstream
> of the moment, OK, who cares?! But if Lisp, the language with
> great AI background and even named by "lisp processing" lags
> even in lists support, it rises concerns.
No, what is clear is you don't know what the term "list" means in the
context of Lisp, or, perhaps, computer science in general.
In article <1137181098.578298.310910
@g43g2000cwa.googlegroups.com>, ············@gmail.com says...
> No, what is clear is you don't know what the term "list" means in the
> context of Lisp, or, perhaps, computer science in general.
Ouch ... I speak about lists generally, as ADT. Lisp lists use
one particular implementation of lists, and not the best one.
Believe me. Or consult, say, Wikipedia.
Anyone else: is there anything in Lisp standard that prevents
Lisp implementors from adding few bytes per lisp and increasing
speed in some operations significantly. Is it *required* that
(length L) is linear? Or it is just usual?
From: Pascal Costanza
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <42qmhkF1kl6n2U1@individual.net>
Majorinc wrote:
> In article <1137181098.578298.310910
> @g43g2000cwa.googlegroups.com>, ············@gmail.com says...
>
>>No, what is clear is you don't know what the term "list" means in the
>>context of Lisp, or, perhaps, computer science in general.
>
> Ouch ... I speak about lists generally, as ADT. Lisp lists use
> one particular implementation of lists, and not the best one.
> Believe me. Or consult, say, Wikipedia.
>
> Anyone else: is there anything in Lisp standard that prevents
> Lisp implementors from adding few bytes per lisp and increasing
> speed in some operations significantly. Is it *required* that
> (length L) is linear? Or it is just usual?
In Lisp, it is a convention since nearly half a decade that lists are
implemented using cons cells in a certain way. It is not an ADT, it is
rather actually the case that the implementation details how lists are
built from cons cells are known. If you don't want the implications of
these implementation details, don't use those lists. However, cons cells
are a vital part of the core of Lisp. Changing them would have serious
implications on the rest of the whole story. You would probably rather
get a different language, maybe a very different one. (But feel free to
experiment.)
If you want other implementations of lists or other kinds of containers,
you can build your own by using structs or classes as building material,
or pick one of the existing libraries. There's no need to suffer from
anything...
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
In article <···············@individual.net>, ··@p-cos.net
says...
> > Anyone else: is there anything in Lisp standard that prevents
> > Lisp implementors from adding few bytes per lisp and increasing
> > speed in some operations significantly. Is it *required* that
> > (length L) is linear? Or it is just usual?
>
> In Lisp, it is a convention since nearly half a decade that lists are
> implemented using cons cells in a certain way. It is not an ADT, it is
> rather actually the case that the implementation details how lists are
> built from cons cells are known.
Well, you're right, I admitt. Lists in Lisp are really not ADT,
and hence they cannot be implemented on any other way without
breaking behaviour.
Pascal Costanza <··@p-cos.net> writes:
> Majorinc wrote:
>> In article <1137181098.578298.310910
>> @g43g2000cwa.googlegroups.com>, ············@gmail.com says...
>>
>>>No, what is clear is you don't know what the term "list" means in the
>>>context of Lisp, or, perhaps, computer science in general.
>> Ouch ... I speak about lists generally, as ADT. Lisp lists use one
>> particular implementation of lists, and not the best one. Believe
>> me. Or consult, say, Wikipedia.
>> Anyone else: is there anything in Lisp standard that prevents Lisp
>> implementors from adding few bytes per lisp and increasing speed in
>> some operations significantly. Is it *required* that (length L) is
>> linear? Or it is just usual?
>
> In Lisp, it is a convention since nearly half a decade that lists are
century
> implemented using cons cells in a certain way. It is not an ADT, it is
> rather actually the case that the implementation details how lists are
> built from cons cells are known. If you don't want the implications of
> these implementation details, don't use those lists. However, cons
> cells are a vital part of the core of Lisp. Changing them would have
> serious implications on the rest of the whole story. You would
> probably rather get a different language, maybe a very different
> one. (But feel free to experiment.)
>
> If you want other implementations of lists or other kinds of
> containers, you can build your own by using structs or classes as
> building material, or pick one of the existing libraries. There's no
> need to suffer from anything...
In addition, the point is that lists directly mapped to cons cell can
share some of their nodes (therefore some of their elements), and that
modification to a suffix of one list may modify at the same time a
suffix of another.
(let* ((l1 (list 'p 'q 'r))
(l2 (list* 'a 'b 'c l1))
(l3 (list* 'd 'e 'f (cdr l1))))
(nconc l1 (list 's)) ; we only modify l1
(push 'pp (cdr l1)) ; we only modify l1
(print l1) (princ (length l1))
(print l2) (princ (length l2)) ; but all the other lists are
(print l3) (princ (length l3))) ; modified too!
(P PP Q R S) 5
(A B C P PP Q R S) 8
(D E F Q R S) 6
For this reason, in general it's more efficient to compute the length
in O(n) when you need it, rather than try to track all the lists
refering the same cons and update their attributes (length, tail,
etc).
Another reason of the choice of directly mapping lists to cons cells,
it that it simplifies a lot the API: when you have a list, you can
access directly to the attributes you use most often (the null, the
first and the rest).
Otherwise, you need to distinguish the list ADT, and the list-node
ADT, and you need to first retrive the list-node you're interested
with (the first-list-node, and then the element attached to this
first-list-node, and the following list-node, and this doesn't give
you a rest list, so you need to allocate a new list ADT and to copy
all the list-nodes to get the rest, because sharing becomes
complicated.
--
__Pascal Bourguignon__ http://www.informatimago.com/
READ THIS BEFORE OPENING PACKAGE: According to certain suggested
versions of the Grand Unified Theory, the primary particles
constituting this product may decay to nothingness within the next
four hundred million years.
Kazimir Majorinc wrote:
> Ouch ... I speak about lists generally, as ADT. Lisp lists use
> one particular implementation of lists, and not the best one.
> Believe me. Or consult, say, Wikipedia.
The word you're looking for there would be "sequence"
(which does indeed mean "anything that supports the usual
sequence operations", though there might be some room for
disagreement about exactly what those are), not "list".
But: Lisp's "lists" are perhaps misnamed, because what Lisp
really has is an ordered-pair type and some facilities
for the common case where you use your ordered pairs
to implement sequences.
> Anyone else: is there anything in Lisp standard that prevents
> Lisp implementors from adding few bytes per lisp and increasing
> speed in some operations significantly. Is it *required* that
> (length L) is linear? Or it is just usual?
It's pretty much required. There are ways to get round it,
but at the cost of making other things appallingly expensive.
For instance: every cons cell (the ordered-pair type from
which Lisp lists are built) could have a "length" field.
But then, since you're allowd to mutate an existing cons
cell, you'd need to arrange for every list it's part of
to update all the lengths, so a simple operation that
obviously ought to be constant-time would become unboundedly
expensive.
Or: you could try to implement lists as resizable arrays,
and have some kind of hack to cope with the general case
where someone uses cons cells as arbitrary ordered pairs.
But then CONS, which slaps something onto the start of a
list and "obviously" ought to be cheap, would become expensive.
Or: you could invent some magic new data structure (let's
call it a "skew AVL binomial prefix heap") that supports
all the operations Lisp needs and runs LENGTH faster. Maybe.
But if you could you'd probably find that in practice all
the usual operations, although they run in amortized constant
time, typically take 10 times longer than they ever did
before, and then millions of existing Lisp programs that
manage just fine with ordinary Lisp lists, thank you very
much, would be much slower and use much more memory than
before.
Lisp lists work fine for many things in practice even
though LENGTH (and, more importantly, ELT) don't run
in constant or even logarithmic time for them. Arrays
work fine for many things in practice even though adding
elements to the front is slow. Yes, there are other ways
to make all those tradeoffs, and it would be nice if Lisp
had a richer variety of data structures in the standard
library, and it would be nice if things like LOOP played
more nicely with user-defined sequence types. No one ever
said that Common Lisp is the perfect language; welcome
to the real world. If those things make Lisp unacceptable
to you, then by all means don't accept it and go use Java
or C++ or something else. Come back in five years and
tell us whether those data structures in the standard
library actually helped much. My own experience is that
no language offers quite the set of data structures that
I'd like, and my suspicion is that no language could
*possibly* please everyone in this respect. Given that,
my preference is for a language that makes it not too
painful to build the structures I want. Lisp is pretty
good in that regard.
--
Gareth McCaughan
.sig under construc
From: Ulrich Hobelmann
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <42qsgsF1k9ltcU1@individual.net>
Majorinc wrote:
> In article <1137181098.578298.310910
> @g43g2000cwa.googlegroups.com>, ············@gmail.com says...
>
>> No, what is clear is you don't know what the term "list" means in the
>> context of Lisp, or, perhaps, computer science in general.
>
> Ouch ... I speak about lists generally, as ADT. Lisp lists use
> one particular implementation of lists, and not the best one.
> Believe me. Or consult, say, Wikipedia.
Which list is best, depends on your point of view. Lisp lists are nice,
because they compose, because they share structure, because they allow
programming without mutating lists all the time, which prevents many
bugs. I used to like doubly-linked lists in C for efficiency, but in
the end I think the hassle wasn't worth it.
Lisp lists are easy. You append two lists, or filter them, but the
original can still be used by another part of the program.
> Anyone else: is there anything in Lisp standard that prevents
> Lisp implementors from adding few bytes per lisp and increasing
> speed in some operations significantly. Is it *required* that
> (length L) is linear? Or it is just usual?
Lists compose. That is, the REST of a list is also a list. The CONS or
APPEND also creates new lists. You don't have lists and their nodes, as
in C style lists, or Java style, where the List class encapsulates the
actual nodes. Composing Java lists like in Lisp would be very slow.
--
the bottom line is that a JavaSchool that won't teach C and won't teach
Scheme is not really teaching computer science, either. -- Joel Spolsky
From: Peter Seibel
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <m23bjgckey.fsf@gigamonkeys.com>
Majorinc, Kazimir <·······@chem.pmf.hr> writes:
> In article <1137167622.307233.131700
> @o13g2000cwo.googlegroups.com>, ·······@gmail.com says...
>
>>
>> So the answer seems to be to use the data structure that fits your
>> needs best, and that simply takes some research.
>
> OK, but this is not satisfactory. Today, it is expected that
> high level PL supports important data structures out of the
> box. If Lisp's, say widgets and sockets lag behind mainstream
> of the moment, OK, who cares?! But if Lisp, the language with
> great AI background and even named by "lisp processing" lags
> even in lists support, it rises concerns.
Hmmmm, what data structure are you thinking of that is commonly
provided by other languages that is missing from Lisp?
-Peter
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
From: Russell McManus
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <87lkx7yo0d.fsf@cl-user.org>
Peter Seibel <·····@gigamonkeys.com> writes:
> Hmmmm, what data structure are you thinking of that is commonly
> provided by other languages that is missing from Lisp?
Queues and binary trees spring to mind.
-russ
From: Edi Weitz
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <ufynfm0t0.fsf@agharta.de>
On Mon, 23 Jan 2006 10:14:58 -0500, Russell McManus <···············@yahoo.com> wrote:
> Peter Seibel <·····@gigamonkeys.com> writes:
>
>> Hmmmm, what data structure are you thinking of that is commonly
>> provided by other languages that is missing from Lisp?
>
> Queues and binary trees spring to mind.
Those are commonly provided in other languages? Which ones?
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Edi Weitz wrote:
> On Mon, 23 Jan 2006 10:14:58 -0500, Russell McManus <···············@yahoo.com> wrote:
>
> > Peter Seibel <·····@gigamonkeys.com> writes:
> >
> >> Hmmmm, what data structure are you thinking of that is commonly
> >> provided by other languages that is missing from Lisp?
> >
> > Queues and binary trees spring to mind.
>
> Those are commonly provided in other languages? Which ones?
>
> --
>
> Lisp is not dead, it just smells funny.
>
> Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Java, C++ and any .NET language has queue and tree.
Not binary tree but SortedSet or SortedMap which is actually
implemented as a tree that allow insertion, deletion and serching in
log(n) time for any kind of comparable object.
Lisp Hashtable is inferior compare to other Language's hash table.
With C++'s map<> or Java's Hashtable, you can define a hash function
for any type of object and you can define your own equivelent
critieria. Whereas in Common Lisp, different object is always different
from hash table's view (You cannot specialize EQUAL, HASH or
LESS-THAN-P function).
C++s map<> and Java's SortedMap also allow one to define the order of
object in that sorted collection. You cannot do that with Common Lisp's
hash table.
The fact that generic function is not fully used in standard also make
working with user collection harder. Standard Common Lisp lacks the
idea of general iterator so if you want to iterate over:
- List: you use dolist or map.
- Hashtable: you use maphash or with-hashtable-iterator.
- Sequence: you use map.
- Your own collection type: you invent every thing.
Using Loop doesn't really abstract the collection out since you have to
know which kind of collection
(LOOP FOR item IN list ...)
(LOOP FOR item ACROSS vector ...)
(LOOP FOR key BEING EACH HASH-KEY OF hash-table ...)
(LOOP FOR symbol BEING EACH EXTERNAL-SYMBOL OF package ...)
(LOOP FOR item IN my-custom-collection) ;; ERROR !!!
If only CLOS is used more in the designed of the standard library,
every collection should have method SIZE, EMPTY-P, and ITERATOR-OF.
Then we can use a new map function as.
(GMAP #'(lambda (key val)...) table)
(GMAP #'(lambda (val)...) list)
(GMAP #'(lambda (val)...) vector)
(GMAP #'(lambda (val)...) my-collection-x)
(GLOOP FOR (key val) IN a-table)
(GLOOP FOR val IN a-list)
(GLOOP FOR val IN a-vector)
(GLOOP FOR val IN my-collection-x)
Now that I said it, it's really easy to implement this library, I'm
sure you also know instantly how to do it already. But the sad thing
for me is that, because it's not designed from the start in the
standard, this facility will only be available in your own code and
library that use your code.
Imagine that if Condition System is not in Common Lisp from the start,
only C style errno is avaliable in Common Lisp. Sure you can implement
Condition System on top, but it will only work so in your own library,
the internal system function will not signal condition for error.
I hope you don't see me as trolling. But Common Lisp is not perfect and
I think it's okay to be honest about what the flaw is, rather than
ignore the issue or pretending that any thing not provided by the
standard is too specific and should be implemented as third-party
library.
Regards,
From: Russell McManus
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <87acdmzqd9.fsf@cl-user.org>
"Pisin Bootvong" <··········@gmail.com> writes:
> If only CLOS is used more in the designed of the standard library,
> every collection should have method SIZE, EMPTY-P, and ITERATOR-OF.
> Then we can use a new map function as.
>
> (GMAP #'(lambda (key val)...) table)
> (GMAP #'(lambda (val)...) list)
> (GMAP #'(lambda (val)...) vector)
> (GMAP #'(lambda (val)...) my-collection-x)
>
> (GLOOP FOR (key val) IN a-table)
> (GLOOP FOR val IN a-list)
> (GLOOP FOR val IN a-vector)
> (GLOOP FOR val IN my-collection-x)
>
> Now that I said it, it's really easy to implement this library, I'm
> sure you also know instantly how to do it already. But the sad thing
> for me is that, because it's not designed from the start in the
> standard, this facility will only be available in your own code and
> library that use your code.
It would be cool if there was a standard loop path to use the generic
functions you described. Or at least a standard way of adding a loop
path!
> I hope you don't see me as trolling. But Common Lisp is not perfect
> and I think it's okay to be honest about what the flaw is, rather
> than ignore the issue or pretending that any thing not provided by
> the standard is too specific and should be implemented as
> third-party library.
Great post. I wish I had the time to write this up. I still much
prefer Common Lisp over any other programming language, but I agree
that these constitute very useful improvements.
-russ
Russell McManus <···············@yahoo.com> writes:
> "Pisin Bootvong" <··········@gmail.com> writes:
>
> > I hope you don't see me as trolling. But Common Lisp is not perfect
> > and I think it's okay to be honest about what the flaw is, rather
> > than ignore the issue or pretending that any thing not provided by
> > the standard is too specific and should be implemented as
> > third-party library.
>
> Great post. I wish I had the time to write this up. I still much
> prefer Common Lisp over any other programming language, but I agree
> that these constitute very useful improvements.
Out of curiosity, what makes this
http://www.metabang.com/open-source-software.html
insufficient in covering most (if not all) the concerns here? Lack of
exposure?
/Jon
--
'j' - a n t h o n y at romeo/charley/november com
From: Russell McManus
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <874q3tzcg0.fsf@cl-user.org>
jayessay <······@foo.com> writes:
> Out of curiosity, what makes this
>
> http://www.metabang.com/open-source-software.html
>
> insufficient in covering most (if not all) the concerns here? Lack of
> exposure?
Pretty cool. Not much is missing in terms of functionality.
One thing I can think of is the ability to hook these data structures
into loop. I would suggest adding just one loop path that would call
the right generic function to get an iterator and then use it
repeatedly.
Another is to have destructive and non-destructive red-black trees
available.
That's it for functionality.
But from reading the documentation, I'm having trouble figuring out
which generic function is called to compare two elements of a
red-black tree. How is this done, and where is it mentioned in the
documentation?
It appears that the documentation is generated by a tool called TINAA,
which though undoubtedly cool, does not substitute for high quality
human written documentation. For Common Lisp add-ons to have anywhere
close to the acceptance of standard facilities the little fiddly bits
like documentation all have to be in place.
-russ
jayessay wrote:
>
> Out of curiosity, what makes this
>
> http://www.metabang.com/open-source-software.html
>
> insufficient in covering most (if not all) the concerns here? Lack of
> exposure?
>
For me, the concern I have is not that there's no library out there
that already does this, as I have already noted that anyone reading my
post probably instantly know how to write it up.
The concern I have is that the conecpt is not build into the core of
the system. Common Lisp's library is not design with much of
extensibility in mind, that's the issue I'm pointing out here.
C# and Java may be inferion in term of language themselves. But they
puts lots of effort in designing library. And I'm not talking about the
amount of library they have but the concept that they put in that allow
one to plug functionality in more than Common Lisp's library desgin.
I can listed here:
- Hash table cannot override hash-function, key-sort-order, object
equality.
- No concept of generic collection iterator, no generic LOOP or MAP
- No generic function EQUAL. I know it's not possible to have a
meaning full equal function in theory. But practically every other
language has it and I found most people to be happy with it.
- No concept of disposable object. This is the same as C++'s
destructor or C# 'using' kerword. With this every disposable object
will implement generic method named CLEAN-UP. So instead of having
WITH-OPEN-FILE, WITH-FORIEGN-OBJECT, WITH-XXXX, WITH-YYYY. Common Lisp
would provide standard macro LET-WITH, which would call CLEAN-UP at the
end of scope. And you just specialize CLEAN-UP method for each class.
So while Common Lisp the language is superior to Java/C# in term of
language features. Java/C# beat back in term of concept, library, and
design pattern.
-----------------
Metatilities and such is a nice library. But as I pointed out before,
not many people use it because it's not in there in their hand in the
first place. So people like you, with good faith, reimplement the
structure. And introduce duplication of works with other who also write
the same structure. A waste of effort and a confusion for users.
For example:
CLISP has WITH-GENSYMS
Arnesi has WITH-UNIQUE-NAMES
Cliki has WITH-UNIQUE-NAMES
Metatilities has WITH-UNIQUE-NAMES
...
Mopilities contains MOP portable layer
Closer to Mop contains MOP portable layer
MCCLIM contains MOP portable layer
...
And many others portable library that did not rely on these library do
the exact same thing over and over again.
>From what I see, not only that these feature are not in the standard.
But there isn't even a community consensus to put it once and for all
in a single defacto standard place and use it. But I knew it's hard to
do; I wouldn't add metatilities as dependency just to use
WITH-UNIQUE-NAMES.
The best I wish is that CL-UTILITES or CL3-DEFACTO project is there and
then SBCL, CMUCL and CLISP agree to package this with their
distribution, use it in CL-USER. And also that most library writer out
there agree to regards it as a new standard and never to reimplement
what's already there. And also put them as dependency in there ASDF
system in case of Lispworks or ACL.
>
> /Jon
>
> --
> 'j' - a n t h o n y at romeo/charley/november com
Pisin,
From: Stefan Nobis
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <87bqy0tqe9.fsf@snobis.de>
"Pisin Bootvong" <··········@gmail.com> writes:
> And many others portable library that did not rely on these library do
> the exact same thing over and over again.
Even worse: If you use some libraries, these may depend on different
of these utility libraries, so you may end with 3 mop-layers, 5
with-unique-names, etc in your project. Not very appealing.
> The best I wish is that CL-UTILITES or CL3-DEFACTO project is there
> and then SBCL, CMUCL and CLISP agree to package this with their
> distribution, use it in CL-USER. And also that most library writer
> out there agree to regards it as a new standard and never to
> reimplement what's already there. And also put them as dependency in
> there ASDF system in case of Lispworks or ACL.
I second this!
--
Stefan.
From: Russell McManus
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <87hd7uzya6.fsf@cl-user.org>
Edi Weitz <········@agharta.de> writes:
> On Mon, 23 Jan 2006 10:14:58 -0500, Russell McManus <···············@yahoo.com> wrote:
>
>> Peter Seibel <·····@gigamonkeys.com> writes:
>>
>>> Hmmmm, what data structure are you thinking of that is commonly
>>> provided by other languages that is missing from Lisp?
>>
>> Queues and binary trees spring to mind.
>
> Those are commonly provided in other languages? Which ones?
C++. Java.
-russ
From: Edi Weitz
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <ulkx6lvu3.fsf@agharta.de>
On Mon, 23 Jan 2006 11:47:45 -0500, Russell McManus <···············@yahoo.com> wrote:
> Edi Weitz <········@agharta.de> writes:
>
>> Those are commonly provided in other languages? Which ones?
>
> C++. Java.
Well, OK, that's two. That's not what I would call "commonly
provided." Although I have to admit that C++ and Java are, in a way,
the direct competition of CL.
Cheers,
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
From: Wade Humeniuk
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <0BPxf.93997$6K2.54911@edtnps90>
Majorinc wrote:
> In article <····················@edtnps90>,
> ··················@telus.net says...
>> Majorinc wrote:
>>> This and some other slow list operations (like nconc) make
>>> lists practically unusable for any time-demanding dynamic data
>>> processing. Of course, I can define my-list data type, but in
>>> that case, I will lose lot of nice operations defined on lists,
>>> like subst.
>>>
>>> So, my question is - what are you doing to make lists
>>> reasonably fast in practice?
>>>
>> That is why CL has other sequence types. Vector and Array have
>> constant time operation for LENGTH. Also SUBSTITUTE works
>> on ARRAYS.
>>
>> Switch your data to be arrays instead of LISTS.
>
> But I need them to grow dynamically. Would it be fast with
> arrays?
>
In your app estimate the size of array you may need. Then when
you allocate the array with MAKE-ARRAY make it adjustable with
a fill pointer and the size you need. Use VECTOR-PUSH-EXTEND to
add elements to the end. If you are uncomfortable with allocating
arrays with mostly empty space, let the Lisp implementation
do what it can. If it has to resize an array then I am sure it
will do its best to extend it in some appropriate way. Extending
an array by reallocating it and copying will probably be about the
same speed as adding an element to the end of a list. Pushing
an element onto the front of a list is very fast, with no speedy
counterpart for an array.
You can create a speedy type of sequence called a queue, where appending
and prepending objects is constant speed.
Wade
From: Giorgos Keramidas
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <864q41ugwq.fsf@flame.pc>
On Fri, 13 Jan 2006 15:22:36 GMT,
Wade Humeniuk <··················@telus.net> wrote:
> You can create a speedy type of sequence called a queue, where
> appending and prepending objects is constant speed.
Would something like this be similar?
> (defparameter *queue* nil)
*QUEUE*
> (defparameter *queue-tail* nil)
*QUEUE-TAIL*
> (defun enqueue (x)
(if (null *queue*)
(progn (setf *queue* (list x))
(setf *queue-tail* *queue*))
(progn (nconc *queue-tail* (list x))
(setf *queue-tail* (cdr *queue-tail*))))
*queue*)
ENQUEUE
> (setf *queue* nil)
NIL
> (enqueue 3)
(3)
> (enqueue 4)
(3 4)
> (enqueue 5)
(3 4 5)
> *queue-tail*
(5)
> (list *queue* *queue-tail*)
((3 4 5) (5))
> (eq (cddr *queue*) *queue-tail*)
T
>
Admittedly it's not "one object", but I was extremely glad when I got it
right, after some experimentation :)))
Giorgos Keramidas wrote:
> On Fri, 13 Jan 2006 15:22:36 GMT,
> Wade Humeniuk <··················@telus.net> wrote:
> > You can create a speedy type of sequence called a queue, where
> > appending and prepending objects is constant speed.
>
> Would something like this be similar?
>
> > (defparameter *queue* nil)
>
> *QUEUE*
> > (defparameter *queue-tail* nil)
Norvig & Waters wrote a good article on queues.
http://www.merl.com/publications/TR1991-004/
Tayssir
--
"Let's talk about the question of why people are wealthy. There is a
myth that it's a function of enormous personal attributes. [...] The
individual wealth which is generated in this economy is, in my
judgment, and I doubt that there is much that anyone could disagree
with about this, is a function of the innovative businesses which are
created as a result of federal research. But you understand that the
people who benefit from that research get it free. [...] So, if
somebody starts a software company or a biotechnology company, or even
if somebody owns a building in downtown Washington which you rent to
those people, it starts from the same place. It starts from this
incredible research activity which is going on with federal money."
-- Bill Gates Sr., 2003
http://www.taxpolicycenter.org/publications/template.cfm?PubID=900584
From: Giorgos Keramidas
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <86acdkuxk4.fsf@flame.pc>
On 18 Jan 2006 19:02:06 -0800,
"Tayssir John Gabbour" <···········@yahoo.com> wrote:
> Giorgos Keramidas wrote:
>> > (defparameter *queue* nil)
>>
>> *QUEUE*
>> > (defparameter *queue-tail* nil)
>
> Norvig & Waters wrote a good article on queues.
> http://www.merl.com/publications/TR1991-004/
Fantastic, thanks! :)
It's companion (part 2) seems also a fine read, and easy to find:
http://www.merl.com/publications/TR1993-017/
From: Zach Beane
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <m364ohasp7.fsf@unnamed.xach.com>
Giorgos Keramidas <········@ceid.upatras.gr> writes:
> Would something like this be similar?
>
> > (defparameter *queue* nil)
>
> *QUEUE*
> > (defparameter *queue-tail* nil)
>
> *QUEUE-TAIL*
> > (defun enqueue (x)
> (if (null *queue*)
> (progn (setf *queue* (list x))
> (setf *queue-tail* *queue*))
> (progn (nconc *queue-tail* (list x))
> (setf *queue-tail* (cdr *queue-tail*))))
> *queue*)
[snip]
Here's the version from "ANSI Common Lisp". It has a slight advantage;
you can make more than one. :)
(defun make-queue () (cons nil nil))
(defun enqueue (obj q)
(if (null (car q))
(setf (cdr q) (setf (car q) (list obj)))
(setf (cdr (cdr q)) (list obj)
(cdr q) (cdr (cdr q))))
(car q))
(defun dequeue (q)
(pop (car q)))
More code here:
http://lib.store.yahoo.net/lib/paulgraham/acl2.lisp
Zach
From: Giorgos Keramidas
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <86wtgxrn0k.fsf@flame.pc>
On 18 Jan 2006 20:53:56 -0500, Zach Beane <····@xach.com> wrote:
> Giorgos Keramidas <········@ceid.upatras.gr> writes:
>> Would something like this be similar?
>>
>> > (defparameter *queue* nil)
>>
>> *QUEUE*
>> > (defparameter *queue-tail* nil)
>>
>> *QUEUE-TAIL*
>> > (defun enqueue (x)
>> (if (null *queue*)
>> (progn (setf *queue* (list x))
>> (setf *queue-tail* *queue*))
>> (progn (nconc *queue-tail* (list x))
>> (setf *queue-tail* (cdr *queue-tail*))))
>> *queue*)
> [snip]
>
> Here's the version from "ANSI Common Lisp". It has a slight advantage;
> you can make more than one. :)
>
> (defun make-queue () (cons nil nil))
>
> (defun enqueue (obj q)
> (if (null (car q))
> (setf (cdr q) (setf (car q) (list obj)))
[...]
Hoho! I keep learning new tricks every day. It didn't occur to me when
I tried to write mine that the result of setf is setfable itself too.
Thanks :)
Giorgos Keramidas <········@ceid.upatras.gr> writes:
> On 18 Jan 2006 20:53:56 -0500, Zach Beane <····@xach.com> wrote:
>> Giorgos Keramidas <········@ceid.upatras.gr> writes:
>> [...]
>> (defun enqueue (obj q)
>> (if (null (car q))
>> (setf (cdr q) (setf (car q) (list obj)))
> [...]
>
> Hoho! I keep learning new tricks every day. It didn't occur to me when
> I tried to write mine that the result of setf is setfable itself too.
Where do you think C took its idea of a=b=c from?
(setf a (setf b c))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Cats meow out of angst
"Thumbs! If only we had thumbs!
We could break so much!"
Majorinc wrote:
> In article <····················@edtnps90>,
> ··················@telus.net says...
> > Switch your data to be arrays instead of LISTS.
>
> But I need them to grow dynamically. Would it be fast with
> arrays?
If we are talking algorithmic complexity, consider that dynamic vectors
can be implemented in O(N) time for the operation of appending N items.
From: Edi Weitz
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <uu0c8mb87.fsf@agharta.de>
On Fri, 13 Jan 2006 15:06:02 +0100, Majorinc, Kazimir <·····@email.address> wrote:
> This and some other slow list operations (like nconc) make lists
> practically unusable for any time-demanding dynamic data processing.
Nonsense. You just have to make sure to use lists in a reasonable
way.
> So, my question is - what are you doing to make lists reasonably
> fast in practice?
Use mostly fast list operations like PUSH, POP, CAR, CONS, etc. Use
the "slow" operations sparingly and only when needed. Use destructive
operations where applicable.
Look at the source code of existing Lisp libraries for typical list
usage.
Cheers,
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
From: Ulrich Hobelmann
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <42q2i8F1kl0nsU1@individual.net>
Majorinc wrote:
> This and some other slow list operations (like nconc) make
> lists practically unusable for any time-demanding dynamic data
> processing. Of course, I can define my-list data type, but in
> that case, I will lose lot of nice operations defined on lists,
> like subst.
True. If you can't live with the restrictions of lists, you can't have
the advantages, either.
> So, my question is - what are you doing to make lists
> reasonably fast in practice?
Lists are fast, but not for random access. But you can bake your own
data structures, such as keeping a pointer to the end of a list, and
SETF-ing the last element to append items or lists. Of course that's
not very clean, but if you know what you're doing...
Or maybe you really want some kind of tree, based on cons cells, or on
structs or vectors. Writing something like SUBST shouldn't be too hard.
In fact SUBST seems to work on cons trees already.
And subst has to traverse the whole data structure, I think, so maybe
the other list operations aren't even the slow-down factor in your
program. Profiling could help to find out how much speed you could gain
by writing your own data structure. Remember Amdahl's Law.
--
the bottom line is that a JavaSchool that won't teach C and won't teach
Scheme is not really teaching computer science, either. -- Joel Spolsky
Majorinc, Kazimir <·····@email.address> writes:
> This and some other slow list operations (like nconc) make
> lists practically unusable for any time-demanding dynamic data
> processing. Of course, I can define my-list data type, but in
> that case, I will lose lot of nice operations defined on lists,
> like subst.
>
> So, my question is - what are you doing to make lists
> reasonably fast in practice?
If you avoid destructive operations, you can memoize LENGTH.
(asdf:operate 'asdf:load-op :memoize)
(shadow 'length)
(defun length (x) (cl:length x))
(memoize:memoize-function 'length)
(let ((l (loop :repeat 100000 :collect nil)))
(time (length l))
(let ((nl (append (list 'some 'new 'elements) l)))
(time (length l)))
(time (length l)))
Real time: 0.002219 sec. ; First time O(length(l))
Run time: 0.0 sec.
Space: 88 Bytes
Real time: 1.5E-5 sec. ; then O(1)
Run time: 0.0 sec.
Space: 8 Bytes
Real time: 5.0E-6 sec. ; and again O(1)
Run time: 0.0 sec.
Space: 8 Bytes
100000
If your algorithm requires it, I see no problem in encapsulating lisp
lists in your own "optimized" list data structure:
(defstruct (fast-list :constructor %make-fast-list)
elements tail length)
(defun make-fast-list (&key elements)
(%make-fast-list :elements elements
:tail (last elements)
:length (length elements)))
(shadow 'length)
(defmethod length ((self cons)) (cl:length self))
(defmethod length ((self null)) 0)
(defmethod length ((self make-fast-list)) (fast-list-length self))
or if you can lose the requirement for an identical interface, merely
write the functions you need on the new data structure:
(fast-list-length fl)
(fast-list-append fl1 fl2 fl2)
(fast-list-first fl)
(fast-list-last fl)
; etc
Or for short, we just _program_!
--
__Pascal Bourguignon__ http://www.informatimago.com/
NEW GRAND UNIFIED THEORY DISCLAIMER: The manufacturer may
technically be entitled to claim that this product is
ten-dimensional. However, the consumer is reminded that this
confers no legal rights above and beyond those applicable to
three-dimensional objects, since the seven new dimensions are
"rolled up" into such a small "area" that they cannot be
detected.
On 2006-01-13 14:06:02 +0000, Majorinc, Kazimir <·····@email.address> said:
> This and some other slow list operations (like nconc) make lists
> practically unusable for any time-demanding dynamic data processing.
That's precisely why Common Lisp offers you a choice in your
data structures, some of which, generically known as sequence,
and of which all of list, string and array are member, all offer
the same LENGTH operation that operates in an amount of time
related to YOUR choice of sequence.
> So, my question is - what are you doing to make lists reasonably fast
> in practice?
You don't use "lists in practice" when lists are the wrong choice.
--
JFB
From: Pascal Costanza
Subject: Re: What to do with (time (length L)) proportional to (length L)
Date:
Message-ID: <42rv72F1ilj82U1@individual.net>
Majorinc wrote:
> This and some other slow list operations (like nconc) make
> lists practically unusable for any time-demanding dynamic data
> processing. Of course, I can define my-list data type, but in
> that case, I will lose lot of nice operations defined on lists,
> like subst.
>
> So, my question is - what are you doing to make lists
> reasonably fast in practice?
Try to avoid using lists in a way that makes the code iterate over the
lists many times. Indeed, 'length and 'nconc iterate over lists. You
have to iterate over lists in the general case, but there are some
idioms to combine several iterations into one or only a few.
For example, instead of:
(let* ((temp1 (mapcar #'f1 some-list))
(temp2 (mapcar #'f2 temp1))
(temp3 (mapcar #'f3 temp2)))
(mapcar #'f4 temp3))
You could better say:
(loop for elem in some-list
collect (f4 (f3 (f2 (f1 elem)))))
That's an extremely simplified example, but that's one direction to go.
Or use some datatype that's better suited to your needs.
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/