• argv_minus_one@beehaw.org
    4·
    1 year 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.

    • IronDonkey@lemmy.world
      3·
      1 year 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.

      • jcg@halubilo.social
        2·
        1 year 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.