Интерпретировать лаконичную рубиновую ошибку 'ноль'

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'

Фон

Я пытаюсь реализовать гарантированную линейную функцию SELECT, используя более или менее строгие реализации CLRS. Все шло гладко с рандомизированным отбором, отбором по срединной оси, пока я не нажму этот. Вот код для 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

Я проследил это вручную в интерпретаторе и не получил никаких ошибок. (Я еще не научился использовать отладчик, хотя я прожег около часа, просматривая различные пакеты, например, время молотка.) Фактически, благодаря перемешиванию, которое происходит до появления ошибки, оно работает, если я снова его запускаю:

[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 также будет существовать в массиве, что мне кажется довольно сомнительным предположением.