From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS4713 221.184.0.0/13 X-Spam-Status: No, score=-3.1 required=3.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, FORGED_GMAIL_RCVD,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from neon.ruby-lang.org (neon.ruby-lang.org [221.186.184.75]) by dcvr.yhbt.net (Postfix) with ESMTP id 19AE01F462 for ; Tue, 21 May 2019 13:09:57 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id 67FBA120914; Tue, 21 May 2019 22:09:50 +0900 (JST) Received: from o1678948x4.outbound-mail.sendgrid.net (o1678948x4.outbound-mail.sendgrid.net [167.89.48.4]) by neon.ruby-lang.org (Postfix) with ESMTPS id 8AE6B1208FC for ; Tue, 21 May 2019 22:09:48 +0900 (JST) Received: by filter0089p3mdw1.sendgrid.net with SMTP id filter0089p3mdw1-25607-5CE3F89C-3C 2019-05-21 13:09:49.013646716 +0000 UTC m=+484250.574615982 Received: from herokuapp.com (unknown [3.90.36.146]) by ismtpd0011p1iad2.sendgrid.net (SG) with ESMTP id 9KYrDuymRqWYfjGNI2arlA for ; Tue, 21 May 2019 13:09:48.901 +0000 (UTC) Date: Tue, 21 May 2019 13:09:48 +0000 (UTC) From: eregontp@gmail.com Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 68228 X-Redmine-Project: ruby-trunk X-Redmine-Issue-Id: 15281 X-Redmine-Issue-Author: RGBD X-Redmine-Issue-Assignee: knu X-Redmine-Sender: Eregon 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: =?us-ascii?Q?KippOI8ZHtTweq7XfQzW93937kJ4QNWwSBuHnaMEcr2tk41HEXukDgJNOFCxTp?= =?us-ascii?Q?DS7MNhDWfpb1kGKVxmX3XFY6BkIfU9KUy+vXGI5?= =?us-ascii?Q?u7l+0=2FiEKFdAToXh9Qem1B2ZU7PKCiqvD3b7h1O?= =?us-ascii?Q?WURC4u6PJyP7AA+XGLjQjIUclhTjdsAt59DdhTz?= =?us-ascii?Q?cErwC21+GMurNcfE8BZGgZEcvZotgR6S8bQ=3D=3D?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 92743 Subject: [ruby-core:92743] [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 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/