A Collections Framework?
in [Lisp]
|
Prev: scheme problem
Next: lisp student job offer
From: Nicolas Neuss on 5 May 2010 09:23 Norbert_Paul <norbertpauls_spambin(a)yahoo.com> writes: > Is there something Comparable ($\ddot\smile$) to the > Java Collections Framework in LISP. > > I use functions like member, union, find, and stuff > to design my algorithms but when they are to become > productive with huge data sets I will need things like > balanced-trees etc. and I don't want to re-invent > the wheel. > > What I like in particular in Javas Collections is > the separation of semantics (via "Interfaces") and > implementation. There should be a similar standard in > LISP. > > Also hash-tables look a bit suspect to me because, > first, they are black-boxes and, second, make no > runtime complexity guarantees (like "O(n log n) > construction and O(log n) lookup") and, third, > "The intent is that this mapping be implemented by > a hashing mechanism, such as that described in > Section 6.4 ``Hashing'' of The Art of Computer > Programming, Volume 3 (pp506-549). In spite of > this intent, no conforming implementation is required > to use any particular technique to implement the > mapping." (t_hash_t.htm) > > Norbert Maybe Scott Burson's FSet? Nicolas
From: Norbert_Paul on 5 May 2010 09:50 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 at http://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". Do you use it yourself? I guess FEM has large data sets, too. So how do you store your sets and maps? Norbert
From: Nicolas Neuss on 5 May 2010 10:20 Norbert_Paul <norbertpauls_spambin(a)yahoo.com> writes: > I have had already seen them and have almost forgotten > it. Now I just took a look at http://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". This depends. It would be easy to construct applications where not destroying is faster, for example when you distribute slightly modified large datasets to functions doing some computation on them in parallel. > Do you use it yourself? I have only tried it, and it worked. But I did not do any performance tests with it. > I guess FEM has large data sets, too. So how do you store > your sets and maps? At the moment I use standard CL containers like hash-tables, vectors and lists. Nicolas
From: Mario S. Mommer on 5 May 2010 10:36 Norbert_Paul <norbertpauls_spambin(a)yahoo.com> writes: > Also hash-tables look a bit suspect to me because, > first, they are black-boxes and, second, make no > runtime complexity guarantees (like "O(n log n) > construction and O(log n) lookup") and, third, > "The intent is that this mapping be implemented by > a hashing mechanism, such as that described in > Section 6.4 ``Hashing'' of The Art of Computer > Programming, Volume 3 (pp506-549). In spite of > this intent, no conforming implementation is required > to use any particular technique to implement the > mapping." (t_hash_t.htm) Yes, an implementation is allowed to have really bad hash tables, but most try to do an at least decent job. Note that the sentences in the spec allow for hash tables using /better/ algorithms than those in TACP, and that that is one reason for that wording. SBCLs hash tables are quite good and AFAIK as fast as such things get. You can use them as a black box without worrying. I would sugest you to at least try them out. If they are too slow, you can still write your own collection stuff :-)
From: Norbert_Paul on 5 May 2010 11:54
Mario S. Mommer wrote: > Yes, an implementation is allowed to have really bad hash tables, but > most try to do an at least decent job. > > Note that the sentences in the spec allow for hash tables using /better/ > algorithms than those in TACP, and that that is one reason for that > wording. > > SBCLs hash tables are quite good and AFAIK as fast as such things > get. You can use them as a black box without worrying. I would sugest > you to at least try them out. If they are too slow, you can still write > your own collection stuff :-) 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)) .. |