The Data Structure You Use Matters a Lot
ฝัง
- เผยแพร่เมื่อ 18 มิ.ย. 2024
- The data structure you use matters a lot. Arrays, linked lists, hash tables, queues, stacks - these are just a few data structures being implemented in just one example to showcase why it matters which data structure you choose based on your use case.
If you're a developer, sign up to my free newsletter Dev Notes 👉 www.devnotesdaily.com/
If you're a student, checkout my Notion template Studious: notionstudent.com
Don't know why you'd want to follow me on other socials. I don't even post. But here you go.
🐱🚀 GitHub: github.com/forrestknight
🐦 Twitter: / forrestpknight
💼 LinkedIn: / forrestpknight
📸 Instagram: / forrestpknight
daily dose of data structures
I guess it's good that the first thought that came to my mind when you talked about undo/redo was a stack.
That is the example taught about its utility.
@@insanityrodax8621 oh, I wouldn't know. I'm from India, we are not given examples, or asked to think critically. We are forced to write our answers exactly as it's taught to us, any deviation is worth docking points.
But yes, now that you mentioned it, it does seem like a trivial solution.
I've been following you for years now. Actually diving into code and data structures for one of your videos? Contrasting different language implementations as well? This makes me so happy!
Not me screaming "Stack!!! Stack!!! Stack!!! 😫" At the beginning of the video.
The level of storytelling you have is amazing, happily subscribed
If you want to display the undo/redo list to the user though you will just default to a fully capable dynamic/resizable array, where you have constant access time on a fixed buffer for storing your operations. There are also history trees where you follow branches, in which case you use a graph and stop caring about the tiny fraction of a memory you consume on the pointers themselves, compared to the cost of carrying the data for the operations themselves, or the state checkpoints that you may need in certain occasions.
These videos are making me dream about code almost every night and that's why I just subscribed
Please make more videos like this, I love them and they also shape your thinking as a computer scientist
Thank you very much
Earned yourself a clean subscribe.👍 The code blocks, the execution, explanation, interaction laid it all for me. Keep creating bro.
uhhhh these videos are just getting better and better! well thought out, respect
This links nicely to the command pattern. I had to implement a history feature in a unity application I was doing, utilising the stack datatype for this very reason. Thanks for the clear video.
let me give you a better solution, (im replying to the first part of the video) so take one array and a int maybe a i8 or i16 (for code editors, taking a smaller number to save memory + i dont think a person would be doing more than 200 writes especially because nowadays we dont record changes to every individual characters instead we use a time) so lets say im on the 5th change so the index variable will be at 4 and then lets say i do undo then simply do this:
index -= 1;
return arr[index];
and when we wanna redo, simply do this:
if(!arr[index+1]) return error
index += 1
return arr[index]
and if u wanna write a new change do this:
index =+ 1
return arr[index]
I was thinking the same thing; why not just use an index or pointer to keep track of the current state in an array? I thought it was weird how he was just using an array as a stack.
This is one of the best videos I have watched of you.
As someone who needs to use data structures in my code, I think this is the best and most succinct video I have seen. It combines code and visual. Usually, you get one or the other.
Gold star! Smashed the like button!
I go one better, a doubly linked list forwards and backwards with a current pointer that you update when you push onto the history and if you undo you just move current to the previous state and redo moves to the next state. Then you write in some control functionality for the maximum size of the "window" you're going to keep in memory before chopping off nodes from the head/tail of the list to keep the windows within bounds.
I have been trying to do this, cause why not, so I looked into editor implementations the easier ones were Nano, and the most daunting ones were the Vim/Neovim with over 3000 lines of C code. This approach is more structured than Nano and Emacs, the vim's approach uses both Command and Memento patterns.
It is litery mind boggling how the undo/redo is implemented in vim/nvim and also in another editors, i learned a lot through them(though still trying to understand the vim's implementation better).
You should also talk about the patterns used to do this. You should also talk about 🌲 ds which are used in the above implementations.
This was a brilliant video⚡, gotta try this out today! 👨🏼💻
digging the animations!
Saving this video to when I finish my data structures course
Nice way of teaching data structure
I love these. I'll say it a million times if I have to
A DEQUEUE is a verb, while A DEQUE is a data structure. HOW AM I SUPPOSED TO SLEEP TONIGHT HEARING SOMEONE REPLACING A NOUN WITH A VERB.
Hahaha... A nerd and a charmer. I'm in love ! Great video mate !
Great vid.
what tool do you use to create these animations by the way? (I mean the code and the other stuff). Thanks in advance.
And yet for maintaining history I would much rather have a tree. This simple approach to undo and redo has the unfortunate side effect that if you make changes after undoing the redo stack is cleared. The data structure you use matters a lot not just for performance but for functionality too.
Interesting video! While stacks are a common starting point for undo/redo, more complex scenarios might benefit from structures like undotrees. They allow for non-linear editing histories and multiple 'undo' paths. It's a good reminder to keep exploring data structure options as the problem complexity grows.
I love it when I undo/redo and accidentally type one latter so VScode can't anymore follow the path backwards
You dont need two stacks for all actions + undone actions. You can just use a single stack with two sizes, with the second meaning how far you actually are.
thank you man 🙌👌
1:06 I guess there is a mistake in function undo(). Function would remove two lasts elements, instead only one. Is that right?
yes. i think this would be better
if (history.lenght > 0) {
redoArray.push(history.pop());
return history.lastElement();
}
not sure if "lastElement()" is valid in this labguage, but you get the idea
Thanks
Forrest you look like a real cowboy now! 🤠 🐎
Can't for the life of me remember who said it, but there was one guru back when who allegedly said that if he was abandoned on a desert island and could take only one data structure with him, other than a scalar and an array which were already there, it would have to be a hash-table :)
Great video! Can you advise what you would start with/use to create a Film database, currently living in a Filemaker Pro database? It's a very large database (2500+ blu-Ray DVD) not to play, just to "house" and possibly keep track of loaning out to someone. I currently use VSC with CSS, HTML, JavaScript. I also use MongoDB and Postman. I'd like to create something that doesn't "look" like a database. Thanks in advance.
Don't use plain HTML and JavaScript. Use a js framework like react or solid
It sounds like you have a working system and just need to develop a new ui for it. Basically you just need to show movies in a list or a grid instead of a table.
Start with a list item or grid item, essentially how one single movie listing would look, then make it work in a list. You might need a menu to select between 'my movies', 'avaliable movies' or whatever.
Another commenter recommended a framework like react or solid. You can go that route, but it's not necessary, and may incur an additional learning curve. I haven't used any of them much, but Vue and HTMX seem to have pretty low learning curves. I played with Vue a little, and I've just seen vids about HTMX but it looks good.
@@reed6514 Thank you! I can use React or Solid.
Somebody add this video to every data structures class
That could've been a dynamically sized circular buffer 😅
can u make examples video like when do we use dsa in own projects
Good idea. I'll definitely do that
@@fknight glad to see that soon
Hey forest man, that's very cool shirt, would you share name of brand.
Deck is the superior pronunciation. De-queue, could be confused with the operation that a Deck supports.
That is all. Amazing video though!
I’ll really have to warm up to it the use of deck. I really don’t like it lol but I do see your point. That’s valid
Ironically, I find implementing simple data structures like stacks and queues easier in C than in other languages with maybe the exception of Assembly for stacks since it’s built in.
q-woo-woo... I lost it xD
I like this man. He's cool
More dsa please 😊
awesome video code jesus
Goat
Does anybody here know what happened to Forrest's coding DevNotes series? Clearly he removed them but does anybody know why?
They're still available for viewing on this playlist: th-cam.com/play/PLp_L1ltSVItxLzsF7599xtBPQm6hQ05MV.html
I marked them as unlisted to clean things up, and I felt they didn't represent my typical content.
And just to update you on the project itself, it's a hobby project in terms of priority and I've just been too busy to work on it. Hopefully I can get around to finishing it up soon.
but what about tree?
Forrest couldn't see the tree... He couldn't see the Forest for the... damn it, there's a joke here somewhere
Can break in most cases:
Change
Undo
Change
Undo
Redo
Redo
Broken
However, if undo/redo limited state (like fixed configurations) this could still work
Yeah, I was thinking of something similar to this as it doesn't appear that previous states would be removed after multiple undos and a change, and thus using the redo function would cause now irrelevant states to come back.
I saw another comment on this video that was talking about how the implementation of undo/redo in NeoVim/Vim had 3k+ lines of code, so it's definitely a tricky issue (or just tedious).
i'm watching this video as I take a break from writing C code rn...
For undo/redo you need only ONE stack
deque = double ended queue
bro thank you its de-queue not d-eck
first and grate vid
🙏👍👊👏🤓💯
Vim uses an undo tree. Just sayin'.
One answer : Stack
please be my college professor
Regarding the Python post you mention, this is my comment there. "100% of this text is wrong, you are confusing python with its default implementation Cpython, on the other hand, all those problems that you say are from "python" are a consequence of its misuse and a rampant ignorance about good practices when it comes to using python, that way of working makes you eventually end up with garbage code regardless of the language".
so basically, they are all the same thing but with different name for things. got it
I am actually having a hard time to comprehand if this guy is trolling or actually a youtuber who pretends to know programming. This is the least informative video I have ever witnessed. He gives a bunch of examples saying they are wrong while not actually explaining how they are wrong (clue - I am pretty sure he does not know why), proceeds to implement a Stack via heap allocations and calls it a linked list .
Later talks about a hash table for god knows what reason and concludes that a stack is the best way to do everything because it does not use nodes (except it does). A stack won't use nodes and dynamic allocation only if implemented on top of a static array, which he starts the video saying is not good because they are not "effecient" as they have a fixed size("not suitable" might be a better word but i gave up on him using the correct terminolagy as he used array and list interchangably).
Thats 80% of the video.
The other 20% of the video is him mumbling about how he maybe should have used c, then maybe python, but he likes switching, so JS it is, and then you sign to their newspaper.
This is the most moronic tech channel I have witnessed, and the fact you have 500K subscribes gives me hope that anyone can appear to be successful if he pays enough for bots.
What!?! Python is not the best tool for every job!?! My world is fine, thanks anyway
what I don't get is why any of this matters, with computers having gigabytes of ram and cpus that do billions of instructions per second then unless you are programming something in an embedded device or some low level performance critical videogame code then it just doesn't matter what you choose. I would think you should do it in the most elegant and mantainable way for the programming language you have (?)
And you had to mention JavaScript.
ctrl+U and ctrl+R for VIM btw. use VIM btw.
You look like a Walking Dead character.
As long as you don't think I look like a Walker, I'll take it lol