Re: understanding data structures, and other low-level stuff
Just want to say I sent this before all the other comments - including the talk by Danie Spiewak and the Sedgewick and Wayne book on Algorithms - so I'll definitely have a look at those too. Thanks again for all the advice! On Mar 20, 6:45 pm, Nic Long nicolasl...@gmail.com wrote: Hey, just want to say thanks for all the advice! And Andy especially for the kind offer - I may well PM some specific questions once I start reading. The Cormen et al. book looks great - tough but exactly what I need - so I'm going to pick up a copy. And I'll also read the PhD thesis on Functional Data Structures suggested by Nuno. On Mar 19, 8:02 pm, Nuno Marques nuno.filipe.marq...@gmail.com wrote: This book: Purely Functional Data Structureshttp://www.cs.cmu.edu/~rwh/theses/okasaki.pdf is a good read. Though, It only contains a small reference (half a page) about persistent data structures. On Mar 19, 2012, at 7:28 PM, Andy Fingerhut wrote: 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-persis... 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/... There is a newer edition than the one I linked to, but an older used copy for $25.00 might
Re: understanding data structures, and other low-level stuff
On 03/15/2012 09:15 PM, Nic Long wrote: 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. I can't recommend Sedgewick and Wayne's Algorithms [1] enough. It's not heavy reading at all; I'm amazed at how readable the book is considering the subject matter. In addition to the great writing the algorithms are presented as Java source code, and their operation is visualized, so you have three ways of looking at each algorithm, which really helps to understand them. The book is also excellently structured, only introducing a handful of new concepts at a time, so reading it cover to cover you will very rarely feel out of your depth. [1] http://amzn.com/032157351X -- Timo -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: understanding data structures, and other low-level stuff
I have to tip my hat to Daniel Spiewak's talk at Clojure/conj 2011: http://blip.tv/clojure/daniel-spiewak-extreme-cleverness-functional-data-structures-in-scala-5970151 I learned a lot from it. Cheers, '(Devin Walters) On Tuesday, March 20, 2012 at 12:56 PM, Timo Mihaljov wrote: On 03/15/2012 09:15 PM, Nic Long wrote: 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. I can't recommend Sedgewick and Wayne's Algorithms [1] enough. It's not heavy reading at all; I'm amazed at how readable the book is considering the subject matter. In addition to the great writing the algorithms are presented as Java source code, and their operation is visualized, so you have three ways of looking at each algorithm, which really helps to understand them. The book is also excellently structured, only introducing a handful of new concepts at a time, so reading it cover to cover you will very rarely feel out of your depth. [1] http://amzn.com/032157351X -- Timo -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com (mailto:clojure@googlegroups.com) Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com (mailto:clojure+unsubscr...@googlegroups.com) 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 clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: understanding data structures, and other low-level stuff
Hey, just want to say thanks for all the advice! And Andy especially for the kind offer - I may well PM some specific questions once I start reading. The Cormen et al. book looks great - tough but exactly what I need - so I'm going to pick up a copy. And I'll also read the PhD thesis on Functional Data Structures suggested by Nuno. On Mar 19, 8:02 pm, Nuno Marques nuno.filipe.marq...@gmail.com wrote: This book: Purely Functional Data Structureshttp://www.cs.cmu.edu/~rwh/theses/okasaki.pdf is a good read. Though, It only contains a small reference (half a page) about persistent data structures. On Mar 19, 2012, at 7:28 PM, Andy Fingerhut wrote: 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-persis... 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/... 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
Re: understanding data structures, and other low-level stuff
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=UTF8qid=1332128117sr=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
Re: understanding data structures, and other low-level stuff
This book: Purely Functional Data Structures http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf is a good read. Though, It only contains a small reference (half a page) about persistent data structures. On Mar 19, 2012, at 7:28 PM, Andy Fingerhut wrote: 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=UTF8qid=1332128117sr=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,
understanding data structures, and other low-level stuff
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 clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: understanding data structures, and other low-level stuff
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=UTF8qid=1332128117sr=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 clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com 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 clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: understanding data structures, and other low-level stuff
On Sun, Mar 18, 2012 at 11:57 PM, Andy Fingerhut andy.finger...@gmail.com wrote: 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. Funny you should mention that. Guess what there's always a copy of on the shelf directly above my computer in my office. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
