Learn More
Resend Email
13
trekhleb
2y

Recently I launched the minimalistic online drawing app https://okso.app. I wanted it to be a place where people could do fast, ad-hoc, napkin-based-like explanations of any concept as if you are sitting with your friend and trying to explain him/her something during lunch. Don't ask me why it is needed, I was just experimenting.

So, the first concept I've tried to explain with sketches was the Data Structures. Without further ado, here is the interactive ✍🏻 https://okso.app/showcase/... showcase that you may play with.

Of course, not all data structures are covered. And of course, this is not comprehensive material, but rather a cheatsheet that would create visual hints and associations for the following data structures:

- Linked List
- Doubly Linked List
- Queue
- Stack
- Hash Table (with hash collision resolution)
- Tree (including the Binary Search Tree)
- Heap (including Mean Heap and Max Heap)
- Trie
- Graph

Each box on the sketch is clickable, so you may dig into the data structure you're interested. For example `Heap → Max Heap`, or `Heap → Min Heap`, or `Heap → Array Representation`.

The sketches are split into so-called Pages just to make it easier to grasp them, so the users stay focused on one concept at a time, they see the relationship between the concept, and thus, hopefully, they are not getting overwhelmed with seeing a lot of information at the same time on one drawing/page.

Each page has a link to the source-code examples that are implementing the data structure on JavaScript.

The full list you may find in the ✍🏻 https://okso.app/showcase/... showcase.

I hope you find this showcase useful and I hope it will be a good visual cheatsheet-like complement to your data structure knowledge.

devrant

beginners

coding

programming

visualisation

tutorials

webdev
Favorite
Ranter
Comments
  • 1
    2y
    This pretty sexy bro I might have to use this when I’m teaching my classmates 👀👀
  • 2
    2y
    That's super janky on a phone.

    I'd suggest revisiting the hash table at least, you say "what if a hash function isn't perfect" resulting in collisions, even a perfect hash function will result in collisions, just with lower probability. The quality of a hash function is about where entropy is distributed.
  • 0
    2y
    @atheist yeah, the performance is a big issue, for now, it is pretty slow (on the phone especially) and there are some issues with zooming/panning. I plan to investigate and optimize it.

    About the perfect hash function... This is a matter of wording, isn't it? I mean... under certain restrictions, depending on the task we're solving the function may be perfect, right? Let's say I want to store the Names of the users for every telephone number in my city. With these restrictions we may say, the telephone number has the format of XXX-XX-XX (i.e. 456-56-23). The hash function might be as simple/stupid as concatenation of all digits into string "XXXXXXX" (i.e. it may produce the "4565623" as a key). Let's say we have 10.000.000 slots of memory (each may contain the Name of the person, if we say the max Name length is 100). This way we will not have any collision, right? And the function is perfect in this case I guess
  • 0
    2y
    @coolguy101 Cool! I hope this app could help with that! :)
  • 0
    2y
    * - ah, yes, about the collison comment above, I meant "concatenated" to a number 4565623 (not a string) and than mapping this number to the address 1:1
  • 1
    2y
    @trekhleb You're not trying to get rid of all collisions in a hash table, because that would mean you're wasting space; you're trying to keep table size as close to the data as possible, with collisions evenly distributed across every slot in the table.

    There's another thing to pay attention to, since you mentioned phone numbers. Phone numbers generally have a fixed part (e.g. an area code) and a random part (the rest). If you decided to, say, have 10.000 slots and take the first 4 digits as your hash, most data would be allocated to the same slots because they all start with the same code. The same thing happens with hashes, e.g. if your hash goes from 0 to 128 and your table has 20 slots, then 12 slots will have the probability of 6/128, and 8 slots will have the collision probability of 7/128, because 128 = 20 * 6 + 8 - that's why you always want to set table size such that all hashes can be evenly divided into every slot.
  • 0
    2y
    So, I think you're conflating 2 different concepts. There's a "mathematically good" hash function, which spreads entropy across the entire output, ie a small change in input should result in a large change in output randomly distributed across the output bits. This gives a low probability of collisions. Then there's the solution you're talking about, where the aim is no collisions (which isn't really the point of hash tables. As long as the number of collisions is low, you get constant time operations, *that's* the important bit), you're thinking of a hash table too much like an array.
  • 0
    2y
    @atheist @hitko Hey, folks, I think we’re talking about different things

    Your comments are valid, but it is not about me “trying to get rid of all collisions in a hash table" or me "thinking of a hash table too much like an array". That's why there is a hash function, collision resolution section, and linked lists described in the Sketches.

    The comment I addressed with my a bit artificial example (with XXX-XX-XX numbers) was: “I'd suggest revisiting the hash table at least” because "even a perfect hash function will result in collisions” and thus using the phrase “what if a hash function isn't perfect" in Sketches is invalid.

    What forbids us from coming up with artificial constraints (i.e. limited set of keys XXXXXXX, enough memory cells. etc.), where we can actually say that 0% collision is possible? It is rare, maybe it is not a real-life example. However, the wording of “what if a hash function isn't perfect" looks not that invalid in this case, doesn't it?
  • 2
    2y
    If its possible to design a "hash" function so that there are zero collisions with 100% occupied cells, you're better off using an array. Hash maps by design will internally grow when they are about 70% full, because with even a very good hash function, that's the point at which the number of likely collisions start to degrade performance.
  • 1
    2y
    The "hash" that you're describing is a coordinate transform more than an actual hash function, and lacks the properties of a good hash function, so I disagree that "perfection" applies.
  • 1
    2y
    Looks absolutely gorgeous with this minimalistic design. I had to bookmark it. :D

    Just a few UX issues I have as feedback:

    - The colour selection button seems like a minus sign/dash, so at first, I thought it was a zoom-out button since it's close to the zoom options. I would consider moving it to the centre, maybe? Also, I could imagine it having a different shape.

    - In my opinion, the undo and redo buttons shouldn't be hidden on desktop, where there is enough space. It's just an unnecessary extra step to perform before actually doing the stuff.

    It's so easy to use, that I went a little overboard with my ideas :D
  • 1
    2y
    @Lasoloz nice sketch! :)

    Yes, good idea not to hide the "Undo/Redo" buttons on the desktop. I'll probably change that.

    With the Color button, yeah, I agree, the "minus-like" looking issue is there. The reason to have a "minus" is that the button does two things: shows the currently selected color AND the currently selected stroke size. But maybe on the desktop, I need to also expand this button into two separate ones... I need to try

    But thanks for the ideas and especially for the sketch! :D
Related Rants
devRant © 2021 Hexical Labs LLC
Privacy Policy  |  Terms of Service
Add Comment