6 ms·

Data Structures Sketches

274 points by kevinslin 4y ago

gfd 4y ago
To save someone a click, "sketch" has a technical definition when it comes to data structures (probabilistic data structures like count min sketch https://en.m.wikipedia.org/wiki/Count%E2%80%93min_sketch https://en.m.wikipedia.org/wiki/Count%E2%80%93min_sketch) But this link is using the non technical definition (drawings)
- n3t 4y ago
  A non-mobile link: https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
threatofrain 4y ago
This is a Very Small sequence of data structures...
- sidlls 4y ago
  It's uncommon that more than the ones presented will be necessary for the majority of applications, though.
  - deleted 4y ago
    [deleted]
  - marginalia_nu 4y ago
    Necessary? Maybe not. Useful? More often than you'd think, in more domains than you'd think. Basic probabilistic structures like bloom filters and the hyperloglog in particular are severely slept on.
    - morelisp 4y ago
      Forget probabilistic structures, any intro to data structures that doesn't show you a deque built with a ring buffer is shit, and I'll die on that hill. (That being said, I'm tweaking something in the ASketch family as we speak, so I agree 100%.)
  - morelisp 4y ago
    You could literally only have "hash table" and this would be true for "necessary for the majority". But maybe we should raise the bar a little bit.
minitoar 4y ago
This reminds me of some interview questions I was asked at Looker like 7 years ago. I felt silly drawing a stack and a queue but in hindsight I think it’s a good way to get some insight into a candidate’s intuition on these things.
- kergonath 4y ago
  I’m glad I am not alone.
deleted 4y ago
[deleted]
morelisp 4y ago
Oh good, another generation of of programmers with their brains stuck thinking about box-and-arrow diagrams and have no clue how to store a binary tree in a way that don't blow your cache or a graph in an adjacency matrix.
- educaysean 4y ago
  Wait, there are people out there that don't know what you know? Sound the alarms everyone! These new generation of amateurs are going to ruin everything!
  - morelisp 4y ago
    You're making a personal issue out of a pedagogical complaint. Which one of us is approaching this poorly? It's not the next generation's fault you've utterly failed them.
    - spinlock 4y ago
      I think you’re overestimating the demand for people who can implement a binary tree. Then again, when I used to work more with node, I would complain daily that those kids were just reimplementing solved problems in computing … poorly. I’m working more with elixir these days and everything is so fast that I’ve never stopped to dig into the implementation.
- marginalia_nu 4y ago
  Yeah, I was thinking this as well. This box and line diagram style is so far away how you would implement many of these structures that you might not recognize them if you saw them.
  - woojoo666 4y ago
    What's the preferred way of implementing a binary tree, and how much more efficient is it over just nodes and references?
minaguib 4y ago
Cool material, but happy to have been exposed to okso.app as a (newcomer?) free online sketching tool (a-la excalidraw, a bit...)
- pelasaco 4y ago
  that's was probably the intention behind this post...
photochemsyn 4y ago
These kinds of diagrams are OK for the most basic introduction to data structures, but they're not much help when it comes to creating an efficient implementation. Learning about data structure implementation without using a relatively low-level language that allows pointers seems to be a recipe for confusion. Hence, one is probably always better off using the built-ins or libraries for any data structure in a higher-level language rather than implementing them from scratch. For example, here's a nice blog post on how Python dicts are implemented using hash tables written in C. https://www.laurentluce.com/posts/python-dictionary-implementation/ https://www.laurentluce.com/posts/python-dictionary-implemen... While it's possible to build something like a binary search tree from scratch in Python using classes for nodes and with references instead of pointers, along with recursive algorithms for traversing it, it doesn't seem like that great of an idea to teach students in this manner. If the goal is to really teach students how to do this, C or similar (Rust?) is probably the better option for code examples, and a lot of time would have to be spent on memory management concepts (i.e. have students build their own dynamically allocated stack for the traversal, to avoid blowing through the stack, maybe).
- raydiatian 4y ago
  Yeah, this website is kind of like porting Windows 95 to the Apple Watch. It dies immediately after its esoteric novelty. > Learning about data structure implementation without using a relatively low-level language that allows pointers seems to be a recipe for confusion. All things considered, one should absolutely do data structures in a pointer-based language, eventually. I think learning CS concepts is inherently fraught with false certainty in your grasp on it early on. I’m pretty sure I did data structures in Java first, though, followed by cpp. I personally can’t see pointer jitsu having made it necessarily easier in my first bout with the concepts. Although there is certainly something to be said for the non-magicalness of doing your own memory management.
spinlock 4y ago
I wish the icon for hash tables was better. The rest are excellent but the hash table just falls back on a common syntax. It bugs me how much this bugs me.
quadrifoliate 4y ago
The notation of head ← n for "n is stored in head" was mainly responsible for my confusion in reading CLRS for the first time. Even now, it really breaks the flow of reading this pseudocode for me, and I'm not quite sure why. Has anyone else struggled with this, and have suggestions on how to rewire my brain so the notation "flows" better?
- pasquinelli 4y ago
  it's just a different symbol from the usual assignment operator, that is to say "put the value you're referring to as `n` in the variable `head`", just like `head = n` in most languages with assignment. the only reason for the arrow is if you're using `=` for true equality, as in `head` is always the same as the value `n`, or if you wanted to use `=` to mean `equals?`, a boolean test for momentary equality. i don't know if any of that helps, it all just comes down to recognizing the symbol and interpreting it correctly.
- deredede 4y ago
  I have no tips, but I share the pain. My intuitive reaction when seeing an arrow is that it changes the text direction, and I do not give semantic meaning to the arrow direction. Iow, my brain essentially treats `a <- b` and `b -> a` identically. This is the usual way that directional operators work in maths: comparisons, set membership and inclusion, implication (to be fair the symmetric version is rare enough), etc.
- derekbaker783 4y ago
  There are programming languages where that syntax is used for assignments to mutable vars (F# being one example). Maybe play around with a language that uses that syntax? https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/values/#mutable-variables https://learn.microsoft.com/en-us/dotnet/fsharp/language-ref...
  - quadrifoliate 4y ago
    This is an excellent suggestion! I was going to say that the only place I have seen arrows used are either struct membership in C or the fat arrow function in JS, and neither of those go from right to left. So playing around with F# might help.
eps 4y ago
All I see at the link is a loading spinner. Using an iPad.

274 points by kevinslin 4y ago

gfd 4y ago

To save someone a click, "sketch" has a technical definition when it comes to data structures (probabilistic data structures like count min sketch https://en.m.wikipedia.org/wiki/Count%E2%80%93min_sketch https://en.m.wikipedia.org/wiki/Count%E2%80%93min_sketch) But this link is using the non technical definition (drawings)

n3t 4y ago
A non-mobile link: https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch

threatofrain 4y ago

This is a Very Small sequence of data structures...

sidlls 4y ago
It's uncommon that more than the ones presented will be necessary for the majority of applications, though.
- deleted 4y ago
  [deleted]
- marginalia_nu 4y ago
  Necessary? Maybe not. Useful? More often than you'd think, in more domains than you'd think. Basic probabilistic structures like bloom filters and the hyperloglog in particular are severely slept on.
  - morelisp 4y ago
    Forget probabilistic structures, any intro to data structures that doesn't show you a deque built with a ring buffer is shit, and I'll die on that hill. (That being said, I'm tweaking something in the ASketch family as we speak, so I agree 100%.)
- morelisp 4y ago
  You could literally only have "hash table" and this would be true for "necessary for the majority". But maybe we should raise the bar a little bit.

minitoar 4y ago

This reminds me of some interview questions I was asked at Looker like 7 years ago. I felt silly drawing a stack and a queue but in hindsight I think it’s a good way to get some insight into a candidate’s intuition on these things.

kergonath 4y ago
I’m glad I am not alone.

deleted 4y ago

[deleted]

morelisp 4y ago

Oh good, another generation of of programmers with their brains stuck thinking about box-and-arrow diagrams and have no clue how to store a binary tree in a way that don't blow your cache or a graph in an adjacency matrix.

educaysean 4y ago
Wait, there are people out there that don't know what you know? Sound the alarms everyone! These new generation of amateurs are going to ruin everything!
- morelisp 4y ago
  You're making a personal issue out of a pedagogical complaint. Which one of us is approaching this poorly? It's not the next generation's fault you've utterly failed them.
  - spinlock 4y ago
    I think you’re overestimating the demand for people who can implement a binary tree. Then again, when I used to work more with node, I would complain daily that those kids were just reimplementing solved problems in computing … poorly. I’m working more with elixir these days and everything is so fast that I’ve never stopped to dig into the implementation.
marginalia_nu 4y ago
Yeah, I was thinking this as well. This box and line diagram style is so far away how you would implement many of these structures that you might not recognize them if you saw them.
- woojoo666 4y ago
  What's the preferred way of implementing a binary tree, and how much more efficient is it over just nodes and references?

minaguib 4y ago

Cool material, but happy to have been exposed to okso.app as a (newcomer?) free online sketching tool (a-la excalidraw, a bit...)

pelasaco 4y ago
that's was probably the intention behind this post...

photochemsyn 4y ago

These kinds of diagrams are OK for the most basic introduction to data structures, but they're not much help when it comes to creating an efficient implementation. Learning about data structure implementation without using a relatively low-level language that allows pointers seems to be a recipe for confusion. Hence, one is probably always better off using the built-ins or libraries for any data structure in a higher-level language rather than implementing them from scratch. For example, here's a nice blog post on how Python dicts are implemented using hash tables written in C. https://www.laurentluce.com/posts/python-dictionary-implementation/ https://www.laurentluce.com/posts/python-dictionary-implemen... While it's possible to build something like a binary search tree from scratch in Python using classes for nodes and with references instead of pointers, along with recursive algorithms for traversing it, it doesn't seem like that great of an idea to teach students in this manner. If the goal is to really teach students how to do this, C or similar (Rust?) is probably the better option for code examples, and a lot of time would have to be spent on memory management concepts (i.e. have students build their own dynamically allocated stack for the traversal, to avoid blowing through the stack, maybe).

raydiatian 4y ago
Yeah, this website is kind of like porting Windows 95 to the Apple Watch. It dies immediately after its esoteric novelty. > Learning about data structure implementation without using a relatively low-level language that allows pointers seems to be a recipe for confusion. All things considered, one should absolutely do data structures in a pointer-based language, eventually. I think learning CS concepts is inherently fraught with false certainty in your grasp on it early on. I’m pretty sure I did data structures in Java first, though, followed by cpp. I personally can’t see pointer jitsu having made it necessarily easier in my first bout with the concepts. Although there is certainly something to be said for the non-magicalness of doing your own memory management.

spinlock 4y ago

I wish the icon for hash tables was better. The rest are excellent but the hash table just falls back on a common syntax. It bugs me how much this bugs me.

quadrifoliate 4y ago

The notation of head ← n for "n is stored in head" was mainly responsible for my confusion in reading CLRS for the first time. Even now, it really breaks the flow of reading this pseudocode for me, and I'm not quite sure why. Has anyone else struggled with this, and have suggestions on how to rewire my brain so the notation "flows" better?

pasquinelli 4y ago
it's just a different symbol from the usual assignment operator, that is to say "put the value you're referring to as `n` in the variable `head`", just like `head = n` in most languages with assignment. the only reason for the arrow is if you're using `=` for true equality, as in `head` is always the same as the value `n`, or if you wanted to use `=` to mean `equals?`, a boolean test for momentary equality. i don't know if any of that helps, it all just comes down to recognizing the symbol and interpreting it correctly.
deredede 4y ago
I have no tips, but I share the pain. My intuitive reaction when seeing an arrow is that it changes the text direction, and I do not give semantic meaning to the arrow direction. Iow, my brain essentially treats `a <- b` and `b -> a` identically. This is the usual way that directional operators work in maths: comparisons, set membership and inclusion, implication (to be fair the symmetric version is rare enough), etc.
derekbaker783 4y ago
There are programming languages where that syntax is used for assignments to mutable vars (F# being one example). Maybe play around with a language that uses that syntax? https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/values/#mutable-variables https://learn.microsoft.com/en-us/dotnet/fsharp/language-ref...
- quadrifoliate 4y ago
  This is an excellent suggestion! I was going to say that the only place I have seen arrows used are either struct membership in C or the fat arrow function in JS, and neither of those go from right to left. So playing around with F# might help.

eps 4y ago

All I see at the link is a loading spinner. Using an iPad.