Issue #15281 has been updated by Eregon (Benoit Daloze).


I think making Set unordered would be a big breaking change, similar to making Hash unordered (as it was in 1.8).
Maybe people forgot, but I find it pretty bad to work with unordered Hashes,
e.g., every iteration method like `each` yields a confusing order changing on potentially every mutation.

I'm also fairly confident there is code out there relying on Set ordering.

This proposal doesn't propose to make Set unordered though, but it would introduce non-determinism in the order of elements returned by Set#&.
That seems not ideal.

Also, this trivial optimization can already be done at the application level if needed, and there the change of ordering is obvious and conscious:
```ruby
set1, set2 = ...
if set1.size < set2.size
  set1 & set2
else
  set2 & set1
end
```

So I don't think it's worth introducing non-determinism in Set for something that can be expressed so simply in application code, with the advantage of the ordering trade-off being clear if done in application code.

----------------------------------------
Feature #15281: Speed up Set#intersect with size check.
https://bugs.ruby-lang.org/issues/15281#change-77797

* 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: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>