On 11/5/14 10:48 PM, Dmitriy wrote:
Hello, I'm in the middle of learning D. I can't find any definitive information about what is the complexity of operator ~= when used for adding an element to an array. Is it amortized O(1) or is it implementation defined? (I hope it at worst O(n) though I haven't seen any information about that either).
It's amortized O(1).
Also documentation to std.array.Appender says that "it is more efficient" to use Appender "when appending many elements". Does it imply that Appender.put has amortized O(1)?
As Jonathan said, it's because array append needs to look up information in the GC, which can be costly (we have mechanisms to mitigate this somewhat, but it can't be inlined). The Appender has all the information it needs handy, and can be inlined. The disadvantage is that the Appender may have higher up-front costs, and does not have some of the same properties as a builtin array.
You may find this article helpful: http://dlang.org/d-array-article.html -Steve
