argv_minus_one 22 points 3 years ago

Finding clothes on a chair isn't constant-time. You have to search through the heap of clothes to find the item you want. It has the same time complexity as searching through the closet; it's only fast because n is small.

path: 0 274748, hotness: undefined, score: 22, children: 4

omenmis 7 points 3 years ago

It takes 2 pause cycles, that's essentially O(1) compared to a cache miss.

save

path: 0 274748 279925, hotness: undefined, score: 7, children: 1

jcg 14 points 3 years ago

You could implement in-closet indexing instead to make the cache misses hurt less, trading off some extra insertion time but needing less memory for the cache which is much more expensive cost wise. At this point you're storing almost your whole DB in the cache and your room's a mess.

save

path: 0 274748 279925 282417, hotness: undefined, score: 14, children: 0

IronDonkey 3 points 3 years ago

This assumes you're looking for a particular item of clothing. It's true that the clothes cache is not optimized for that.

However, if you are instead looking for a shirt, a pair of pants, and/or so on, without regards to which specific shirt, and if the cache is randomly sorted and the distribution of all such items is roughly equal, then it becomes O(1) - regardless of the size of the cache, you'll get what you want within 4 or 5 checks. Plus, you typically want one of each of the types of item, and you'll get all of them within those same 4 or 5 checks.

Bonus: the checks can be parallelized by using a "wide" cache that enables multiple items to be checked at once. This is why I use a short and wide clean clothes basket and a tall and skinny dirty clothes basket.

save

path: 0 274748 884502, hotness: undefined, score: 3, children: 0

asdfasdfasdf 1 point 3 years ago

save

path: 0 274748 2133296, hotness: undefined, score: 1, children: 0

SpezCanLigmaBalls 13 points 3 years ago

I’ve been subscribed to this subreddit for years and so much shit is way over my head lol

save

path: 0 269956, hotness: undefined, score: 13, children: 2

Deebster 2 points 3 years ago

I'm really confused by this - is this a bot reposting replies that don't work because the context has changed or is this some super-meta content that I'm whooshing on.

save

path: 0 269956 287987, hotness: undefined, score: 2, children: 1

SpezCanLigmaBalls 8 points 3 years ago

No I’m just stupid

save

path: 0 269956 287987 288714, hotness: undefined, score: 8, children: 0

Kettlepants 11 points 3 years ago

I like this logic.

save

path: 0 280368, hotness: undefined, score: 11, children: 0

darcy 11 points 3 years ago

I just expand my L1 cache to half my wardrobe hehe