2

我已经在这几天了，我无法破解这个错误：

[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 函数。随机选择，中值枢轴选择，一切都顺利进行，直到我点击了这个。这是代码partition：

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 调用它时它可以工作，所以我认为问题出在线性时间 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
4

1 回答 1

3

该错误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也将存在于数组中，这对我来说似乎是一个非常值得怀疑的假设。

于 2013-11-27T11:22:53.883 回答