[HN Gopher] Data Structures Sketches
___________________________________________________________________
Data Structures Sketches
Author : kevinslin
Score : 131 points
Date : 2022-10-09 17:42 UTC (5 hours ago)
(HTM) web link (okso.app)
(TXT) w3m dump (okso.app)
| gfd wrote:
| 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)
|
| But this link is using the non technical definition (drawings)
| n3t wrote:
| A non-mobile link:
| https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
| threatofrain wrote:
| This is a Very Small sequence of data structures...
| sidlls wrote:
| It's uncommon that more than the ones presented will be
| necessary for the majority of applications, though.
| marginalia_nu wrote:
| 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 wrote:
| 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 wrote:
| 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.
| [deleted]
| photochemsyn wrote:
| 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-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).
| minitoar wrote:
| 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.
| morelisp wrote:
| 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.
| jltsiren wrote:
| CS is built on abstractions, which make things more modular and
| easier to think about.
|
| A data structure can be seen as an interface, a logical
| structure, a physical layout, or an encoding. When you teach
| them, you have to start from somewhere. The logical structure
| is usually a good choice, because it contains the key ideas of
| the structure. If you cram in too many details and too many
| levels of abstraction, you are just going to confuse the
| audience.
| Valmar wrote:
| > CS is built on abstractions, which make things more modular
| and easier to think about.
|
| CS also leads to generally garbage performance with its
| abstractions, because computers simply don't function
| according to assumptions of CS...
|
| Better to teach people how computers actually work, and then
| go from there.
|
| Doesn't feel particularly surprising anymore that software
| has been getting slower far more quickly than hardware can
| get faster.
| marginalia_nu wrote:
| 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 wrote:
| What's the preferred way of implementing a binary tree, and
| how much more efficient is it over just nodes and references?
| educaysean wrote:
| 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 wrote:
| 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.
| [deleted]
| minaguib wrote:
| Cool material, but happy to have been exposed to okso.app as a
| (newcomer?) free online sketching tool (a-la excalidraw, a
| bit...)
___________________________________________________________________
(page generated 2022-10-09 23:00 UTC)