Feature #6515: array.c: added method that verifies if an Array is part of another

• Status: Feedback
• Assignee: matz (Yukihiro Matsumoto)
• Target version: -

[lellisga (Li Ellis Galardo)]

This method is like the include? method but instead of receiving a value and check if the array has it, it receives an array an check if it's part of another one.

https://github.com/ruby/ruby/pull/127

[nobu (Nobuyoshi Nakada)]

• % Done changed from 100 to 0

Why attaching whole files?

[lellisga (Li Ellis Galardo)]

Sorry, I wasn;t sure what to upload. Please remove them.

nobu (Nobuyoshi Nakada) wrote:

Why attaching whole files?

[zzak (zzak _)]

• File feature_6515_array_part_of.patch feature_6515_array_part_of.patch added

I've added Li's patch from GH#127

[naruse (Yui NARUSE)]

• Status changed from Open to Assigned
• Assignee set to matz (Yukihiro Matsumoto)

[lellisga (Li Ellis Galardo)]

• File feature_6515_array_part_of_v2.patch feature_6515_array_part_of_v2.patch added

I'm adding a new patch that fixed a typo. I also did some refactor to the code.

[nobu (Nobuyoshi Nakada)]

=begin
I'm not in favor with this proposal, because of its name mainly.
'Array ((|X|)) is part of array ((|Y|))' sounds like 'all elements in ((|X|)) are
arranged in ((|Y|)) successively in the same order', to me.

If the order is not your concern, why it isn't a method of (({Set}))?

Also, (({Array#&})) isn't necessary here.
(ary1 - ary2).empty?
would work enough.
=end

[lellisga (Li Ellis Galardo)]

• File feature_6515_array_part_of_v3.patch feature_6515_array_part_of_v3.patch added

@nobu (Nobuyoshi Nakada) you are right. I'll change the method to (arry1 - arry2).empty?. About the method functionally I thought of it like the subset method from Set. That's why it doesn't care about the order.

[nobu (Nobuyoshi Nakada)]

• Status changed from Assigned to Feedback

=begin
Then why don't you use (({Set#subset?})) method?

What's the rationale that (({Array})) also should have similar method?
And why different name?
=end

[lellisga (Li Ellis Galardo)]

Sorry but i'm not sure what you are asking. In other words you really think it's easier to do this:

a = [1,2,3,4,5,6,7].to_set
=> #<Set: {1, 2, 3, 4, 5, 6, 7}>
b = [1,2,3].to_set
=> #<Set: {1, 2, 3}>
b.subset? a
=> true

If you answer is yes, then we are doing this wrong because subset? or part_of method should be in a parent class (maybe Enumerable class ) in order for it to work for subset, array, hash and any data structure that inherit from it Enumerable.

There's a difference between subset and arrays isn't it? they should have different methods, eventually some of them will work for subset just as they work for arrays.

[Eregon (Benoit Daloze)]

lellisga (Li Ellis Galardo) wrote:

a = [1,2,3,4,5,6,7].to_set
=> #<Set: {1, 2, 3, 4, 5, 6, 7}>
b = [1,2,3].to_set
=> #<Set: {1, 2, 3}>
b.subset? a
=> true

If you answer is yes, then we are doing this wrong because subset? or part_of method should be in a parent class (maybe Enumerable class ) in order for it to work for subset, array, hash and any data structure that inherit from it Enumerable.

Taking you example of a the first set and b the maybe-subset:
Well, probably because #subset? is O(m) (m is the size of b), and doing it naively on Array/Enumerable is O(m*n) (n being the size of a). Using (b-a).empty? is actually O(n+m) because it creates a hash (think set in this case) underneath and iterates b. Note Array#- mentions the Set library, because it's likely what you want if you need this kind of operations. Of course you might need both Array and Set operations, in which case you may:

• transform them to set when needed: which is O(n+m + m) so O(n+m).

• use (a-b).empty? which I believe is clear and concise (although a comment might help for other readers) but creates the diff Array for nothing. You might want something like:

  as = a.to_set
  b.all? { |e| as.include?(e) }

Which does not allocate an intermediary Array, and is O(n+m) as well.

Often, when you want this kind of behavior, you don't need Array-specific operations, which is why using a Set directly is better (and usually more efficient).

[Eregon (Benoit Daloze)]

Eregon (Benoit Daloze) wrote:

as = a.to_set
b.all? { |e| as.include?(e) }

Which does not allocate an intermediary Array, and is O(n+m) as well.

But does allocate the Set for it of course (so likely not better).

[mame (Yusuke Endoh)]

• Target version changed from 2.0.0 to 2.6

[naruse (Yui NARUSE)]

• Target version deleted (2.6)