5 ms·

Interestingly, you can use scheduling to make a non-amortized dynamic array. Your probably know this, but for other commenters who do not— Keep two arrays, of

Interestingly, you can use scheduling to make a non-amortized dynamic array. Your probably know this, but for other commenters who do not— Keep two arrays, of size n and 2n. Initially the first has capacity c = n/2 and the second has capacity 0. Reads go to the first array. When you append, append one element to the first array, and copy two elements to the second array. By the time the first array is full, it has been entirely copied to the second array—so discard the first array, move the second array to be first, and allocate a new "next" array. The same trick can be applied to many amortized data structures (but it gets very complicated when you have many operations).

vladf 5y ago
One thing I’ve always been curious about, can you guarantee worst case linear memory use with this setup while supporting pop() at the same time?
- mjevans 5y ago
  It depends on how strictly the structure of each array is defined, the answer can be yes but I don't know what effect this has on modern superscaler CPUs. The source array might be considered to have even offsets (0, 2, 4, etc, index left shift 1 bit) relative to the double-sized array. Addition operations past the halfway value of the smaller array have a relation to values in the second by (Index << 1) % n + 1 ; that is they pair with the values from the start of the smaller array. When a removal operation, like pop(), selects a victim in the source array the corresponding operations must also apply in sync to the values in the larger array.
- Dylan16807 5y ago
  Easily! You can just make pop do the opposite of push. For example, if push copies two elements to the bigger array, make pop copy two elements to the smaller array.
  - vladf 5y ago
    I challenge you to try to implement it this way and test that (1) an arbitrary sequence of push/pop is valid and (2) doesn’t use more than linear space.
    - Dylan16807 5y ago
      It's pretty easy to make sure an arbitrary sequence is valid if you make push and pop be almost exact opposites of each other. Let me walk through a simple version based on the description above, ignoring that it's rather inefficient: Start with an array of size 64, with 32 elements. Our first action is either a push or a pop. I'll split those up. * * * If the first action is a push: From here, call the existing array Small and make a new 128 element array called Big. For the first push, store it in Small[32]. Then copy Small[0] and Small[1] to Big[0] and Big[1]. For the second push, store it in Small[33]. Then copy Small[2] and Small[3] to Big[2] and Big[3]. Then for a pop, just remove the element in Small[33]. Then pushing again, store it in Small[33]. Then copy Small[2] and Small[3] to Big[2] and Big[3]. Notice how this is exactly the same as the previous push. And if you undid two pushes, then did two more pushes, both of them would be the same as they were before. So, analyzing this, once we push once, any arbitrary sequence of pushes and pops is going to do one of the following: * Pushes is always more than pops, but the difference is always under 32. This bounces around forever, undoing and redoing pushes. This is valid, and always uses the same amount of space for 33-63 elements, so that's clearly linear too. * Eventually pops catches up to pushes. This means we're back to 32 elements, right where we started. Throw out the 'Big' array too. Going back where we started is valid and uses linear space. If the next action is a push, go to the start of the push instructions. If it's a pop, go to the start of the pop instructions. * Eventually pushes minus pops reaches 32. So now our Small array is completely full, and our Big array is half full, and they contain exactly the same data. Throw out the Small array. Now we're back where we started, except with twice as many elements in an array twice as big. Use all the same logic as before, but with 2x numbers. This is valid and uses linear space. * * * If the first action is a pop: From here, call the existing array Big and make a new 32 element array called Small. For the first pop, copy Big[0] to Small[0]. Then delete and return Big[31]. For the second pop, copy Big[1] to Small[1]. Then delete and return Big[30]. If we get a push, put it in Big[30]. If there's another pop, copy Big[1] to Small[1]. Then delete and return Big[30]. Notice how this is exactly the same as the previous pop. And if you undid two pops, then did two more pops, both of them would be the same as they were before. So, analyzing this, once we pop once, any arbitrary sequence of pops and pushes is going to do one of the following: * Pops are always more than pushes, but the difference is always under 16. This bounces around forever, undoing and redoing pops. This is valid, and always uses the same amount of space for 17-31 elements, so that's clearly linear too. * Eventually pushes catch up to pops. This means we're back to 32 elements, right where we started. Throw out the 'Small' array too. Going back where we started is valid and uses linear space. If the next action is a push, go to the start of the push instructions. If it's a pop, go to the start of the pop instructions. * Eventually pops minus pushes reaches 16. So now our Small array is half full, and our Big array is one quarter full, and they contain exactly the same data. Throw out the Big array. Now we're back where we started, except with half as many elements in an array half as big. Use all the same logic as before, but with numbers cut by 2x. This is valid and uses linear space. There. Now, there are easy optimizations that could be done on top of that to cut the memory use in half, or combine pushing and popping into the same logic, or all sorts of other improvements. And you want to have a special case if the size gets too small to stop shrinking. But that should be a perfectly good basic explanation of an algorithm that's very straightforward and has no wiggle room for anything to go wrong.
deleted 5y ago
[deleted]
vecter 5y ago
IIUC, this is assuming that memory allocation is O(1)?
- hawk_ 5y ago
  yes it's rare to not assume that.
  - mhh__ 5y ago
    The coefficient can and will bite your head off, however.
pierrebai 5y ago
This is dangerous, but if well documented and understood it might be okay. Some data might contain unique things (for argument's sake, say a std::unique_ptr). It can get tricky since you need to know the implementation details of everything that gets inserted and it's ownership behavior, since elements can be kept at two places. (A copy in array n and one in 2n.) Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats. As for the original interview question, there are systems where an occasional longer pause is not OK. Personally, I think that sticking to your gun must have come across as being stubborn and unyielding and maybe not ready to admit errors. As an interviewer, and for having worked with people who always think they're right and inflexible, it would have been a red flag.
- rav 5y ago
  > Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats. > As for the original interview question, there are systems where an occasional longer pause is not OK. As you say, it's a tradeoff between worst-case operation cost and average operation cost: If you allow any worst-case operation cost, you can get really efficient on average. If you want really efficient worst-case operation cost, you can't get it down to exactly the average operation cost you could've otherwise gotten. I wouldn't be surprised if this tradeoff is inherent to many de-amortization problems. But since the difference between the amortized and de-amortized solution is usually only a constant factor (as it is in this case), you have to be very specific about the model of computation if you want to prove anything mathematically.
  - remram 5y ago
    To be clear, there is no tradeoff in the number of operations. You are doing the exact same number on average (or total or amortized), while improving the worst-case. You do lose the ability to do a no-copy realloc() though, and increase the average memory use (not peak).
- scottlamb 5y ago
steelframe 5y ago
The primary thing I like about this approach vs. stopping to copy the entire array on expanding its capacity is cache hotness.
- mhh__ 5y ago
  Evidence?

vladf 5y ago

One thing I’ve always been curious about, can you guarantee worst case linear memory use with this setup while supporting pop() at the same time?

mjevans 5y ago
It depends on how strictly the structure of each array is defined, the answer can be yes but I don't know what effect this has on modern superscaler CPUs. The source array might be considered to have even offsets (0, 2, 4, etc, index left shift 1 bit) relative to the double-sized array. Addition operations past the halfway value of the smaller array have a relation to values in the second by (Index << 1) % n + 1 ; that is they pair with the values from the start of the smaller array. When a removal operation, like pop(), selects a victim in the source array the corresponding operations must also apply in sync to the values in the larger array.
Dylan16807 5y ago
Easily! You can just make pop do the opposite of push. For example, if push copies two elements to the bigger array, make pop copy two elements to the smaller array.
- vladf 5y ago
  I challenge you to try to implement it this way and test that (1) an arbitrary sequence of push/pop is valid and (2) doesn’t use more than linear space.
  - Dylan16807 5y ago
    It's pretty easy to make sure an arbitrary sequence is valid if you make push and pop be almost exact opposites of each other. Let me walk through a simple version based on the description above, ignoring that it's rather inefficient: Start with an array of size 64, with 32 elements. Our first action is either a push or a pop. I'll split those up. * * * If the first action is a push: From here, call the existing array Small and make a new 128 element array called Big. For the first push, store it in Small[32]. Then copy Small[0] and Small[1] to Big[0] and Big[1]. For the second push, store it in Small[33]. Then copy Small[2] and Small[3] to Big[2] and Big[3]. Then for a pop, just remove the element in Small[33]. Then pushing again, store it in Small[33]. Then copy Small[2] and Small[3] to Big[2] and Big[3]. Notice how this is exactly the same as the previous push. And if you undid two pushes, then did two more pushes, both of them would be the same as they were before. So, analyzing this, once we push once, any arbitrary sequence of pushes and pops is going to do one of the following: * Pushes is always more than pops, but the difference is always under 32. This bounces around forever, undoing and redoing pushes. This is valid, and always uses the same amount of space for 33-63 elements, so that's clearly linear too. * Eventually pops catches up to pushes. This means we're back to 32 elements, right where we started. Throw out the 'Big' array too. Going back where we started is valid and uses linear space. If the next action is a push, go to the start of the push instructions. If it's a pop, go to the start of the pop instructions. * Eventually pushes minus pops reaches 32. So now our Small array is completely full, and our Big array is half full, and they contain exactly the same data. Throw out the Small array. Now we're back where we started, except with twice as many elements in an array twice as big. Use all the same logic as before, but with 2x numbers. This is valid and uses linear space. * * * If the first action is a pop: From here, call the existing array Big and make a new 32 element array called Small. For the first pop, copy Big[0] to Small[0]. Then delete and return Big[31]. For the second pop, copy Big[1] to Small[1]. Then delete and return Big[30]. If we get a push, put it in Big[30]. If there's another pop, copy Big[1] to Small[1]. Then delete and return Big[30]. Notice how this is exactly the same as the previous pop. And if you undid two pops, then did two more pops, both of them would be the same as they were before. So, analyzing this, once we pop once, any arbitrary sequence of pops and pushes is going to do one of the following: * Pops are always more than pushes, but the difference is always under 16. This bounces around forever, undoing and redoing pops. This is valid, and always uses the same amount of space for 17-31 elements, so that's clearly linear too. * Eventually pushes catch up to pops. This means we're back to 32 elements, right where we started. Throw out the 'Small' array too. Going back where we started is valid and uses linear space. If the next action is a push, go to the start of the push instructions. If it's a pop, go to the start of the pop instructions. * Eventually pops minus pushes reaches 16. So now our Small array is half full, and our Big array is one quarter full, and they contain exactly the same data. Throw out the Big array. Now we're back where we started, except with half as many elements in an array half as big. Use all the same logic as before, but with numbers cut by 2x. This is valid and uses linear space. There. Now, there are easy optimizations that could be done on top of that to cut the memory use in half, or combine pushing and popping into the same logic, or all sorts of other improvements. And you want to have a special case if the size gets too small to stop shrinking. But that should be a perfectly good basic explanation of an algorithm that's very straightforward and has no wiggle room for anything to go wrong.

deleted 5y ago

[deleted]

vecter 5y ago

IIUC, this is assuming that memory allocation is O(1)?

hawk_ 5y ago
yes it's rare to not assume that.
- mhh__ 5y ago
  The coefficient can and will bite your head off, however.

pierrebai 5y ago

This is dangerous, but if well documented and understood it might be okay. Some data might contain unique things (for argument's sake, say a std::unique_ptr). It can get tricky since you need to know the implementation details of everything that gets inserted and it's ownership behavior, since elements can be kept at two places. (A copy in array n and one in 2n.) Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats. As for the original interview question, there are systems where an occasional longer pause is not OK. Personally, I think that sticking to your gun must have come across as being stubborn and unyielding and maybe not ready to admit errors. As an interviewer, and for having worked with people who always think they're right and inflexible, it would have been a red flag.

rav 5y ago
> Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats. > As for the original interview question, there are systems where an occasional longer pause is not OK. As you say, it's a tradeoff between worst-case operation cost and average operation cost: If you allow any worst-case operation cost, you can get really efficient on average. If you want really efficient worst-case operation cost, you can't get it down to exactly the average operation cost you could've otherwise gotten. I wouldn't be surprised if this tradeoff is inherent to many de-amortization problems. But since the difference between the amortized and de-amortized solution is usually only a constant factor (as it is in this case), you have to be very specific about the model of computation if you want to prove anything mathematically.
- remram 5y ago
  To be clear, there is no tradeoff in the number of operations. You are doing the exact same number on average (or total or amortized), while improving the worst-case. You do lose the ability to do a no-copy realloc() though, and increase the average memory use (not peak).
scottlamb 5y ago

steelframe 5y ago

The primary thing I like about this approach vs. stopping to copy the entire array on expanding its capacity is cache hotness.

mhh__ 5y ago
Evidence?