Удаление измененного объекта из набора в нерабочем состоянии?

См. пример ниже

require "set"
s = [[1, 2], [3, 4]].to_set # s = {[1, 2], [3, 4]}
m = s.max_by {|a| a[0]} # m = [3, 4]
m[0] = 9 # m = [9, 4], s = {[1, 2], [9, 4]}
s.delete(m) # s = {[1, 2], [9, 4]} ?????

Это ведет себя иначе, чем массив. (Если мы удалим .to_set, мы получим s = [[1, 2]], что и ожидалось.) Это ошибка?


ruby set
person Ethan    schedule 28.04.2012    source источник

Ответы (1)


arrow_upward
7
arrow_downward

Да, это ошибка, или, по крайней мере, я бы назвал это ошибкой. Кто-то назвал бы это «деталью реализации, случайно просочившейся во внешний мир», но это всего лишь причудливая болтовня горожанина о баге.

Проблема имеет две основные причины:

  1. Вы изменяете элементы Сета без ведома Сета.
  2. Стандартный Ruby Set реализован как хэш.

В результате вы изменяете ключи внутреннего хэша без ведома хэша, и это сбивает с толку бедного хэша, который на самом деле не знает, какие у него есть ключи. Класс Hash имеет метод rehash:

перефразировать → hsh

Перестраивает хэш на основе текущих значений хэша для каждого ключа. Если значения ключевых объектов изменились с момента их вставки, этот метод переиндексирует hsh.

a = [ "a", "b" ]
c = [ "c", "d" ]
h = { a => 100, c => 300 }
h[a]       #=> 100
a[0] = "z"
h[a]       #=> nil
h.rehash   #=> {["z", "b"]=>100, ["c", "d"]=>300}
h[a]       #=> 100

Обратите внимание на интересное поведение в примере, включенном в документацию rehash. Хэши отслеживают вещи, используя значения k.hash для ключа k. Если у вас есть массив в качестве ключа, и вы меняете массив, вы также можете изменить значение hash массива; в результате хэш по-прежнему имеет этот массив в качестве ключа, но хэш не сможет найти этот массив в качестве ключа, потому что он будет искать в корзине новое значение hash, но массив будет в корзине для старое значение hash. Но если вы rehash хешируете, он вдруг снова сможет найти все свои ключи, и маразм уйдет. Аналогичные проблемы возникнут и с ключами, не являющимися массивами: вам просто нужно изменить ключ таким образом, чтобы его значение hash изменилось, а хеш, содержащий этот ключ, запутался и потерялся, пока вы его не rehash.

класс Set использует хеш внутри для хранения своих членов и члены используются как ключи хеша. Итак, если вы поменяете члена, Set запутается. Если бы у Сета был метод rehash, то вы могли бы обойти проблему, хлопнув Сета по голове rehash, чтобы придать ему какой-то смысл; увы, в Set такого метода нет. Тем не менее, вы можете самостоятельно исправить обезьяну в:

class Set
  def rehash
    @hash.rehash
  end
end

Затем вы можете изменить ключи, вызвать rehash в Set, и ваш delete (и различные другие методы, такие как member?) будут работать правильно.

person mu is too short    schedule 28.04.2012
comment
Считаете ли вы, что хэши были реализованы таким образом, потому что накладные расходы Ruby на отслеживание изменений ключей и выполнение rehash внутри были бы слишком велики? - person Cary Swoveland; 29.04.2020
comment
@CarySwoveland Я думаю, что простое отслеживание изменений в ключах было бы дорого, в конечном итоге вам потребовались бы обратные вызовы изменений для всего, не так ли? Так что да, вероятно, много расходов для необычного случая. - person mu is too short; 29.04.2020