Not if items are covered by other items. You’ve got a layer of fast L1 cache that is O(1), but exceed the limit of that layer by placing an item of clothing on top of it, and some elements are effectively “pushed down” to a higher latency tier, which is going to be closer to O(log N) as you have to move some percentage of the items out of the way to get to the target item. Cache eviction (doing the laundry) will reset this.
As always careful optimisation of the cache size, in relation to the expected distribution of items to be accessed, is key to maximising performance.
Sure, the more clothes are on top, the longer it takes. But Big O notation is only useful if the N gets very big. And considering that the naximum amount of clothes is likely very small, it can be treated as O(1).
If there’s one layer of clothes then you’re correct, it O(1). On further thought deeper piles are not O(log N), but O(N). Once the number of items exceeds C it takes more than a single operation to retrieve an item from the bottom layer, and the number of operations is proportional to the number of layers, or N/C.
If you consider either picking an item up or moving it aside as a single operation, then retrieval from a single layer take 1 operation, and is O(1), but retrieval from the bottom of a two layer pile actually takes 3 operations (move the top item, retrieve the target item, replace the top item into the bottom layer, or you risk getting a deeper pile in one slot in the pathalogical case). Retrieval from the bottom of 3 layers takes 5 operations (move, move, take, replace, replace). in other words we have an O(1) process for taking the target item, and an O(N/C)=O(N) process for uncovering it in the first place, giving O(N) over all.
Your statement that “considering that the naximum amount of clothes is likely very small, it can be treated as O(1).” is true iff N<=C, which, I concede, is a likely scenario in any well managed laundry pile, hence comment about cache sizing.
notabot@piefed.social 4 weeks ago
Not if items are covered by other items. You’ve got a layer of fast L1 cache that is O(1), but exceed the limit of that layer by placing an item of clothing on top of it, and some elements are effectively “pushed down” to a higher latency tier, which is going to be closer to O(log N) as you have to move some percentage of the items out of the way to get to the target item. Cache eviction (doing the laundry) will reset this.
As always careful optimisation of the cache size, in relation to the expected distribution of items to be accessed, is key to maximising performance.
yetAnotherUser@discuss.tchncs.de 4 weeks ago
Nope. Assume the chair fits at most C clothes, with C being a constant.
The efficiency is at worst O© = O(C * 1) = C * O(1) = O(1).
Sure, the more clothes are on top, the longer it takes. But Big O notation is only useful if the N gets very big. And considering that the naximum amount of clothes is likely very small, it can be treated as O(1).
notabot@piefed.social 4 weeks ago
If there’s one layer of clothes then you’re correct, it O(1). On further thought deeper piles are not O(log N), but O(N). Once the number of items exceeds C it takes more than a single operation to retrieve an item from the bottom layer, and the number of operations is proportional to the number of layers, or N/C.
If you consider either picking an item up or moving it aside as a single operation, then retrieval from a single layer take 1 operation, and is O(1), but retrieval from the bottom of a two layer pile actually takes 3 operations (move the top item, retrieve the target item, replace the top item into the bottom layer, or you risk getting a deeper pile in one slot in the pathalogical case). Retrieval from the bottom of 3 layers takes 5 operations (move, move, take, replace, replace). in other words we have an O(1) process for taking the target item, and an O(N/C)=O(N) process for uncovering it in the first place, giving O(N) over all.
Your statement that “considering that the naximum amount of clothes is likely very small, it can be treated as O(1).” is true iff N<=C, which, I concede, is a likely scenario in any well managed laundry pile, hence comment about cache sizing.