From: RedGreenBlueDiamond@... Date: 2018-11-03T17:10:21+00:00 Subject: [ruby-core:89699] [Ruby trunk Feature#15281] Speed up Set#intersect with size check. Issue #15281 has been updated by RGBD (Oleg Zubchenko). marcandre (Marc-Andre Lafortune) wrote: > Thanks for the patch. > > Sadly, I don't think we can do that as `Set`s are ordered. That optimization would change the order of the resulting `Set` in some cases. Where in the documentation can I read that? [this](https://ruby-doc.org/stdlib-2.5.3/libdoc/set/rdoc/Set.html#method-i-to_a) says order is unspecified. Top of the page states: > Set implements a collection of unordered values with no duplicates. This is a hybrid of Array's intuitive inter-operation facilities and Hash's fast lookup. ---------------------------------------- Feature #15281: Speed up Set#intersect with size check. https://bugs.ruby-lang.org/issues/15281#change-74742 * Author: RGBD (Oleg Zubchenko) * Status: Open * Priority: Normal * Assignee: * 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: