1112

I won't let Big Closet tell me how to live my life. Rule. (lemmy.blahaj.zone)

submitted 1 year ago by yttrium@lemmy.blahaj.zone to c/196@lemmy.blahaj.zone

23 comments fedilink hide all child comments

all 25 comments

sorted by: hot top controversial new old

[-] yetAnotherUser@feddit.de 48 points 1 year ago* (last edited 1 year ago)

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 >:(

[-] funnystuff97@lemmy.world 22 points 1 year ago

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)

[-] yetAnotherUser@feddit.de 7 points 1 year ago

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.

[-] Cralder@feddit.nu 10 points 1 year ago

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.

[-] yetAnotherUser@feddit.de 5 points 1 year ago

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).

[-] Cralder@feddit.nu 7 points 1 year ago

I feel like this metaphor is getting out of hand

[-] rasensprenger@feddit.de 6 points 1 year ago

As the volume of the room is finite, even "exponential" or worse search algorithms will complete in constant time.

[-] yetAnotherUser@feddit.de 3 points 1 year ago

<.<

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.

[-] rasensprenger@feddit.de 4 points 1 year ago

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.

[-] funnystuff97@lemmy.world 7 points 1 year ago* (last edited 1 year ago)

A cache is not a stack, it's memory stored in parallel cells. The CPU could theoretically, depending on the implementation, directly find the data it's looking for by going to the address of the cell it remembers that it's in.

Not all L1 caches operate the same, but in almost all cases, it's easy to actually go and get the data no matter where it physically is. If the data is at address 0 or at address 512, they both take the same time to fetch. The problem is if you don't know where the data is, in which case you have to use heuristics to guess where it might be, or in the worst case check absolutely everywhere in the cache only to find it at the very last place... or the data isn't there at all. In which case you'd check L2 cache, or RAM. The whole purpose of a cache is to randomly store data there that the CPU thinks it might need again in the future, so fast access is key. And in the most ideal case, it could theoretically be done in O(1).

ETA: I don't personally work with CPUs so I could be very wrong, but I have taken a few CPU architecture classes.

[-] BluesF@feddit.uk 6 points 1 year ago

I think the previous commenters point was that to get to something at the bottom of a pile of clothes, even if you know where it is, you have to move everything from on top of it, like a stack.

[-] yttrium@lemmy.blahaj.zone 10 points 1 year ago* (last edited 1 year ago)

Huh, TIL about big theta

[-] saigot@lemmy.ca 4 points 1 year ago

There's also big omega (lower bound)

[-] optimal@lemmy.blahaj.zone 1 points 1 year ago

what's the difference?

[-] darcy@sh.itjust.works 42 points 1 year ago

its O(n^2), but better than O(n) for small values of n

[-] Franzia@lemmy.blahaj.zone 15 points 1 year ago

Oh omg. Have I been coding this whole time?

[-] n0m4n@lemmy.world 8 points 1 year ago

Our clothes' storage has been set up next to our dryer, which, in turn, is by the shower. I also switched to a mix and match wardrobe that are my series of 'uniforms'. This combination simplifies my mornings to an extreme that works well for me.

[-] jaywalker@lemm.ee 5 points 1 year ago

Get dressed in dirty clothes, take a shower, and then get inside the dryer wearing your freshly showered clothes. Now you can wear the same thing all the time.

[-] Tischkante@discuss.tchncs.de 6 points 1 year ago

What if my cat peed on it.

[-] yttrium@lemmy.blahaj.zone 15 points 1 year ago

Cache poisoning

[-] hungryphrog@lemmy.blahaj.zone 3 points 1 year ago

Free parfume!

[-] TheCoolerMia@lemmy.blahaj.zone 3 points 1 year ago

EXACTLY!! If I'm going to use something in the next 48 hours I'm not going to hide it away?! But my desk did get a little messy lately and I'll have to reorganize it when I get home so thanks for the accidental reminder :3