Viewing:
http://blip.tv/file/get/Richhickey-ClojureDataStructuresPart2506.mov
I'm wondering:
Take this for example:
user> (def m {:a 1 :b 2})
#'user/m
user> (def m2 (conj m {:d 3 :b 56}))
#'user/m2
user> m2
{:d 3, :a 1, :b 56}
user> m
{:a 1, :b 2}
user>
The point here is that m2 behaves like a completly new map, and you
can't modify it, BUT internally, m2 is NOT a copy of m, but m with
modifications.
Rich says that this allows:
- (Almost) constant time access to the original map and to the apparent
copies of it.
- Very little memory penalty.
- Complete immutability anyway, and, as a consequence, these data maps
are completely thread safe.
- Efficient use of functional programming.
So, my question is, does any open source implementation of CL implement
hash maps and vectors like this?
Javier <·······@gmail.com> writes:
> So, my question is, does any open source implementation of CL implement
> hash maps and vectors like this?
For hash-tables it may not make much difference time wise (it would
still need much more memory, for each copies, only the stored objects
and keys may be shared, not the table itself).
For vector it would be catastrophic on both dimension. Instead of
having O(1) access time, you get O(log32(N)) access time (and much
more memory is needed).
So, being lucky to have mutable data structure nobody felt the need to
implement inferior immutable versions.
That said, this is not up to an implementation to implement such a
datastructure (given that it's not specified by the standard). If you
need it, implement it yourself. You could even contribute it as a free
library.
--
__Pascal Bourguignon__
Pascal J. Bourguignon wrote:
> Javier <·······@gmail.com> writes:
>> So, my question is, does any open source implementation of CL implement
>> hash maps and vectors like this?
>
> For hash-tables it may not make much difference time wise (it would
> still need much more memory, for each copies, only the stored objects
> and keys may be shared, not the table itself).
>
> For vector it would be catastrophic on both dimension. Instead of
> having O(1) access time, you get O(log32(N)) access time (and much
> more memory is needed).
>
> So, being lucky to have mutable data structure nobody felt the need to
> implement inferior immutable versions.
>
>
> That said, this is not up to an implementation to implement such a
> datastructure (given that it's not specified by the standard). If you
> need it, implement it yourself. You could even contribute it as a free
> library.
http://common-lisp.net/project/fset/
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza escribi�:
> Pascal J. Bourguignon wrote:
>> Javier <·······@gmail.com> writes:
>>> So, my question is, does any open source implementation of CL implement
>>> hash maps and vectors like this?
>>
>> For hash-tables it may not make much difference time wise (it would
>> still need much more memory, for each copies, only the stored objects
>> and keys may be shared, not the table itself).
>>
>> For vector it would be catastrophic on both dimension. Instead of
>> having O(1) access time, you get O(log32(N)) access time (and much
>> more memory is needed).
>>
>> So, being lucky to have mutable data structure nobody felt the need to
>> implement inferior immutable versions.
>>
>>
>> That said, this is not up to an implementation to implement such a
>> datastructure (given that it's not specified by the standard). If you
>> need it, implement it yourself. You could even contribute it as a free
>> library.
>
> http://common-lisp.net/project/fset/
Nice, but how well fset integrates with CL? Can you use aref, assoc,
map, and so on with its collections?
Javier wrote:
> Pascal Costanza escribi�:
>> Pascal J. Bourguignon wrote:
>>> Javier <·······@gmail.com> writes:
>>>> So, my question is, does any open source implementation of CL implement
>>>> hash maps and vectors like this?
>>> For hash-tables it may not make much difference time wise (it would
>>> still need much more memory, for each copies, only the stored objects
>>> and keys may be shared, not the table itself).
>>>
>>> For vector it would be catastrophic on both dimension. Instead of
>>> having O(1) access time, you get O(log32(N)) access time (and much
>>> more memory is needed).
>>>
>>> So, being lucky to have mutable data structure nobody felt the need to
>>> implement inferior immutable versions.
>>>
>>>
>>> That said, this is not up to an implementation to implement such a
>>> datastructure (given that it's not specified by the standard). If you
>>> need it, implement it yourself. You could even contribute it as a free
>>> library.
>> http://common-lisp.net/project/fset/
>
> Nice, but how well fset integrates with CL? Can you use aref, assoc,
> map, and so on with its collections?
Third paragraph of the FSet homepage: "To get started using FSet, check
out the FSet Tutorial. Once you've gone through that, I recommend the
FSet/CL page, which explains how FSet is integrated into Common Lisp."
Just click both links, not just the first one.
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza escribi�:
> Javier wrote:
>> Pascal Costanza escribi�:
>>> Pascal J. Bourguignon wrote:
>>>> Javier <·······@gmail.com> writes:
>>>>> So, my question is, does any open source implementation of CL
>>>>> implement
>>>>> hash maps and vectors like this?
>>>> For hash-tables it may not make much difference time wise (it would
>>>> still need much more memory, for each copies, only the stored objects
>>>> and keys may be shared, not the table itself).
>>>>
>>>> For vector it would be catastrophic on both dimension. Instead of
>>>> having O(1) access time, you get O(log32(N)) access time (and much
>>>> more memory is needed).
>>>>
>>>> So, being lucky to have mutable data structure nobody felt the need to
>>>> implement inferior immutable versions.
>>>>
>>>>
>>>> That said, this is not up to an implementation to implement such a
>>>> datastructure (given that it's not specified by the standard). If you
>>>> need it, implement it yourself. You could even contribute it as a free
>>>> library.
>>> http://common-lisp.net/project/fset/
>>
>> Nice, but how well fset integrates with CL? Can you use aref, assoc,
>> map, and so on with its collections?
>
> Third paragraph of the FSet homepage: "To get started using FSet, check
> out the FSet Tutorial. Once you've gone through that, I recommend the
> FSet/CL page, which explains how FSet is integrated into Common Lisp."
>
> Just click both links, not just the first one.
>
>
> Pascal
>
I'd be very surprised if this has half of the performance of Clojure.
And, manual doesn't say anything about CL integration with current
algorithms in the CL standard. In fact, it uses a different set of
function names.
On Mar 15, 9:47 am, Javier <·······@gmail.com> wrote:
> I'd be very surprised if this has half of the performance of Clojure.
In clojure, when you want speed, you don't use immutable (aka,
"persistent") data. You use java arrays and mutate them. Now you're
back in the same boat as common lisp.
Clojure's persistent sequences are for reasonable amounts of data, and
reasonable performance. For doing something like iterating over the
rgba float pixels of a 35MB image, you probably won't be using
clojure's sequence functions operating on persistent data if you want
good performance.
Javier <·······@gmail.com> writes:
> I'd be very surprised if this has half of the performance of Clojure.
> And, manual doesn't say anything about CL integration with current
> algorithms in the CL standard. In fact, it uses a different set of
> function names.
There's no point in coming back always to the function exported by CL.
The standard specifies that any of the can be open-coded that is,
inlined, and therefore unless you regenerate a new implementation,
they won't ever use new additions to the system in most implementation.
With some implementation, you may be lucky and able to redefine easily
a standard function to use additions, but since most such addition
would render the language or the library function NOT Common Lisp,
there's no point in putting such modified function in the CL package
anyways, they should go to "YOUR-LISP" package instead.
Given the availability of free implementations, and of free
implementations written in Lisp, it should be rather trivial to do:
(defpackage "MY-LISP-WITH-EXTENSIONS"
(:use "CL" "AND-ANY-EXTENSION")
(:export #.(all-symbols-expored-by-cl-and-more)))
(in-package "MY-LISP-WITH-EXTENSIONS")
(load "source-of-cl-libraries.lisp")
and then:
(defpackage "MY-LISP-USER"
(:use "MY-LISP-WITH-EXTENSIONS"))
(in-package "MY-LISP-USER")
(have-fun-with-cl-like-functions-but-with-extensions)
--
__Pascal Bourguignon__
Javier wrote:
> Pascal Costanza escribi�:
>> Javier wrote:
>>> Pascal Costanza escribi�:
>>>> Pascal J. Bourguignon wrote:
>>>>> Javier <·······@gmail.com> writes:
>>>>>> So, my question is, does any open source implementation of CL
>>>>>> implement
>>>>>> hash maps and vectors like this?
>>>>> For hash-tables it may not make much difference time wise (it would
>>>>> still need much more memory, for each copies, only the stored objects
>>>>> and keys may be shared, not the table itself).
>>>>>
>>>>> For vector it would be catastrophic on both dimension. Instead of
>>>>> having O(1) access time, you get O(log32(N)) access time (and much
>>>>> more memory is needed).
>>>>>
>>>>> So, being lucky to have mutable data structure nobody felt the need to
>>>>> implement inferior immutable versions.
>>>>>
>>>>>
>>>>> That said, this is not up to an implementation to implement such a
>>>>> datastructure (given that it's not specified by the standard). If you
>>>>> need it, implement it yourself. You could even contribute it as a free
>>>>> library.
>>>> http://common-lisp.net/project/fset/
>>> Nice, but how well fset integrates with CL? Can you use aref, assoc,
>>> map, and so on with its collections?
>> Third paragraph of the FSet homepage: "To get started using FSet, check
>> out the FSet Tutorial. Once you've gone through that, I recommend the
>> FSet/CL page, which explains how FSet is integrated into Common Lisp."
>>
>> Just click both links, not just the first one.
>>
>>
>> Pascal
>>
>
> I'd be very surprised if this has half of the performance of Clojure.
You will only know by running some serious benchmarks.
> And, manual doesn't say anything about CL integration with current
> algorithms in the CL standard. In fact, it uses a different set of
> function names.
You are contradicting yourself. Either it doesn't say anything about the
integration with CL, or it does say something about it. It's not
possible that both can be true at the same time.
What's your problem?
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Mar 15, 4:44 am, Javier <·······@gmail.com> wrote:
> Pascal Costanza escribió:
> >http://common-lisp.net/project/fset/
>
> Nice, but how well fset integrates with CL? Can you use aref, assoc,
> map, and so on with its collections?
FSet does provide shadowed versions of many of the generic CL sequence
operations -- `subseq', `find', etc. -- so that you can invoke these
operations by familiar names on both FSet and CL collections.
Doing the same with low-level operations like `aref' and `assoc',
however, is more problematic. The problem with `aref' is the meaning
of (setf (aref ...) ...). On a CL array it has to mutate the
sequence; but of course it can't do this on an FSet seq. So it
doesn't entirely make sense for FSet to let you use `aref'. (`elt'
has the same problem.)
The problem with `assoc' is that it is defined too much in terms of
the details of its implementation (it must return the specific cons
whose car is the supplied key; the caller might want to mutate that
cons).
The problem with `map' is different -- the name is shadowed for use as
the `map' constructor macro. I recommend instead my `gmap' macro
which is much more powerful and versatile than CL `map'.
The upshot is, to use FSet you will have to learn some new
vocabulary. I have tried to keep the amount of new vocabulary to a
reasonable minimum, but it was not possible to eliminate it entirely.
-- Scott
J> - (Almost) constant time access to the original map and to the apparent
J> copies of it.
algorithmically we can represent almost anything as "(almost) constant
time",
but there still could be huge performance differences. while there will be
little difference for tree-like structures (e.g. balanced binary trees), for
vectors
overhead would be very significant.
J> - Very little memory penalty.
if we compare it to a full copy, then yes, it is very little. but if we'll
compare
to chaning in place, there will be significant penalty.
J> So, my question is, does any open source implementation of CL implement
J> hash maps and vectors like this?
for Clojure these overheads could be fine, as it does aim to provide
top-notch
performance, but CL's spirit is to provide honest performance
characteristics,
so it would be very strange to see vectors implemented like this in CL.
however,
having real, fast vectors you always can implement immutable ones as you
wish,
so this is left up to libraries and applications.