Почему мой метод фильтрации не удаляет некоторые элементы, которые следует удалить?

Question

Я пытаюсь создать метод под названием filer_out! который принимает массив и pro c и возвращает тот же массив, но с каждым элементом, который возвращает true при запуске через pro c, с оговоркой, что мы не можем использовать Array # reject!

Я написал это:

def filter_out!(array, &prc)
    array.each { |el| array.delete(el) if prc.call(el)}
end

arr_2 = [1, 7, 3, 5 ]
filter_out!(arr_2) { |x| x.odd? }
p arr_2

но когда я запускаю код, выводится следующее:

[7, 5]

, хотя ответ должен быть:

[]

При просмотре решения я вижу, что сначала использовался массив # uniq:

def filter_out!(array, &prc)
    array.uniq.each { |el| array.delete(el) if prc.call(el) }
end

arr_2 = [1, 7, 3, 5 ]
filter_out!(arr_2) { |x| x.odd? }
p arr_2

, и был отображен правильный результат:

[]

Итак, я предполагаю, в чем мой вопрос , почему вам нужно использовать Array # uniq, чтобы получить правильное решение? спасибо за помощь!

Answer 1

Проблема здесь в методе delete модификации исходного массива. Вот сделка, если вы разместите некоторую информацию:

def filter_out!(array, &prc)
  array.each.with_index do |el, i|
    p "Current index #{i}"
    p "Current array #{array}"
    p "Current element #{el}"
    array.delete(el) if prc.call(el)
  end
end

arr_2 = [1, 7, 3, 5 ]
filter_out!(arr_2) { |x| x.odd? }
# Output:
#"Current index 0"
# "Current array [1, 7, 3, 5]"
# "Current element 1"
# "Current index 1"
# "Current array [7, 3, 5]"
# "Current element 3"

Объясните:

• В первый раз элемент будет 1, после его удаления массив будет [7, 3, 5]
• Второй раз, индекс в итерации равен 1, он получает текущий элемент с этим индексом в текущем массиве, в данном случае 3 не 7, и удаляет его после удаления массив имеет вид [3, 5]
• Через два раза он останавливает итерацию, потому что текущий индекс выходит за пределы диапазона текущего массива

Используя uniq, вы получаете правильный результат, потому что array.uniq он создает копию исходного массива, когда исходный массив изменяется, итерация по-прежнему соответствует ожидаемой.

Answer 2

Как правило, не только для этого вопроса и не только для Ruby, никогда не рекомендуется изменять коллекцию, когда вы повторяете ее. Только не делай этого. Когда-либо.

На самом деле, лично я просто думаю, что вам следует избегать любых мутаций, насколько это возможно и разумно, но это может быть немного экстремально.

Ваш код также совершает еще один кардинальный грех: никогда не изменять аргумент. Когда-либо. Вы должны использовать только аргументы для вычисления результата, вы никогда не должны их изменять. Это очень удивительно для любого, кто вызывает ваш метод, а в программировании сюрпризы опасны. Они приводят к ошибкам и дырам в безопасности.

Наконец, вы неправильно используете соглашение об именах bang !. Челка используется для обозначения «более удивительного» из пары методов. Вам следует только иметь метод filter_out!, если у вас также есть метод filter_out. И, говоря о стиле, отступ в Ruby составляет 2 пробела, а не 4, согласно стандартному стилю кодирования сообщества.

Хорошо, сказав это, давайте посмотрим, что происходит в вашем коде.

Вот соответствующая часть реализации Array#each из реализации Rubinius Ruby, определенной в core/array.rb#L62-L77:

def each
  i = @start
  total = i + @total
  tuple = @tuple

  while i < total
    yield tuple.at(i)
    i += 1
  end
end

Как видите, это всего лишь while l oop увеличение индекса каждый раз. Другие реализации Ruby аналогичны, например, вот упрощенная версия реализации J Ruby в core/src/main/java/org/jruby/RubyArray.java#L1805-L1818:

public IRubyObject each(ThreadContext context, Block block) {
    for (int i = 0; i < size(); i++) {
        block.yield(context, eltOk(i));
    }
}

Опять же, просто простой индекс l oop.

В вашем случае мы начинаем с массива, чье резервное хранилище выглядит так:

1 7 3 5

На первая итерация each, счетчик итераций имеет индекс 0:

1 7 3 5
↑

1 нечетно, поэтому мы удаляем его, и теперь ситуация выглядит так:

7 3 5
↑

Последнее, что мы делаем на итерации l oop, - это увеличиваем счетчик итераций на единицу:

7 3 5
  ↑

Хорошо, на следующей итерации мы снова проверяем: 3 is odd, поэтому мы его удаляем:

7 5
  ↑

Увеличиваем счетчик итераций:

7 5
    ↑

И теперь у нас есть условие выхода нашего l oop: i is no длиннее, чем размер массива: i равно 2, и размер также 2.

Обратите внимание, что в реализации J Ruby размер проверяется с помощью вызова по методу size(), что означает, что он каждый раз пересчитывается. В Rubinius, однако, размер кэшируется и вычисляется только один раз перед запуском l oop. Таким образом, Rubinius фактически попытается продолжить работу и получить доступ к третьему элементу вспомогательного кортежа , которого не существует , что приводит к исключению NoMethodError:

NoMethodError: undefined method `odd?' on nil:NilClass.

Доступ к несуществующему элементу Rubinius::Tuple возвращает nil, а each затем передает этот nil блоку, который пытается вызвать Integer#odd?.

Важно отметить, что Рубиниус здесь не делает ничего плохого . Тот факт, что это вызывает исключение, - это , а не ошибка в Rubinius. Ошибка находится в вашем коде: изменение коллекции во время итерации по ней просто недопустимо.

Теперь все это объясняет, почему решение, которое вызывает Array#uniq сначала работает: Array#uniq возвращает массив новый , поэтому массив, который вы повторяете (тот, который возвращается из Array#uniq), и массив, который вы изменяете (тот, на который ссылается параметр array binding) - это два разных массива . Вы бы получили тот же результат, например, Object#clone, Object#dup, Enumerable#map или многие другие. В качестве примера:

def filter_out(array)
  array.map(&:itself).each { |el| array.delete(el) if yield el }
end

arr_2 = [1, 7, 3, 5]
filter_out(arr_2, &:odd?)
p arr_2

Однако более идиоматическое решение c Ruby будет примерно таким:

def filter_out(array, &blk)
  array.delete_if(&blk)
end

arr_2 = [1, 7, 3, 5]
arr_3 = filter_out(arr_2, &:odd?)
p arr_3

Это устраняет все проблемы с вашим кодом:

• Он не изменяет массив.
• Он не изменяет ни один аргумент.
• Фактически, мутации не происходит в все .
• Он использует существующие методы из основной библиотеки Ruby вместо того, чтобы заново изобретать колесо.
• Без звука !
• Отступ в два пробела.

Единственный реальный вопрос: нужен ли метод вообще, или было бы разумнее просто написать

arr_2 = [1, 7, 3, 5]
arr_3 = arr_2.delete_if(&:odd?)
p arr_3

Answer 3

При обходе массива используется какой-то внутренний «курсор», указывающий на текущий элемент, например:

[ 1, 7, 3, 5 ]  # 1st step
# ^

[ 1, 7, 3, 5 ]  # 2nd step (increment cursor)
#    ^

# etc.

Если вы удалите текущий элемент во время итерации, курсор сразу же укажет на следующий элемент , таким образом пропуская элемент, когда он увеличивается на следующем ходу:

[ 1, 7, 3, 5 ]  # 1st step
# ^

[ 7, 3, 5 ]     # 1nd step (remove element under cursor)
# ^

[ 7, 3, 5 ]     # 2nd step (increment cursor)
#    ^

[ 7, 5 ]        # 2nd step (remove element under cursor)
#    ^

# done

Типичный обходной путь - перебрать массив в обратном порядке , то есть:

[ 1, 7, 3, 5 ]  # 1st step
#          ^

[ 1, 7, 3 ]     # 1nd step (remove element under cursor)
#          ^

[ 1, 7, 3 ]     # 2nd step (decrement cursor)
#       ^

[ 1, 7 ]        # 2nd step (remove element under cursor)
#       ^

# etc.

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

Приведенный выше как Ruby код:

def filter_out!(array)
  (array.size - 1).downto(0) do |i|
    array.delete_at(i) if yield array[i]
  end
end