コードがタイムアウトするRuby

Question

数字の集合の要素の数が奇数または偶数であるため、その集合の中央値はそれぞれ、中間値またはリストの2つの中間値の平均として定義されます。ソートされます。

以下は、数字のリストの「実行中の」中央値を計算するためのコードです。 「実行中」の中央値は動的中央値であり、これまでに登場したすべての数値に対してリストがスキャンされるので、新しい数値の出現とともに再計算される。入力は整数nでn個の整数のリストが続き、出力はリストがスキャンされるときにリストの "実行中の"メジアンでなければなりません。 4 [4]の中央値、2.5（+ 4（1）/ 2）[4,1]と4の中央値であるので、例えば、

3 
4 
1 
5 

は

4 
2.5 
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）