5

並べ替えられたnumpy配列の正しい位置に値を挿入する最も簡単な方法は何ですか?

bたとえば、 のすべての値を に挿入したいと思いますa。

a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70]

b = [5,7,9,45]

aの各値をループしてb、そのように挿入しようとしました。私もbisect_left方法を試しました： 

for i in b:
a.insert(bisect_left(a,i),i)

何十万ものデータ要素を通過する必要があるため、どちらの方法も遅すぎます。

何か案は？

4

5 に答える 5

4

注意しましょうn = len(a) and m = len(b)、

  1. バイナリ検索を使用して各要素の位置を見つけて挿入できます。これはm*n*log(n)時間で行われます
  2. n + mの複雑さを持つ両方の配列をマージできます
  3. 特殊な構造、バランスの取れたバイナリ ツリーを使用できます。Python でこれらの多くの実装を見つけることができます。時間の複雑さはmlog(n)になります。

n と m の可能な値が与えられると、どのソリューションが最適かを判断できますが、それよりも優れた結果を期待しないでください。

于 2013-11-08T13:37:32.740 に答える
4

組み込みsortメソッドを使用するだけです。実装しtimsortます。リストがほぼソートされている場合、非常に高速になります。

a.extend(b)
a.sort()
于 2013-11-08T13:34:45.250 に答える