I've got my copy of Cormen, Leiserson, and Rivest's book with me now, which is the 3rd edition, and looking in the index under "persistent" it does have one exercise in chapter 13 on that topic, and a mention later in the book that is a paragraph or two long with a reference to a research paper.
So while that book isn't a good reference for persistent data structures in particular, it is a good reference for the more widely known (and some not-so-widely known) mutable data structures. If you learn at least a few of those, then you are very well prepared to understand Clojure's persistent data structures, too, and there are blog posts on the topic that can get you a lot of the way there (once you understand the basics), e.g.: http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice/ The book does assume a knowledge of how basic arrays work, but those are quite simple and hopefully my message below is nearly as much as there is to know about them. To get an understanding of data structures like hash tables and some different kinds of trees, you can probably get there just reading a few of the introductory sections at the beginning, and then jump to those specific sections. Save all the stuff on algorithms for when and if you are interested. Andy On Mar 18, 2012, at 8:57 PM, Andy Fingerhut wrote: > Feel free to ask follow-up questions on the basics privately, since many > Clojure programmers are probably already familiar with them, whereas > follow-up questions on persistent data structures are very on-topic, since I > would guess many people who have studied computer science and/or programming > for a while may not be familiar with them. > > The classic model of an array is based upon the implementation of physical > RAM in a computer: a physical RAM, at a high level and leaving out details of > variations, is a device where you either give it a command READ and an > address, and it returns an 8-bit byte stored at that location, or you give it > a WRITE command, an address, and an 8-bit value, and it stores the 8-bit > value at the location given by the address. > > A classic array is a one-dimensional structure indexed by an integer i, > usually from 0 up to some maximum value N, and every item in the array stores > an item of the same size and type, e.g. all 32-bit integers, or all pointers > to some object elsewhere in the memory. If every item fits in exactly B > bytes, and the first item of the array begins at address A in the memory, > then item i will be at address A+B*i in the memory. In terms of performance, > computers are designed to be able to access any address in their memory in > the same amount of time, no matter what address it is stored at, so with a > couple of instructions to calculate A+B*i, the computer can read or write any > element of an array within a constant amount of time (constant meaning it > doesn't get larger or smaller depending upon the size of the array -- it is > always the same no matter the array's size). With other non-array data > structures like trees, accessing an element takes longer as the data > structure grows to contain more items. > > I don't recall if it covers persistent data structures like the ones most > commonly used in Clojure, but Cormen, Leiserson, and Rivest's "Introduction > to Algorithms" is used in many colleges as a text in courses on algorithms > and data structures. There are probably other books that would be better as > a "primer", and it does assume you are comfortable with at least algebra and > a bit more math, but if you got through a chapter of it and understood even > half of it, you'd have learned something worth knowing about the subject. > > http://www.amazon.com/Introduction-Algorithms-Includes-CD-Rom-Thomas/dp/0072970545/ref=sr_1_2?ie=UTF8&qid=1332128117&sr=8-2 > > There is a newer edition than the one I linked to, but an older used copy for > $25.00 might be closer to what you want if you aren't sure yet. > > Andy > > On Mar 15, 2012, at 12:15 PM, Nic Long wrote: > >> Hi all, >> >> I am starting to learn Clojure after buying the book 7 Languages in 7 >> Weeks (really interesting read) and working through the examples >> there. But my background is PHP (and no Computer Science degree) so my >> understanding of data structures and in general, my understanding of >> low-level CS ideas, is pretty limited to say the least - PHP only has >> arrays (which I read are only 'ordered hash tables' in fact) and >> objects so I've never had to think hard about which data structures to >> use, nor how they actually work. >> >> So I guess I'm asking whether anyone can recommend some good primers >> on data structures, both as they relate to Clojure, but also how they >> work in the fundamentals - e.g. what exactly is the classic model of >> an 'array' and how does it work, etc. I have read the various >> performance commitments for the data-types in Clojure on the .org site >> but even things like Big O notation are still pretty new to me. >> >> I'm sure this stuff is pretty basic for many, but I don't know it and >> would like to! >> >> I'm not afraid of some heavy reading; I'd rather get a really deep and >> solid grasp of the fundamentals, then a quick surface-level solution. >> If I'm to develop as a programmer I feel like I need to get looking >> under the hood as it were, even though I can get by in PHP (for the >> most part anyway) without this kind of understanding. >> >> Thanks in advance, >> >> Nic >> >> -- >> You received this message because you are subscribed to the Google >> Groups "Clojure" group. >> To post to this group, send email to [email protected] >> Note that posts from new members are moderated - please be patient with your >> first post. >> To unsubscribe from this group, send email to >> [email protected] >> For more options, visit this group at >> http://groups.google.com/group/clojure?hl=en > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/clojure?hl=en
