为什么我的过滤方法没有删除一些应该删除的元素？

Question

我正在尝试创建一个名为 filer_out 的方法！它接受一个数组和一个 proc，并且 returns 是相同的数组，但是每个元素在运行通过 proc 时 returns 为真，但需要注意的是我们不能使用数组#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]

即使答案应该是：

[]

查看解决方案后，我发现首先使用了 Array#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

遍历数组使用某种指向当前元素的内部“游标”，例如：

[ 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

典型的work-around是以逆序迭代数组，即：

[ 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

Answer 3

作为一般规则，不仅针对这个问题，也不仅仅是针对 Ruby，绝不在迭代时改变集合是个好主意超过它。只是不要那样做。曾经。

实际上，就个人而言，我只是认为您应该在可行和明智的情况下完全避免任何突变，但这可能有点极端。

您的代码还犯了另一个大错：从不改变参数。曾经。你应该只使用参数来计算结果，你不应该改变它们。对于任何调用您的方法的人来说，这都是非常令人惊讶的，而在编程中，意外是危险的。它们会导致错误和安全漏洞。

最后，您使用的 bang ! 命名约定有误。爆炸用于标记对方法中的“更令人惊讶”。如果您也有一个filter_out方法，那么您应该只有有一个filter_out!方法。说到风格，Ruby 中的缩进是 2 个空格，而不是 4 个，按照标准社区编码风格。

好吧，话虽如此，让我们看看您的代码中发生了什么。

这里是Array#each from the Rubinius Ruby implementation, defined in 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 循环，每次递增索引。其他 Ruby 实现类似，例如这是 JRuby's implementation in 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));
    }
}

同样，只是一个简单的索引循环。

对于您的情况，我们从一个数组开始，其 后备存储 如下所示：

1 7 3 5

在 each 的第一次迭代中，迭代计数器位于索引 0:

1 7 3 5
↑

1是奇数，所以我们删除它，现在的情况是这样的：

7 3 5
↑

我们在循环迭代中做的最后一件事是将迭代计数器加一：

7 3 5
  ↑

好的，在下一次迭代中，我们再次检查：3是奇数，所以我们删除它：

7 5
  ↑

我们增加迭代计数器：

7 5
    ↑

现在我们有了循环的退出条件： i 不再小于数组的大小： i 是 2 并且大小也是 2.

请注意，在 JRuby 实现中，通过调用 size() 方法检查大小，这意味着每次都是 re-calculated。然而，在 Rubinius 中，大小被缓存，并且只在循环开始前计算一次。因此，Rubinius 实际上会尝试继续前进并访问不存在的支持元组 的第三个元素，这会导致此 NoMethodError 异常：

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

访问Rubinius::Tuplereturnsnil的non-existing元素，然后each将nil传递给块，它试图调用 Integer#odd?.

重要的是要注意 Rubinius 在这里没有做错什么。它引发异常的事实不是 Rubinius 中的错误。该错误在您的代码中：根本不允许在遍历集合时改变集合。

现在所有这些都解释了为什么调用 Array#uniq first works: Array#uniq returns a new array, so the array you are iterating over (the one returned returned from Array#uniq) and the array you are mutating (the one referenced by the array parameter binding) are two different arrays. You would have gotten the same result with, e.g. 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

然而，更惯用的 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 核心库中的现有方法，而不是 re-inventing 轮子。
没有爆炸!
两个空格缩进。

唯一真正的问题是是否需要该方法，或者只写

是否更有意义

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

为什么我的过滤方法没有删除一些应该删除的元素？

Why is my filter method not removing some elements that should be removed?

ruby

array-unique

proc