this post was submitted on 19 Oct 2023
0 points (NaN% liked)
196
16459 readers
33 users here now
Be sure to follow the rule before you head out.
Rule: You must post before you leave.
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
Why would you use a pile out of all data structures, only adding is in ϴ(1), searching is in ϴ(n).
I suggest throwing the clothes on the floor and remembering the spot they landed on. That's ϴ(1) for adding and for searching, far superior to a stack of clothes on a chair.
Side note: fuck big O notation, use big ϴ notation >:(
i think that's the point, it's not a "messy pile", it's actually a completely organized cache; depending on the replacement policy it can appear messy, but you keep the offset and address stored locally for fast access and more hits (i remember that i put some arguably clean socks somewhere in the corner over there)
Ok, I didn't understand roughly half of your comment because I don't actually know how cache works in practice
BUT
a messy pile of clothes represents a stack, doesn't it? And a stack makes a horrible cache because unlike a simple array you don't have fast random access. You'd have to dig through the entire pile of clothes to get to the bottom which takes a lot of time.
Not necessarily. If you know that your pants are at the bottom then you can just plunge your hand into the pile and grab them without any searching.
Thay depends on the size of the pile, there could be a lot of weight and instability above the pants and you'll have to pull them out à la Jenga or carefully rearrange the stack.
Since the amount of rearranging increases for larger n (imagine a pile reaching the ceiling), searching is in ω(1).
I feel like this metaphor is getting out of hand
As the volume of the room is finite, even "exponential" or worse search algorithms will complete in constant time.
<.<
Well, there's only finitely many atoms in the universe, do all algorithms therefore have constant time?
Although you could argue for very large amounts of clothes my method of throwing clothes on the floor starts performing worse due to clothes falling on the same spot and piling up again.
Unless you extend your room. Let's take a look at the ✨amortized✨time complexity.
Well landau notation only describes the behaviour as an input value tends to infinty, so yes, every real machine with constant finite memory will complete everything in constant time or loop forever, as it can only be in a finite amount of states.
Luckily, even if our computation models (RAM/TM/...) assume infinite memory, for most algorithms the asymptotic behaviour is describing small-case behaviour quite well.
But not always, e.g. InsertionSort is an O(n^2) algorithm, but IRL much faster than O(n log n) QuickSort/MergeSort, for n up to 7 or so. This is why in actual programs hybrid algorithms are used.