[ruby-core:99550] [Ruby master Feature#15281] Speed up Set#intersect with size check.
From:
marcandre-ruby-core@...
Date:
2020-08-11 02:43:32 UTC
List:
ruby-core #99550
Issue #15281 has been updated by marcandre (Marc-Andre Lafortune). Apparently the linked PR has been merged last december 31st. I note there's no NEWS entry. ---------------------------------------- Feature #15281: Speed up Set#intersect with size check. https://bugs.ruby-lang.org/issues/15281#change-87012 * Author: RGBD (Oleg Zubchenko) * Status: Assigned * Priority: Normal * Assignee: knu (Akinori MUSHA) ---------------------------------------- Current implementation computes set intersection s1 & s2 in O(s2.size) time. It can be reduced to O([s1.size, s2.size].min) time. Additional speedup comes from using #each instead of #do_with_enum. See files attached for benchmarks. [Pull Request](https://github.com/ruby/ruby/pull/2003) P.S. using benchmark-ips gem ---Files-------------------------------- intersect.rb (1.91 KB) intersect_standalone.rb (671 Bytes) benchmark_results.txt (3.68 KB) -- https://bugs.ruby-lang.org/ Unsubscribe: <mailto:[email protected]?subject=unsubscribe> <http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>