[ruby-core:108219] [Ruby master Bug#18692] Set += is O(n^2)
From:
"Eregon (Benoit Daloze)" <noreply@...>
Date:
2022-04-13 09:29:47 UTC
List:
ruby-core #108219
Issue #18692 has been updated by Eregon (Benoit Daloze).
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 <<.
----------------------------------------
Bug #18692: Set += is O(n^2)
https://bugs.ruby-lang.org/issues/18692#change-97205
* Author: jablin (Johannes Abt)
* Status: Rejected
* Priority: Normal
* ruby -v: ruby 2.6.5p114 (2019-10-01 revision 67812) [x86_64-linux]
* Backport: 2.6: UNKNOWN, 2.7: UNKNOWN, 3.0: UNKNOWN, 3.1: UNKNOWN
----------------------------------------
$ 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
--
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>