From: eregontp@...
Date: 2019-05-21T13:09:48+00:00
Subject: [ruby-core:92743] [Ruby trunk Feature#15281] Speed up Set#intersect	with size check.

Issue #15281 has been updated by Eregon (Benoit Daloze).


Just a note, for compatibility there is often a gap between what the documentation states and what Ruby programs assume.
So even though the documentation says it's unordered, I would guess there are programs relying on Sets being ordered since Ruby 1.9.

Maybe not so many programs, but I think we should evaluate before changing.

----------------------------------------
Feature #15281: Speed up Set#intersect with size check.
https://bugs.ruby-lang.org/issues/15281#change-78105

* Author: RGBD (Oleg Zubchenko)
* Status: Assigned
* Priority: Normal
* Assignee: knu (Akinori MUSHA)
* Target version: 
----------------------------------------
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:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>