Actions
Bug #18692
closed
Set += is O(n^2)
Status:
Rejected
Assignee:
-
Target version:
-
ruby -v:
ruby 2.6.5p114 (2019-10-01 revision 67812) [x86_64-linux]
Description
$ time ruby26 --disable=gems -r set -e 's = Set.new(); 1.upto(10_000).each { |n| s += [n] }'
real 0m1.346s
user 0m1.290s
sys 0m0.055s
Three times the input size:
$ time ruby26 --disable=gems -r set -e 's = Set.new(); 1.upto(30_000).each { |n| s += [n] }'
real 0m13.099s
user 0m12.443s
sys 0m0.642s
Three times the input size is 9 to 10 times the runtime!
For comparsion, using the << operator instead of +=:
$ time ruby26 --disable=gems -r set -e 's = Set.new(); 1.upto(5_000_000).each { |n| s << n }'
real 0m1.472s
user 0m1.290s
sys 0m0.180s
Updated by
Updated by Eregon (Benoit Daloze) about 3 years ago
- Status changed from Open to Rejected
It's fully expected, a += b is just a = a + b and so it's N Set instances/copies created vs 1 with <<.
Actions
Like0
Like0Like0