Project

General

Profile

Actions

Feature #15281

open

Speed up Set#intersect with size check.

Added by RGBD (Oleg Zubchenko) about 3 years ago. Updated over 1 year ago.

Status:
Assigned
Priority:
Normal
Target version:
-
[ruby-core:89696]

Description

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

P.S. using benchmark-ips gem


Files

intersect.rb (1.91 KB) intersect.rb RGBD (Oleg Zubchenko), 11/03/2018 12:57 PM
intersect_standalone.rb (671 Bytes) intersect_standalone.rb RGBD (Oleg Zubchenko), 11/03/2018 12:58 PM
benchmark_results.txt (3.68 KB) benchmark_results.txt RGBD (Oleg Zubchenko), 11/03/2018 01:19 PM
Actions

Also available in: Atom PDF