Actions
Bug #21449
closed
Set#divide is order dependent and not working correctly
Status:
Closed
Assignee:
-
Target version:
-
ruby -v:
ruby 3.5.0dev (2025-06-23T11:03:48Z master af6b98f7a2) +YJIT +MN +PRISM [arm64-darwin22]
Description
Set[0,1,2,3].divide{(_1 - _2).abs == 1}
#=> #<Set: {#<Set: {0, 1, 2, 3}>}>
Set[0,2,3,1].divide{(_1 - _2).abs == 1}
#=> #<Set: {#<Set: {0, 1, 2, 3}>}> (ruby 3.4)
#=> #<Set: {#<Set: {0, 1}>, #<Set: {2, 3, 1}>}> (ruby 3.5.0dev)
Result of Set#divide wrongly depends on set order.
Set.new(1000.times.to_a.shuffle).divide{(_1 - _2).abs == 1}.size
#=> 1 (ruby 3.4)
#=> 250±20 (ruby 3.5.0dev)
Updated by tompng (tomoya ishida) 3 days ago
Updated by tompng (tomoya ishida) 2 days ago
- Status changed from Open to Closed
Applied in changeset git|67346a7d94b101acc00c177b01ad0aabfef605a8.
[Bug #21449] Fix Set#divide{|a,b|} using Union-find structure (#13680)
- [Bug #21449] Fix Set#divide{|a,b|} using Union-find structure
Implements Union-find structure with path compression.
Since divide{|a,b|} calls the given block n**2 times in the worst case, there is no need to implement union-by-rank or union-by-size optimization.
- Avoid internal arrays from being modified from block passed to Set#divide
Internal arrays can be modified from yielded block through ObjectSpace.
Freeze readonly array, use ALLOCV_N instead of mutable array.
Actions
Like1
Like0Like0