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=-4.1 required=3.0 tests=BAYES_00,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,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 2EB321F461 for ; Sat, 11 May 2019 13:40:43 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id 13A67120946; Sat, 11 May 2019 22:40:37 +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 309DF120907 for ; Sat, 11 May 2019 22:40:34 +0900 (JST) Received: by filter0182p3mdw1.sendgrid.net with SMTP id filter0182p3mdw1-23021-5CD6D0D3-2 2019-05-11 13:40:35.033922135 +0000 UTC m=+157945.593583925 Received: from herokuapp.com (unknown [3.93.58.81]) by ismtpd0004p1iad1.sendgrid.net (SG) with ESMTP id d2lhNcMVTe6NT6VjBECmxw for ; Sat, 11 May 2019 13:40:35.001 +0000 (UTC) Date: Sat, 11 May 2019 13:40:35 +0000 (UTC) From: nobu@ruby-lang.org Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 68105 X-Redmine-Project: ruby-trunk X-Redmine-Issue-Id: 15281 X-Redmine-Issue-Author: RGBD X-Redmine-Issue-Assignee: knu X-Redmine-Sender: nobu 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?q8Dly+pU2+3ektTtZVXgZtbJPXwqo7p86jCsvYTW4Bz50FNqHZv6DzYK=2FfMGUc?= =?us-ascii?Q?WuigutEnDw+6Uty81qfQ55IJNobI7QkZ8dA54wU?= =?us-ascii?Q?h9pnkwc5+Yd8NYV0Owg9XUp0SQm1SsxjPFOvnso?= =?us-ascii?Q?uS8zsYMAGntM4NNF2RRDt3zSvCGHFRV3K5C4OaL?= =?us-ascii?Q?vuoIN5fRNBtcMTi0XWJ6AW5l9Fn=2FhTQPNRg=3D=3D?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 92622 Subject: [ruby-core:92622] [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 nobu (Nobuyoshi Nakada). Assignee changed from matz (Yukihiro Matsumoto) to knu (Akinori MUSHA) The author of set.rb is knu. ---------------------------------------- Feature #15281: Speed up Set#intersect with size check. https://bugs.ruby-lang.org/issues/15281#change-77982 * Author: RGBD (Oleg Zubchenko) * Status: Open * 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/