9 ms·

Itsy Bitsy Data Structures – Simplified examples of many common data structures

223 points by thejameskyle 10y ago

deleted 10y ago
[deleted]
notsorandomname 10y ago
Hash table realization seems to be harmful with the "no collisions" assumption. That's like writing a red black tree and assuming that insert/delete operations will keep tree balanced so we don't need rotations.
- duaneb 10y ago
  Yea, a hash table without even bucketing(?) is laughably useless.
- elliotec 10y ago
  At least the ASCII art for the hash table section was pretty funny.
- ksk 10y ago
  How is it harmful? You really think that somebody who is going to write a red black tree implementation (or similar) is going to use this document as a reference? That'd be like complaining about a high school physics textbook because somebody from Boeing might use it to design a plane.
  - hexane360 10y ago
    I'm not sure I understand. OP just made an analogy to red black trees. He's not suggesting anyone will make bad trees because of this document. He's just saying that the hash table is pretty useless if two random keys could access the same memory.
    - ksk 10y ago
      >He's just saying that the hash table is pretty useless if two random keys could access the same memory. That is already mentioned in the document itself. Also mentioned is that a proper implementation would have to deal with collisions. As to it being useless.. the value of content is in its explanation of simple concepts, not in some imagined production-quality requirement that people want to assume it must have.
      - coldtea 10y ago
        >As to it being useless.. the value of content is in its explanation of simple concepts, not in some imagined production-quality requirement that people want to assume it must have. The value of an explanation of simple concepts is in their simple AND adequate explanation. You can cut the implementation details, but can't cut essential properties to simplify, because then you're not explaining the original concept at all.
  - xg15 10y ago
    Some simplifications may actually be harmful to understanding if they throw away key points or introduce logical contradictions. For a hash table, the general "promise" is that you map a very large space of keys (e.g. all strings) to a very small space of indexes using a simple function. Common sense might tell you that this shouldn't be possible ("how can you put something big into something small?") - and of course actual hash tables solve the conundrum by acknowledging collisions and defining ways to deal with them. But by saying "let's assume no collisions" the reader is asked to just ignore the logical contradiction instead of solving it. That can lead to frustration in the best case or to serious misconceptions in the worst case. Of course there is nothing wrong with saying "let's ignore those points for now, I'll explain later". Also I guess it depends very much on the learning style of the reader. But bad simplification can be very annoying for some learners.
    - ksk 10y ago
      >For a hash table, the general "promise" is that you map a very large space of keys (e.g. all strings) to a very small space of indexes using a simple function Well, AFAICT there is no mention of any of this in the document. No "promise" or any such thing has been said or implied. Please stick to what the author has actually said rather than what you imagine people are thinking about when reading the document. >. Common sense might tell you that this shouldn't be possible ("how can you put something big into something small?") No, it doesn't tell me that at all, because that point is not brought up in the document. But is that how you think most people learn? Using common sense? >But by saying "let's assume no collisions" the reader is asked to just ignore the logical contradiction instead of solving it. Sure, you think those are the logical contradictions in the readers' minds. Can you actually establish that? > But bad simplification can be very annoying for some learners. A list of what is annoying for "some" learners is quite possibly very very large. Lets not.... -- Anyway, we can go down this rabbit hole, but it isn't actually productive, and quite boring to be honest. My point is that every-time someone tries simplify something for beginners, people seem to relish that opportunity to show everyone how "smart" they are about trivial data-structures. Yes, if you want somebody to make an expository article for beginners with the detail of something like TAOCP, then yeah, you're going to be disappointed. But, you can and should learn Newtonian physics, even if its "wrong", before you move on to Einstein.
mthoms 10y ago
At first glance, this looks like it could be a useful reference. Regardless it's worth a visit for the ASCII art alone. My favorite: the literal interpretation of "hash tables".
vonmoltke 10y ago
> algorithms are implemented with data structures Eh, for a certain definition of "algorithm". Plenty of signal processing algorithms, for instance, have nothing to do with data structures.
- jjnoakes 10y ago
  I would consider the signal's value over time to be a sequence.
  - vonmoltke 10y ago
    Algorithms that work over multiple samples are not tied to a data structure, except in an overly broad and useless sense of "data structure". A time or frequency series is not a data structure. It can be stored in any of several data structures, with various pros and cons depending on other circumstances, but the choice of data structure has nothing to do with the algorithm.
    - squeaky-clean 10y ago
      > It can be stored in any of several data structures, with various pros and cons depending on other circumstances, but the choice of data structure has nothing to do with the algorithm. It has nothing to do with the theory of the algorithm. But everything to do with the implementation. So I think the original statement is true. > algorithms are implemented with data structures
      - riboflava 10y ago
        Where are the data structures? [0] MIN := X[N]; k := N; for j := N-1 step -1 until 1 do if X[j] < MIN then begin MIN := X[j]; k := j; end; [0] https://assets.cs.ncl.ac.uk/seminars/139.pdf https://assets.cs.ncl.ac.uk/seminars/139.pdf
        icebraining 10y ago
zeusk 10y ago
This is too dumbed down, imo. Also, the part where it explains why memory is zero-addressed is so wrong, it rustled my jimmies.
- ksk 10y ago
  >This is too dumbed down, imo. That is why the word 'simplified' appears in the title, and the words 'super simplified' appear in the linked document. The purpose is to convey a point, and take away other distractions. Its probably not a good idea to introduce calculus to first graders either. If you don't think omitted content is a distraction, then it's probably not meant for you.
noobermin 10y ago
One thing's for sure, it caught my attention. Humungo text that made me chuckle. Then, I clicked on the text, and it was the example. Pretty clever.
jscheel 10y ago
Seems to be a lot of snark in this thread already. If you see a problem, create an issue or submit a pull request. It's great that OP is trying to help spread knowledge.
kylehotchkiss 10y ago
Question: for the hashtables example, it looks like it's setting arbitrary indexes inside a JS array, instead of incrementing ones. IIRC, Javascript stringifys arrays with gaps like this: [ 1,2,3,undefined/null,undefined/null,undefined/null,undefined/null,undefined/null,4,5,6,undefined/null,undefined/null,undefined/null] - With the hashtables function, if you accidentally generate an index that is say 100,000, wouldn't you end up with an unwieldy-sized array that would be more difficult to search than one like this: [{ value: 1, index: 103405}, { value: 2, index: 14550 }] Or does JS store the arrays as an object internally and just stringify them with all the blanks?
- wolf550e 10y ago
  JS engines have both sparse and dense representations for arrays and array instances switch from one to another when you insert and delete elements. Details are of course implementation defined.
marvy 10y ago
Most languages have a built in type for a dynamic array, but many of them lack a built-in queue. I have a favorite trick for a quick-and dirty queue in those languages. You need an array (initially empty) and an integer (initially zero). To add to the queue, add to the array. To get the front of the queue, just do array[int]. And finally, to remove from the queue, simply increment the integer. The advantages of this approach are simplicity and speed: each operation takes amortized constant time. The obvious disadvantage is that it's potentially a major memory leak. For instance, if you try to do breadth-first search of a tree using this queue, your memory usage will be proportional to the size of the tree. How much worse than optimal is this? It depends on the tree. If it's a complete binary tree, you've doubled your memory usage, which might not be too bad. But if the tree is a path, then you use linear memory, whereas a proper queue would only use O(1) memory.
- lliiffee 10y ago
  You could periodically delete the wasted space. I think that if you, say, delete the wasted space when it is equal to the used space, you still still have O(1) amortized time.
  - marvy 10y ago
    You could, but then it's not quite so quick-and-dirty anymore :) The de-queue method goes from "self.i += 1" (Python syntax) to self.i +=1 if self.i > len(self.a)/2: self.a[:self.i] = [] self.i = 0 I didn't test the above code, and I am only 50% sure it is bug-free. I'm 99% sure the leaky version is bug-free. Memory leaks are not a bug if I document them, right? ;) But yes, periodically deleting the wasted space is still easier than trying to do the usual thing with circular buffers and stuff :)
    - lliiffee 10y ago
      I definitely see your point! I guess there is a place for algorithms at any point on the easy/good trade-off.
    - andrepd 10y ago
andrepd 10y ago
I have 2 issues with this. First, you could say what you wanted to say in 1/3rd of the length if you weren't speaking in such a conversational manner and interspersing your discourse with irrelevant jokes and stuff like ""OOooooOOOooh soo exciting" right?". I don't read stuff on data structures to amuse myself. I want it to be as succint and to the point as possible and not waste my time kidding around. If I want to kid around I will do something else. But I guess some people prefer this, I suppose. Second, I don't think the best place to go on lengthy explanations with figures included is in the comments of a source code file. Markdown is your friend.
- weatherlight 10y ago
  lighten up :) the giant "Itsy Bitsy Data Structures" in itself was pretty light hearted.
- seagreen 10y ago
  I have 2 issues with this [..] I don't read stuff on data structures to amuse myself. I want it to be as succint and to the point as possible and not waste my time kidding around. Someone should write a serious data structures book for you. Oh wait, they have, there are literally hundreds of them. If you're attacking a topic with your full attention then you want maximum information as fast as possible. If you're tired on a friday and want to learn something and have fun then information density doesn't matter anymore.
- TuringNYC 10y ago
  There is no shortage of Algorithms and Data Structures books. But different people prefer different styles of learning and interaction. This meets the needs for some people. I appreciated it and encourage James Kyle to continue his great effort.
- mcbits 10y ago
  I can't speak for everyone, but I read conversational prose a lot faster than dense technical writing. If I were to read enough of each style to absorb the same amount of information, I don't think it's safe to assume I would spend less time on the dense material just by virtue of its length.
medecau 10y ago
This is a safe-space! Keep critical opinions out of the comment section. Thank you.
thejameskyle 10y ago
Hi I wrote this thing. I guess I'll comment on this thread since it got some attention. I think a lot of people that are in this thread went into this project with the complete wrong state of mind. I'm not trying to teach people how a hash table or linked list implementation works. I'm not trying to make a library that is useful to anyone. What I'm trying to do is connect the dots between a bunch of different important concepts in data structures. People can go read things about each of these individual topics to great length and I encourage them too, but in general there are a lot of great computer science resources for just piecing a lot of related topics together for beginners. Sure you can read a 600 page book that will cover things from end to end, but those are very intimidating when you have no prior knowledge of the topic and sometimes you don't get as much out of them if you don't know the basics. If I can provide people with just a quick highlight reel of essential knowledge of data structures then I've done what I set out to do. I hope Hacker News can appreciate that, I don't expect it to, but I can hope.
- Jizzle 10y ago
  As someone who has implemented all these before, I thought the presentation was great. Yes, there are some holes, but in under 1500 lines, ASCII art and all, a lot was covered. More importantly, the ideas put forward can always be built upon--more data structures, more talk about time/space complexity or even probability (e.g. bloom filters), forays into solving famous problems with those data structures (optimally or not), etc, etc. Whether this is the first and final installment or not, it's a nice contribution.
- posterboy 10y ago
  I didn't read it, because I know the topic already, but also because I found it too long for an overview. If the crowd with reduced attention span is your target group, this doesn't work. This would amount to a 20 pages perhaps. I'd assume that's roughly how much it would need in the 600 page book, too. Also, there is no TOC to gloss over, the ascii, cute as it is, is harder to fly over than legit text with embedded code snippets.
  - thejameskyle 10y ago
HiroshiSan 10y ago
This is fucking awesome, did you draw the ascii pictures yourself?

223 points by thejameskyle 10y ago

deleted 10y ago

[deleted]

Hash table realization seems to be harmful with the "no collisions" assumption. That's like writing a red black tree and assuming that insert/delete operations will keep tree balanced so we don't need rotations.

duaneb 10y ago
Yea, a hash table without even bucketing(?) is laughably useless.
elliotec 10y ago
At least the ASCII art for the hash table section was pretty funny.
ksk 10y ago
How is it harmful? You really think that somebody who is going to write a red black tree implementation (or similar) is going to use this document as a reference? That'd be like complaining about a high school physics textbook because somebody from Boeing might use it to design a plane.
- hexane360 10y ago
  I'm not sure I understand. OP just made an analogy to red black trees. He's not suggesting anyone will make bad trees because of this document. He's just saying that the hash table is pretty useless if two random keys could access the same memory.
  - ksk 10y ago
    >He's just saying that the hash table is pretty useless if two random keys could access the same memory. That is already mentioned in the document itself. Also mentioned is that a proper implementation would have to deal with collisions. As to it being useless.. the value of content is in its explanation of simple concepts, not in some imagined production-quality requirement that people want to assume it must have.
    - coldtea 10y ago
      >As to it being useless.. the value of content is in its explanation of simple concepts, not in some imagined production-quality requirement that people want to assume it must have. The value of an explanation of simple concepts is in their simple AND adequate explanation. You can cut the implementation details, but can't cut essential properties to simplify, because then you're not explaining the original concept at all.
- xg15 10y ago
  Some simplifications may actually be harmful to understanding if they throw away key points or introduce logical contradictions. For a hash table, the general "promise" is that you map a very large space of keys (e.g. all strings) to a very small space of indexes using a simple function. Common sense might tell you that this shouldn't be possible ("how can you put something big into something small?") - and of course actual hash tables solve the conundrum by acknowledging collisions and defining ways to deal with them. But by saying "let's assume no collisions" the reader is asked to just ignore the logical contradiction instead of solving it. That can lead to frustration in the best case or to serious misconceptions in the worst case. Of course there is nothing wrong with saying "let's ignore those points for now, I'll explain later". Also I guess it depends very much on the learning style of the reader. But bad simplification can be very annoying for some learners.
  - ksk 10y ago
    >For a hash table, the general "promise" is that you map a very large space of keys (e.g. all strings) to a very small space of indexes using a simple function Well, AFAICT there is no mention of any of this in the document. No "promise" or any such thing has been said or implied. Please stick to what the author has actually said rather than what you imagine people are thinking about when reading the document. >. Common sense might tell you that this shouldn't be possible ("how can you put something big into something small?") No, it doesn't tell me that at all, because that point is not brought up in the document. But is that how you think most people learn? Using common sense? >But by saying "let's assume no collisions" the reader is asked to just ignore the logical contradiction instead of solving it. Sure, you think those are the logical contradictions in the readers' minds. Can you actually establish that? > But bad simplification can be very annoying for some learners. A list of what is annoying for "some" learners is quite possibly very very large. Lets not.... -- Anyway, we can go down this rabbit hole, but it isn't actually productive, and quite boring to be honest. My point is that every-time someone tries simplify something for beginners, people seem to relish that opportunity to show everyone how "smart" they are about trivial data-structures. Yes, if you want somebody to make an expository article for beginners with the detail of something like TAOCP, then yeah, you're going to be disappointed. But, you can and should learn Newtonian physics, even if its "wrong", before you move on to Einstein.

mthoms 10y ago

At first glance, this looks like it could be a useful reference. Regardless it's worth a visit for the ASCII art alone. My favorite: the literal interpretation of "hash tables".

vonmoltke 10y ago

> algorithms are implemented with data structures Eh, for a certain definition of "algorithm". Plenty of signal processing algorithms, for instance, have nothing to do with data structures.

jjnoakes 10y ago
I would consider the signal's value over time to be a sequence.
- vonmoltke 10y ago
  Algorithms that work over multiple samples are not tied to a data structure, except in an overly broad and useless sense of "data structure". A time or frequency series is not a data structure. It can be stored in any of several data structures, with various pros and cons depending on other circumstances, but the choice of data structure has nothing to do with the algorithm.
  - squeaky-clean 10y ago
    > It can be stored in any of several data structures, with various pros and cons depending on other circumstances, but the choice of data structure has nothing to do with the algorithm. It has nothing to do with the theory of the algorithm. But everything to do with the implementation. So I think the original statement is true. > algorithms are implemented with data structures
    - riboflava 10y ago
      Where are the data structures? [0] MIN := X[N]; k := N; for j := N-1 step -1 until 1 do if X[j] < MIN then begin MIN := X[j]; k := j; end; [0] https://assets.cs.ncl.ac.uk/seminars/139.pdf https://assets.cs.ncl.ac.uk/seminars/139.pdf
      - icebraining 10y ago

zeusk 10y ago

This is too dumbed down, imo. Also, the part where it explains why memory is zero-addressed is so wrong, it rustled my jimmies.

ksk 10y ago
>This is too dumbed down, imo. That is why the word 'simplified' appears in the title, and the words 'super simplified' appear in the linked document. The purpose is to convey a point, and take away other distractions. Its probably not a good idea to introduce calculus to first graders either. If you don't think omitted content is a distraction, then it's probably not meant for you.

noobermin 10y ago

One thing's for sure, it caught my attention. Humungo text that made me chuckle. Then, I clicked on the text, and it was the example. Pretty clever.

jscheel 10y ago

Seems to be a lot of snark in this thread already. If you see a problem, create an issue or submit a pull request. It's great that OP is trying to help spread knowledge.

kylehotchkiss 10y ago

Question: for the hashtables example, it looks like it's setting arbitrary indexes inside a JS array, instead of incrementing ones. IIRC, Javascript stringifys arrays with gaps like this: [ 1,2,3,undefined/null,undefined/null,undefined/null,undefined/null,undefined/null,4,5,6,undefined/null,undefined/null,undefined/null] - With the hashtables function, if you accidentally generate an index that is say 100,000, wouldn't you end up with an unwieldy-sized array that would be more difficult to search than one like this: [{ value: 1, index: 103405}, { value: 2, index: 14550 }] Or does JS store the arrays as an object internally and just stringify them with all the blanks?

wolf550e 10y ago
JS engines have both sparse and dense representations for arrays and array instances switch from one to another when you insert and delete elements. Details are of course implementation defined.

marvy 10y ago

Most languages have a built in type for a dynamic array, but many of them lack a built-in queue. I have a favorite trick for a quick-and dirty queue in those languages. You need an array (initially empty) and an integer (initially zero). To add to the queue, add to the array. To get the front of the queue, just do array[int]. And finally, to remove from the queue, simply increment the integer. The advantages of this approach are simplicity and speed: each operation takes amortized constant time. The obvious disadvantage is that it's potentially a major memory leak. For instance, if you try to do breadth-first search of a tree using this queue, your memory usage will be proportional to the size of the tree. How much worse than optimal is this? It depends on the tree. If it's a complete binary tree, you've doubled your memory usage, which might not be too bad. But if the tree is a path, then you use linear memory, whereas a proper queue would only use O(1) memory.

lliiffee 10y ago
You could periodically delete the wasted space. I think that if you, say, delete the wasted space when it is equal to the used space, you still still have O(1) amortized time.
- marvy 10y ago
  You could, but then it's not quite so quick-and-dirty anymore :) The de-queue method goes from "self.i += 1" (Python syntax) to self.i +=1 if self.i > len(self.a)/2: self.a[:self.i] = [] self.i = 0 I didn't test the above code, and I am only 50% sure it is bug-free. I'm 99% sure the leaky version is bug-free. Memory leaks are not a bug if I document them, right? ;) But yes, periodically deleting the wasted space is still easier than trying to do the usual thing with circular buffers and stuff :)
  - lliiffee 10y ago
    I definitely see your point! I guess there is a place for algorithms at any point on the easy/good trade-off.
  - andrepd 10y ago

andrepd 10y ago

I have 2 issues with this. First, you could say what you wanted to say in 1/3rd of the length if you weren't speaking in such a conversational manner and interspersing your discourse with irrelevant jokes and stuff like ""OOooooOOOooh soo exciting" right?". I don't read stuff on data structures to amuse myself. I want it to be as succint and to the point as possible and not waste my time kidding around. If I want to kid around I will do something else. But I guess some people prefer this, I suppose. Second, I don't think the best place to go on lengthy explanations with figures included is in the comments of a source code file. Markdown is your friend.

weatherlight 10y ago
lighten up :) the giant "Itsy Bitsy Data Structures" in itself was pretty light hearted.
seagreen 10y ago
I have 2 issues with this [..] I don't read stuff on data structures to amuse myself. I want it to be as succint and to the point as possible and not waste my time kidding around. Someone should write a serious data structures book for you. Oh wait, they have, there are literally hundreds of them. If you're attacking a topic with your full attention then you want maximum information as fast as possible. If you're tired on a friday and want to learn something and have fun then information density doesn't matter anymore.
TuringNYC 10y ago
There is no shortage of Algorithms and Data Structures books. But different people prefer different styles of learning and interaction. This meets the needs for some people. I appreciated it and encourage James Kyle to continue his great effort.
mcbits 10y ago
I can't speak for everyone, but I read conversational prose a lot faster than dense technical writing. If I were to read enough of each style to absorb the same amount of information, I don't think it's safe to assume I would spend less time on the dense material just by virtue of its length.

medecau 10y ago

This is a safe-space! Keep critical opinions out of the comment section. Thank you.

thejameskyle 10y ago

Hi I wrote this thing. I guess I'll comment on this thread since it got some attention. I think a lot of people that are in this thread went into this project with the complete wrong state of mind. I'm not trying to teach people how a hash table or linked list implementation works. I'm not trying to make a library that is useful to anyone. What I'm trying to do is connect the dots between a bunch of different important concepts in data structures. People can go read things about each of these individual topics to great length and I encourage them too, but in general there are a lot of great computer science resources for just piecing a lot of related topics together for beginners. Sure you can read a 600 page book that will cover things from end to end, but those are very intimidating when you have no prior knowledge of the topic and sometimes you don't get as much out of them if you don't know the basics. If I can provide people with just a quick highlight reel of essential knowledge of data structures then I've done what I set out to do. I hope Hacker News can appreciate that, I don't expect it to, but I can hope.

Jizzle 10y ago
As someone who has implemented all these before, I thought the presentation was great. Yes, there are some holes, but in under 1500 lines, ASCII art and all, a lot was covered. More importantly, the ideas put forward can always be built upon--more data structures, more talk about time/space complexity or even probability (e.g. bloom filters), forays into solving famous problems with those data structures (optimally or not), etc, etc. Whether this is the first and final installment or not, it's a nice contribution.
posterboy 10y ago
I didn't read it, because I know the topic already, but also because I found it too long for an overview. If the crowd with reduced attention span is your target group, this doesn't work. This would amount to a 20 pages perhaps. I'd assume that's roughly how much it would need in the 600 page book, too. Also, there is no TOC to gloss over, the ascii, cute as it is, is harder to fly over than legit text with embedded code snippets.
- thejameskyle 10y ago

HiroshiSan 10y ago

This is fucking awesome, did you draw the ascii pictures yourself?