Issue #15281 has been updated by knu (Akinori MUSHA).


It is clearly stated that Set is an unordered collection and it doesn't even guarantee any determinacy about the order of elements, and as you know, it's just it happened to become ordered and deterministic when the underlying data structure (Hash) got an order.

That being said, I can understand the need for an ordered set if there are already some users using Set as such.  We could probably introduce OrderedSet for easier migration before making this "breaking" change (and maybe some others to follow) to Set, I guess?

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

* 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>