A Collections Framework?
in [Lisp]
|
Prev: scheme problem
Next: lisp student job offer
From: Tim Bradshaw on 6 May 2010 06:30 On 2010-05-06 09:35:04 +0100, Norbert_Paul said: > So I am only preparing myself to worry later, when the code > might show to be useful. However, I always worry about sticking > to the official spec. I do this as well. However I think the right thing to do (which I find counterintuitive and hard) is to do minimal abstraction, and be willing to rewrite when and if it becomes necessary, but only then, because you almost certainly can not predict the performance bottlenecks, not least because the requirements for the code will change so that things you thought would matter will, in fact, not matter, and things you thought would not, will. "minimal abstraction" means something like "do enough abstraction that the code is readable, but no more". So say NAME-OF rather than (CDR (ASSOC 'NAME PERSON-ALIST)) &c, but don't stress if your people are secretly just alists until it turns out that that matters.
From: Scott L. Burson on 7 May 2010 19:10 On May 5, 6:50 am, Norbert_Paul <norbertpauls_spam...(a)yahoo.com> wrote: > Nicolas Neuss wrote: > > Maybe Scott Burson's FSet? > > I have had already seen them and have almost forgotten > it. Now I just took a look athttp://common-lisp.net/project/fset/ > and have some questions: > > Is FSet efficient? > Scott Burson call it "functional", hence, doesn't > allow destructive modifiations. I can't imagine efficency > without "destroying things". There is a performance price, certainly. But remember: "Premature optimization is the root of all evil". My own policy is to use functional collections until profiling demonstrates the need for some particular collection to be imperative. So far there it hasn't happened, though that's partly a function of the particular kind of code I happen to be writing, which isn't extremely performance-sensitive. It surprises me a little that Lisp users are so resistant to functional collections. Lisp is all about trading small amounts of performance for more elegant semantics. Generic arithmetic, GC, array bounds checking, ... if we did not think these were good things, we would still be writing in C. Still, it's fair to ask just how much the performance price is for using FSet. Alas, I don't have benchmark numbers, but it isn't as bad as you might think. I wouldn't hesitate to use it for anything except inner loops in code I know (through profiling, ideally) is performance- critical. -- Scott
From: Scott L. Burson on 7 May 2010 19:17 On May 7, 4:10 pm, "Scott L. Burson" <g...(a)zeta-soft.com> wrote: > On May 5, 6:50 am, Norbert_Paul <norbertpauls_spam...(a)yahoo.com> > wrote: > > > Nicolas Neuss wrote: > > > Maybe Scott Burson's FSet? > > > I have had already seen them and have almost forgotten > > it. Now I just took a look athttp://common-lisp.net/project/fset/ > > and have some questions: > > > Is FSet efficient? > > Scott Burson call it "functional", hence, doesn't > > allow destructive modifiations. I can't imagine efficency > > without "destroying things". > > There is a performance price, certainly. > > But remember: "Premature optimization is the root of all evil". My > own policy is to use functional collections until profiling > demonstrates the need for some particular collection to be > imperative. So far there it hasn't happened, though that's partly a > function of the particular kind of code I happen to be writing, which > isn't extremely performance-sensitive. > > It surprises me a little that Lisp users are so resistant to > functional collections. Lisp is all about trading small amounts of > performance for more elegant semantics. Generic arithmetic, GC, array > bounds checking, ... if we did not think these were good things, we > would still be writing in C. > > Still, it's fair to ask just how much the performance price is for > using FSet. Alas, I don't have benchmark numbers, but it isn't as bad > as you might think. I wouldn't hesitate to use it for anything except > inner loops in code I know (through profiling, ideally) is performance- > critical. I should add, since FSet is implemented using balanced trees, the one thing you don't have to worry about when using it is time complexity problems. Every operation is within a (log n) factor of having the best time complexity that it can be implemented with, AFAIK. This makes it great for prototyping as you don't have to make data structure decisions in advance of knowing how you're really going to use the collection. You have operations like linear-time set intersection and log-time sequence concatenation at your disposal. -- Scott
From: Captain Obvious on 7 May 2010 19:36 SLB> It surprises me a little that Lisp users are so resistant to SLB> functional collections. They are fine with lists though, so I guess they don't use functional collections either because they don't like API (too complex?) or just are not aware of them. While lists are in language standard (even even in language's name...) are API is dead simple. As for performance argument, I guess you hear it often only because people who are interested in alternative collections are people who are concerned with performace. (Well, some might just need additional operations, but they won't complain...) And if performance is not of a concern at all, then just using lists might work. Lists can be used in functional (immutable) way and Common Lisp has a lot of functions to work with lists. At same time destructive counterparts are also available, so it's quite flexible. So, as I understand, performance-wise FSets are somewhere between lists (and simple, ad-hoc data structures) and highly-optimized imperative data structures. Thus we can say it is a niche thing. But if functional collections are implemented on language level -- e.g. as in Clojure -- people just use them and do not complain.
From: Duane Rettig on 7 May 2010 20:37
On May 5, 9:26 am, Norbert_Paul <norbertpauls_spam...(a)yahoo.com> wrote: > Paul Khuong wrote: > >> I am still worried, though. It is a pity that you cannot choose to exploit > >> features of your collections. At least sxhash should have been made > >> generic -- for example as generic function or via > >> (make-hash-table&key ... (hash #'sxhash)) > >> . > > > You mean, like the extension described in > > <http://sbcl.sourceforge.net/manual/Hash-Table-Extensions.html>? > > > :hash-function > > If nil (the default), a hash function based on the test argument > > >... > Yes, but I also want to write in compatible Common Lisp and avoid using > implementation specific features. Well, you'd at least be able to port to Allegro CL, which has had various make-hash-table options, including :hash-function, long before most other CL implementations did. Duane |