From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS4713 221.184.0.0/13 X-Spam-Status: No, score=-3.8 required=3.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.1 Received: from neon.ruby-lang.org (neon.ruby-lang.org [221.186.184.75]) by dcvr.yhbt.net (Postfix) with ESMTP id 97D3B1F453 for ; Sat, 3 Nov 2018 17:10:27 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id C753F121555; Sun, 4 Nov 2018 02:10:25 +0900 (JST) Received: from o1678916x28.outbound-mail.sendgrid.net (o1678916x28.outbound-mail.sendgrid.net [167.89.16.28]) by neon.ruby-lang.org (Postfix) with ESMTPS id 4B1D712105B for ; Sun, 4 Nov 2018 02:10:24 +0900 (JST) Received: by filter0113p3las1.sendgrid.net with SMTP id filter0113p3las1-31994-5BDDD67D-8 2018-11-03 17:10:21.63227721 +0000 UTC m=+239587.840793473 Received: from herokuapp.com (ec2-54-205-117-243.compute-1.amazonaws.com [54.205.117.243]) by ismtpd0002p1iad1.sendgrid.net (SG) with ESMTP id y9SGWDtSRMGTOZzmNiegAQ for ; Sat, 03 Nov 2018 17:10:21.512 +0000 (UTC) Date: Sat, 03 Nov 2018 17:10:21 +0000 (UTC) From: RedGreenBlueDiamond@gmail.com To: ruby-core@ruby-lang.org Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 65084 X-Redmine-Project: ruby-trunk X-Redmine-Issue-Id: 15281 X-Redmine-Issue-Author: RGBD X-Redmine-Sender: RGBD X-Mailer: Redmine X-Redmine-Host: bugs.ruby-lang.org X-Redmine-Site: Ruby Issue Tracking System X-Auto-Response-Suppress: All Auto-Submitted: auto-generated X-SG-EID: ync6xU2WACa70kv/Ymy4QrNMhiuLXJG8OTL2vJD1yS6ZyylVn9Wp/6y+GeHee5xsZ1oNoctq6C5FjJ qSIC25wwFn2NYzhwbh2bdFJoHP2P+1viumg9ITl51rr6s59Z0dzVdpjbXwv4JlmDMkqq9Ma0yXLUAG qHGEx0JzzPyUizQl1/89Sn88fy2Y+QlqorEOAO48sg3f/LPMFPaCDGUMVw== X-ML-Name: ruby-core X-Mail-Count: 89699 Subject: [ruby-core:89699] [Ruby trunk Feature#15281] Speed up Set#intersect with size check. X-BeenThere: ruby-core@ruby-lang.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Ruby developers List-Id: Ruby developers List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ruby-core-bounces@ruby-lang.org Sender: "ruby-core" 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/