4 ms·

I don't think it's so clear-cut that the capacity should be decreased in that case, because it not only destroys the theoretical complexity of algorithms using

by _flux 2y ago

I don't think it's so clear-cut that the capacity should be decreased in that case, because it not only destroys the theoretical complexity of algorithms using it, but also because in practice there can be cases where an array gets increased to 1000000 elements, then it gets consumed to 0 elements, after which it again is increased to 1000000 elements for the next round of operations. Converting the array to be backed by a smaller allocation is not free. Indeed, which case is even more common: large arrays getting smaller and then kept that way, or large arrays getting smaller to grow again later? I suppose some more complicated metric (e.g. keeping track of reallocations per array) could help with the most common cases.

csjh 2y ago
Decreasing capacity wouldn't affect the theoretical complexity of algorithms using it - same concept as increasing capacity during push still being amortized O(1)
- _flux 2y ago
  I don't think it works that way when a container can grow and shrink, because an algorithm can trigger those operations any number of times, not just O(log(n)) times.
  - csjh 2y ago
    I'm not sure where you're getting O(logn) from here. If it couldn't work that way when a container can grow and shrink, then arrays wouldn't be able to have both amortized O(1) push and pop as they do in most relevant implementations. As long as the expensive O(n) resize operation happens at some frequency relative to the size of the container rather than every constant size difference (i.e. capacity doubles when length == capacity and halves when length == capacity/2) then it will amortize out to O(1). There's a proof available in section 2.1.2 of this textbook: https://opendatastructures.org/ods-java/2_1_ArrayStack_Fast_Stack_O.html https://opendatastructures.org/ods-java/2_1_ArrayStack_Fast_...
deleted 2y ago
[deleted]
lifthrasiir 2y ago
You have a good point. Unless JS exposes some API to directly control the capacity, we have to guess which use cases are more common and which use cases are fine to ignore. On the other hands though, JS's lack of capacity control means that developers are not conscious about the memory usage after all and JS engines have to do something about that anyway. Indeed, if you look at the actual bug [1], one commentator does mention exactly what I have said: > This is a great idea! Both shift() and pop() can treat the elements array as a dequeue. A "shrink capacity to 1/2 when usage is <1/3" would give us O(1) amortized performance for shift() and pop(), while avoid edge cases where we keep shrinking/growing for alternating add/remove ops around the shrink/grow boundary. [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1348772 https://bugzilla.mozilla.org/show_bug.cgi?id=1348772
- _flux 2y ago
  I don't quite understand how it avoids the case for code that pushes lots of stuff to a vector, then shifts its all out, and then does this again—which, to me, doesn't seem like an edge-case at all. Do any languages automatically reduce vector size when elements are removed from it? If this is the first one, then arguably it would be a bit surprising behaviour.

by _flux 2y ago

csjh 2y ago

Decreasing capacity wouldn't affect the theoretical complexity of algorithms using it - same concept as increasing capacity during push still being amortized O(1)

_flux 2y ago
I don't think it works that way when a container can grow and shrink, because an algorithm can trigger those operations any number of times, not just O(log(n)) times.
- csjh 2y ago
  I'm not sure where you're getting O(logn) from here. If it couldn't work that way when a container can grow and shrink, then arrays wouldn't be able to have both amortized O(1) push and pop as they do in most relevant implementations. As long as the expensive O(n) resize operation happens at some frequency relative to the size of the container rather than every constant size difference (i.e. capacity doubles when length == capacity and halves when length == capacity/2) then it will amortize out to O(1). There's a proof available in section 2.1.2 of this textbook: https://opendatastructures.org/ods-java/2_1_ArrayStack_Fast_Stack_O.html https://opendatastructures.org/ods-java/2_1_ArrayStack_Fast_...

deleted 2y ago

[deleted]

lifthrasiir 2y ago

You have a good point. Unless JS exposes some API to directly control the capacity, we have to guess which use cases are more common and which use cases are fine to ignore. On the other hands though, JS's lack of capacity control means that developers are not conscious about the memory usage after all and JS engines have to do something about that anyway. Indeed, if you look at the actual bug [1], one commentator does mention exactly what I have said: > This is a great idea! Both shift() and pop() can treat the elements array as a dequeue. A "shrink capacity to 1/2 when usage is <1/3" would give us O(1) amortized performance for shift() and pop(), while avoid edge cases where we keep shrinking/growing for alternating add/remove ops around the shrink/grow boundary. [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1348772 https://bugzilla.mozilla.org/show_bug.cgi?id=1348772

_flux 2y ago
I don't quite understand how it avoids the case for code that pushes lots of stuff to a vector, then shifts its all out, and then does this again—which, to me, doesn't seem like an edge-case at all. Do any languages automatically reduce vector size when elements are removed from it? If this is the first one, then arguably it would be a bit surprising behaviour.