Timeline for Reasoning behind specifically doubling the array size upon reallocation
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2022 at 5:07 | comment | added | Jörg W Mittag |
Doubling is actually not so much related to performance but to simplicity. It is mostly used in textbooks. Real-world implementations use different factors, e.g. Microsoft's implementation of the C++ STL uses 1.5x, as does .NET. For dictionaries, .NET uses 1.5x rounded up to the next prime number. Oracle's implementation of ArrayList[T] uses 1.25x. YARV uses 1.25x. Python uses 1.125x + 3 for smaller x and 1.125x + 6 for large x. 1.5x has some performance advantages over 2x. For a specific definition of "optimal" and an infinitely large array, the optimal value is actually the golden ratio.
|
|
| Mar 10, 2022 at 11:12 | answer | added | Rinkesh P | timeline score: 1 | |
| Mar 10, 2022 at 7:23 | history | edited | xyf | CC BY-SA 4.0 |
added 320 characters in body
|
| Mar 8, 2022 at 6:35 | comment | added | Rinkesh P | stackoverflow.com/questions/61377948/… check this post. | |
| Mar 8, 2022 at 6:09 | comment | added | xyf | yeah increase by a random size as opposed to multiplying by a factor... | |
| Mar 8, 2022 at 5:30 | comment | added | Rinkesh P | What do you mean by random, do you mean that everytime the resizing happens, you increase the size by a random value or you mean any other choice other than doubling it everytime? | |
| Mar 8, 2022 at 5:05 | history | asked | xyf | CC BY-SA 4.0 |