[ruby-core:108218] [Ruby master Bug#18692] Set += is O(n^2)
From:
"jablin (Johannes Abt)" <noreply@...>
Date:
2022-04-13 08:42:44 UTC
List:
ruby-core #108218
Issue #18692 has been reported by jablin (Johannes Abt).
----------------------------------------
Bug #18692: Set += is O(n^2)
https://bugs.ruby-lang.org/issues/18692
* Author: jablin (Johannes Abt)
* Status: Open
* 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
`
Tree 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
`
Tree 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>