Срок действия кода Ruby

Question

По мере того, как количество элементов в наборе чисел нечетно или равно, медиана этого набора определяется соответственно как среднее значение или среднее из двух средних значений в списке, которое возникает, когда набор сортируется.

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

3 
4 
1 
5 

должны давать

4 
2.5 
4 

потому, что 4 является медианой [4], 2.5 ((1 + 4)/2) является медианой [4,1] и 4 снова является медианой [4,1,5].

Моя программа работает правильно, но это время на определенном тесте на очень больших входах. Я подозреваю, что этот шаг копирования является проблемой.

a=(a[0,(k=a.index(a.bsearch{|x|x>=t}))].push(t) + a[k,a.length-k]) 

Но я не уверен, потому что эта копия предназначена для мелкой копии, насколько я знаю. Кроме того, я не использую регулярную вставку в любом месте, что связано с перемещением элементов и, следовательно, с замедлением кода, в массив, содержащий числа.

n=gets.chomp.to_i 
a=[] 
n.times do 
    t=gets.chomp.to_i 

    a==[]||(t<=a.first) ? a.unshift(t): t>=a.last ? a.push(t) : a=(a[0,(k=a.index(a.bsearch{|x|x>=t}))].push(t) + a[k,a.length-k]) 


    p (l=a.count)%2==0 ? ((a[l/2] + a[l/2-1])/2.0).round(1):a[(l-1)/2].round(1) 
end 

Может ли кто-нибудь указать, где проблема? Спасибо.

Здесь представлена ​​менее запутанная версия.

n=gets.chomp.to_i 
a=[] 
n.times do 
    t=gets.chomp.to_i 


    if a==[]||(t<=a.first) 
     a.unshift(t) 
    else 
     k=a.index(a.bsearch{|x|x>=t}) 
     if k.nil? == true 
      k=a.length 
     end 
     a=a[0,k].push(t)+ a[k,a.length-k] 
    end 
    p (l=a.count)%2==0 ? ((a[l/2] + a[l/2-1])/2.0).round(1):a[(l-1)/2].round(1) 
end 

Answer 1

Я думаю ...

a=(a[0,(k=a.index(a.bsearch{|x|x>=t}))].push(t) + a[k,a.length-k]) 

... потому что это создает новый массив каждый раз, когда, скорее всего, это дорогостоящая операция, как массив становится все больше.

Лучше может быть что-то, что мутирует исходный массив.

a.insert((a.index{|x|x>t} || -1), t) 

Он также обрабатывает краевые случаи меньше первого или более последнего, поэтому вы можете удалить эти тесты. Также работает на первом проходе (пустой массив a)