Ruby: слишком большой уровень стека (SystemStackError), реализующий сортировку слиянием с подсчетом инверсий - PullRequest
Новая
       7

Ruby: слишком большой уровень стека (SystemStackError), реализующий сортировку слиянием с подсчетом инверсий

1 голос
/ 22 марта 2012

Вот мой код. 

@@inversions = 0
numbers = [very big array]

def merge_sort(array)
  return array if array.size <= 1

  left = array.slice(0, (array.size / 2).round)
  right = array - left
  merge(merge_sort(left), merge_sort(right))
end

def merge(left, right)
  return right if left.empty? # crashes here with stack level too deep
  return left if right.empty?

  if left.first <= right.first
    [left.first] + merge(left[1..-1], right)
  else
    @@inversions += left.size
    [right.first] + merge(left, right[1..-1])
  end
end

Подскажите, пожалуйста, почему это не получается? (работает с массивами размером менее ~ 15000)

Ответы [ 2 ]

3 голосов
/ 22 марта 2012

Вероятно, причина в вашей рекурсивной функции слияния. Вы идете на один уровень глубже в стеке для каждого элемента в массиве. Стандартная сортировка слиянием не должна идти глубже, чем lg (N). Попробуйте переписать merge для повторения, а не для рекурсии.

Что-то вроде 

def merge left,right
  a = []
  while !left.empty? and !right.empty?
    if left.first < right.first
       a<<left.shift
    else 
       a<<right.shift
    end
  end
  a + left + right
end
0 голосов
/ 22 марта 2012

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

В компьютерной архитектуре есть область микросхемы, выделенная как «стек», которая обычно является «блокнотом» LIFO («последний пришел - первым вышел»). Данные «помещаются» и «выталкиваются» в стек и выводятся из него иногда автоматически, а иногда по выбору программистов.

У этого стека есть конечная длина (в * 86 переполнение этого стека перезаписывает другую специальную область чипа (EIP), которая является классическим методом взлома для изменения управления потоком программ, но в любом случае ...

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

...