Что метод Ruby `uniq` использует для проверки равенства?

Question

Я заинтересован в реализации пользовательского метода равенства для использования в массиве объектов в Ruby.Вот упрощенный пример:

class Foo

  attr_accessor :a, :b

  def initialize(a, b)
    @a = a
    @b = b
  end 

  def ==(other)
    puts 'doing comparison'
    @a == @a && @b == @b
  end

  def to_s
    "#{@a}: #{@b}"  
  end

end 

a = [
  Foo.new(1, 1),
  Foo.new(1, 2),
  Foo.new(2, 1),
  Foo.new(2, 2),
  Foo.new(2, 2)
]
a.uniq

Я ожидал, что метод uniq вызовет Foo#== и удалит последний экземпляр Foo.Вместо этого я не вижу строки отладки «выполнение сравнения», и массив остается той же длины.

Примечания:

• Я использую ruby ​​2.2.2
• Я пытался определить метод как ===
• Я сделал это длинным ружьем с a.uniq{|x| [x.a, x.b]}, но мне не нравится это решение, оно заставляет код выглядеть довольно загроможденным.

Answer 1

Вы можете найти ответ в документации Array#uniq (по какой-то причине он не упоминается в документации Enumerable#uniq):

Он сравнивает значения, используя их hash и eql? методы для эффективности.

Контракты hash и eql? заключаются в следующем:

• hash возвращает Integer, что должно быть одинаковым для объектов, которые считаются равными, но не обязательно должны быть разными для объектов, которые не равны.Это означает, что разные хэши означают, что объекты определенно не равны, но тот же хеш ничего вам не говорит.В идеале hash также должен быть устойчивым к случайным и преднамеренным столкновениям.
• eql? - это равенство значений, обычно более строгое, чем ==, но менее строгое, чем equal?, что более или менее идентично: equal? должен возвращать true только если вы сравниваете объект с самим собой.

uniq? использует тот же трюк, который используется в хэш-таблицах, хэш-наборах и т. д. для ускорения поиска:

1. Сравните хэши.Обычно вычисление хэша должно быть быстрым.
2. Если хэши идентичны, то, и только потом, перепроверьте, используя eql?.

Answer 2

Он сравнивает значения, используя их хэш и EQL?методы повышения эффективности.

https://ruby -doc.org / core-2.5.0 / Array.html # method-i-uniq-3F

Поэтому вы должны переопределить eql? (, то есть ==) и hash

ОБНОВЛЕНИЕ:

Я не могу полностью объяснить, почему это так, но переопределяю hash и == не работает.Я полагаю, это вызвано тем, что uniq реализовано в C:

From: array.c (метод C): Владелец: Array Видимость: public Количество строк: 20

static VALUE
rb_ary_uniq(VALUE ary)
{
    VALUE hash, uniq;

    if (RARRAY_LEN(ary) <= 1)
        return rb_ary_dup(ary);
    if (rb_block_given_p()) {
        hash = ary_make_hash_by(ary);
        uniq = rb_hash_values(hash);
    }
    else {
        hash = ary_make_hash(ary);
        uniq = rb_hash_values(hash);
    }
    RBASIC_SET_CLASS(uniq, rb_obj_class(ary));
    ary_recycle_hash(hash);

    return uniq;
}

Вы можете обойти это, используя блочную версию uniq:

> [Foo.new(1,2), Foo.new(1,2), Foo.new(2,3)].uniq{|f| [f.a, f.b]}
=> [#<Foo:0x0000562e48937cc8 @a=1, @b=2>, #<Foo:0x0000562e48937c78 @a=2, @b=3>]

или использовать Struct вместо:

F = Struct.new(:a, :b)
[F.new(1,2), F.new(1,2), F.new(2,3)].uniq
# => [#<struct F a=1, b=2>, #<struct F a=2, b=3>]

UPDATE2:

Фактически в терминахпереопределение это не то же самое, если вы переопределите == или eql?.Когда я переопределил eql? Он работал как задумано:

class Foo
  attr_accessor :a, :b

  def initialize(a, b)
    @a = a
    @b = b
  end 

  def eql?(other)
    (@a == other.a && @b == other.b)
  end

  def hash
    [a, b].hash
  end

  def to_s
    "#{@a}: #{@b}"  
  end

end 

a = [
  Foo.new(1, 1),
  Foo.new(1, 2),
  Foo.new(2, 1),
  Foo.new(2, 2),
  Foo.new(2, 2)
]
a.uniq
#=> [#<Foo:0x0000562e483bff70 @a=1, @b=1>,
#<Foo:0x0000562e483bff48 @a=1, @b=2>,
#<Foo:0x0000562e483bff20 @a=2, @b=1>,
#<Foo:0x0000562e483bfef8 @a=2, @b=2>]