ソートされた位置の配列に要素を追加する方がより効果的ですか？

Question

このメソッドは、要素を取得し、既に順序付けられた配列の順序付けられた位置に挿入するだけです。

@ary = [9,7,3,1] 
insert_in_order(5) 
@ary = [9,7,5,3,1] 

私はすでに、配列の値をプッシュしてソートを実行するよりも速いことを確認しました。それは後で。しかし、これはこれ以上のステップを取っているようです。これを行うためのより効率的で効率的な方法がありますか？

def insert_in_order val 
    @val = val 
    @ary.each_with_index{|v,i| 
     if @val > v 
      @found_index = i 
      break 
     end 
     } 
    @found_index ? @ary.insert(@found_index, @val) : @ary.push(@val) 
end 

Answer 1

バイナリ検索を行い、この要素が属するインデックスを見つけて、そのインデックスに挿入します。インデックスを見つけるにはO（log（n））がかかり、現在のリストがソートされていることが保証されている場合にのみ動作します。

Answer 2

@Adithya Surampudiが示唆するように、これは非常に遅いでしょう。定義による配列の要素は隣接するメモリ位置に配置されているので、の最後の位置にの配列に挿入すると、i要素は新しい要素のためのスペースを作るために1つ右の位置に移動する必要があります。赤黒のツリー（またはあなたが運が良ければ通常のバイナリ検索ツリー）など、別のデータ構造を検討することもできます。

Answer 3

あなたがあなたのアプリのボトルネックを持って決定的に知るまでは、パフォーマンスよりも重要であるIMHO、それはあなたが今持っているものよりもパフォーマンスではないのですが、私はそれがうまく読み込んだと思う：

>> ary = [9,7,3,1] #=> [9, 7, 3, 1] 
>> val = 5 #=> 5 
>> bigger, smaller = ary.partition{|x| x >= val} #=> [[9, 7], [3, 1]] 
>> [*bigger, val, *smaller] #=> [9, 7, 5, 3, 1]