ruby - 解释简洁的 ruby​​ 'nil' 错误

Question

我已经解决这个问题几天了，但无法解决这个错误:

[3] pry(main)> my_list = (1..10).to_a.sample(10)
=> [3, 5, 9, 2, 7, 6, 10, 4, 1, 8]
[4] pry(main)> linear_select(my_list,4)
NoMethodError: undefined method `-' for nil:NilClass
from .../selector/select.rb:44:in `partition'

背景

我正在尝试使用或多或少严格的 CLRS 实现来实现有保证的线性时间 SELECT 函数。随机选择、中枢轴选择一切都进展顺利，直到我遇到了这个。这是分区的代码:

def partition(my_list, part_start, part_end, pivot = my_list[part_end])
# From CLRS p. 171
# In-place rearrangement of subarrays to find rank of pivot. Does no rearrangement 
# if the array is already sorted.
# Returns the rank of the pivot, which is set by default to the end of the partition.

return(0) if my_list.length == 1

  sort_separator = part_start - 1
  for loop_ind in (part_start..(part_end-1)) # This is the offending line 44
    if my_list[loop_ind] <= my_list[part_end]
      sort_separator += 1
      my_list[sort_separator],my_list[loop_ind] = 
        my_list[loop_ind],my_list[sort_separator]
    end
  end
  my_list[sort_separator+1],my_list[part_end] = 
    my_list[part_end],my_list[sort_separator+1]

  return(sort_separator+1)
end

这几乎是 CLRS 伪代码的逐字转录(相应地，基本上没有错误检查)，并且当由我编写的其他风格的 SELECT 调用时它可以工作，所以我认为问题在于线性-时间选择:

def linear_select(my_list, rank)
# From CLRS 9.3
# select algorithm in worst-case linear time

group_size = 5

# 1. Divide the elements of the input array into (n/5).floor(+1) groups
groups = my_list.each_slice(group_size).to_a

# 2. Sort, get medians of each group (the median method defined above includes
# sorting)
medians = groups.each.collect{|group| group.median}

# 3. Find median of medians using linear_select recursively
# median_of_medians = linear_select(medians,medians.length/2.floor-1) # doesn't work yet
median_of_medians = medians.median

# Partition input array around median of medians using partition with pivot
# argument -- where the pivot passes the array index
new_part = partition(my_list, 0, my_list.index(median_of_medians-1), median_of_medians)

# The rest of the algorithm follows the select() archetype.
pivot = new_part + 1

if rank == pivot
    return my_list[new_part] # -1 here for zero-indexing
  elsif rank < pivot
    return(linear_select(my_list[0..(pivot - 1)], rank))
  else
    return(linear_select(my_list[pivot..-1], rank - pivot -1 ))
  end

end

我在解释器中手动跟踪它，没有收到任何错误。 (我还没有学会如何使用调试器，尽管我花了一个小时左右的时间查看不同的软件包，例如hammertime。)事实上，由于错误出现之前进行的改组，如果我再次运行它，它就会起作用:

[5] pry(main)> linear_select(my_list,4)
=> 4
[6] pry(main)> my_list
=> [3, 2, 4, 5, 7, 6, 10, 9, 1, 8]

我认为错误是因为上部索引(partition() 中的第三个参数)超出范围，但我不清楚这是如何发生的。

任何解释此错误的帮助，或朝着正确方向插入找出原因的插入，我们将不胜感激。我感觉我已经很接近了。

编辑:供引用，这是我实现Array#median方法(较低中位数)的方法:

class Array # extends Array to include median calculation
def median
    # returns floor-median of list of values
    self.sort[((self.length - 1)/2.0).floor()]
  end
end

Answer 1

错误undefined method '-' for nil:NilClass 表示减法运算的左侧是值nil 而不是数字。在您的情况下，这意味着 part_end 参数为 nil。当 my_list.index(median_of_medians-1) 返回 nil 而不是数字时，就会发生这种情况，这意味着 median_of_medians-1 未在数组my_list。我不熟悉您正在实现的算法，所以这就是我所能为您提供的，希望它有所帮助。

编辑:获取数字数组的中位数保证返回该数组中的数字，但您似乎假设数字median_of_medians-1也将存在于数组中，这对我来说似乎是一个非常可疑的假设。