* [ruby-core:99550] [Ruby master Feature#15281] Speed up Set#intersect with size check.
[not found] <redmine.issue-15281.20181103130832.16963@ruby-lang.org>
@ 2020-08-11 2:43 ` marcandre-ruby-core
0 siblings, 0 replies; only message in thread
From: marcandre-ruby-core @ 2020-08-11 2:43 UTC (permalink / raw)
To: ruby-core
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/
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2020-08-11 2:43 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <redmine.issue-15281.20181103130832.16963@ruby-lang.org>
2020-08-11 2:43 ` [ruby-core:99550] [Ruby master Feature#15281] Speed up Set#intersect with size check marcandre-ruby-core
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).