Issue #17483 has been updated by mame (Yusuke Endoh).

Status changed from Open to Rejected

In short, it is unavoidable.

Currently, an array is internally represented as consecutive memory area. Adding new elements into the middle of an array requires reallocation of the array, which takes O(n). Therefore, calling Array#insert n times takes O(n^2 ). Theoretically, by replacing the internal data structure with a tree or somthing, the order can be improved to O(n log n), but it will make other (more commonly used) operations slow.

----------------------------------------
Bug #17483: Array#insert is pathologically slow
https://bugs.ruby-lang.org/issues/17483#change-89589

* Author: djberg96 (Daniel Berger)
* Status: Rejected
* Priority: Normal
* ruby -v: ruby 2.6.6p146 (2020-03-31 revision 67876) [x86_64-darwin19]
* Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN
----------------------------------------
I ran some generic Array method benchmarks:

https://github.com/djberg96/berger_spec/blob/ruby23/bench/core/bench_array.rb (comment out nitems first)

https://github.com/djberg96/berger_spec/blob/ruby23/bench/core/Array/bench_insert.rb

What I noticed is that all of these complete in a fraction of a second, except Array#insert, which takes about 6-8 seconds on my Mac desktop.

Is this unavoidable?



-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>