From: ruby-core@... Date: 2018-11-03T18:42:14+00:00 Subject: [ruby-core:89700] [Ruby trunk Feature#15281] Speed up Set#intersect with size check. Issue #15281 has been updated by marcandre (Marc-Andre Lafortune). Assignee set to matz (Yukihiro Matsumoto) RGBD (Oleg Zubchenko) wrote: > > 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. Good point. Note that this documentation is 15 years old and predates Hash being ordered. I'd be enclined to say that Set should be officially ordered, even if "mathematically" speaking that doesn't make sense. I'm assigning this to Matz. ---------------------------------------- Feature #15281: Speed up Set#intersect with size check. https://bugs.ruby-lang.org/issues/15281#change-74743 * Author: RGBD (Oleg Zubchenko) * Status: Open * Priority: Normal * Assignee: matz (Yukihiro Matsumoto) * 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: