次のような2つのソートされた配列があるとします。
a = array([1,2,4,5,6,8,9])
b = array([3,4,7,10])
出力を次のようにしたいと思います。
c = array([1,2,3,4,5,6,7,8,9,10])
また：
c = array([1,2,3,4,4,5,6,7,8,9,10])
私は次のことができることを知っています：
c = unique(concatenate((a,b))
私が扱っている配列には何百万もの要素があるので、もっと速い方法があるかどうか疑問に思っています。
どんなアイデアでも大歓迎です。ありがとう
numpyを使用しているので、bisecがまったく役に立たないと思います...代わりに、2つの小さなことを提案します。
np.sort使用してください。c.sort()np.unique配置されていないものを使用する必要がありますnp.sort。したがって、を使用する代わりにnp.unique、手動でロジックを実行します。IE。最初に（インプレースで）ソートしてからnp.unique、手動でメソッドを実行し（Pythonコードも確認してください）、それを使用flag = np.concatenate(([True], ar[1:] != ar[:-1]))してunique = ar[flag]（arをソートして）実行します。もう少し良くするには、おそらくそれ自体でフラグ操作を行う必要があります。flag = np.ones(len(ar), dtype=bool)そして、np.not_equal(ar[1:], ar[:-1], out=flag[1:])これは基本的にの完全なコピーを1つ回避しますflag。.sort、3つの異なるアルゴリズムがあります。配列はほぼ既に並べ替えられている可能性があるため、並べ替え方法を変更すると速度が異なる場合があります。これにより、完全なものが得られたものに近くなります（事前に一意の処理を行う必要はありません）。
def insort(a, b, kind='mergesort'):
# took mergesort as it seemed a tiny bit faster for my sorted large array try.
c = np.concatenate((a, b)) # we still need to do this unfortunatly.
c.sort(kind=kind)
flag = np.ones(len(c), dtype=bool)
np.not_equal(c[1:], c[:-1], out=flag[1:])
return c[flag]
要素をメモリ内でフラットにするため、要素を中央に挿入することarrayは非常に非効率的な操作です。そのため、別の要素を挿入するたびにすべてをシフトする必要があります。結果として、おそらく使用したくないでしょうbisect。そうすることの複雑さはおよそ O(N^2)です。
あなたの現在のアプローチはO(n*log(n))ですので、それははるかに良いですが、それは完璧ではありません。
すべての要素をハッシュテーブル（などset）に挿入するのは何かです。一意化には時間がかかりO(N)ますが、次に、どちらがかかるかを並べ替える必要がありますO(n*log(n))。まだ素晴らしいではありません。
実際のO(N)解決策では、配列を割り当ててから、入力リストの最小の先頭を取得して、一度に1つの要素を配列に入力します。マージ。残念ながら、numpyPythonもそのようなものを持っていないようです。解決策は、Cythonで作成することです。
漠然と次のようになります。
def foo(numpy.ndarray[int, ndim=1] out,
numpy.ndarray[int, ndim=1] in1,
numpy.ndarray[int, ndim=1] in2):
cdef int i = 0
cdef int j = 0
cdef int k = 0
while (i!=len(in1)) or (j!=len(in2)):
# set out[k] to smaller of in[i] or in[j]
# increment k
# increment one of i or j
タイミングについて知りたい場合は、常にtimeit。以下に、さまざまなメソッドのサブセットとそのタイミングを示します。
import numpy as np
import timeit
import heapq
def insort(a, x, lo=0, hi=None):
if hi is None: hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if x < a[mid]: hi = mid
else: lo = mid+1
return lo, np.insert(a, lo, [x])
size=10000
a = np.array(range(size))
b = np.array(range(size))
def op(a,b):
return np.unique(np.concatenate((a,b)))
def martijn(a,b):
c = np.copy(a)
lo = 0
for i in b:
lo, c = insort(c, i, lo)
return c
def martijn2(a,b):
c = np.zeros(len(a) + len(b), a.dtype)
for i, v in enumerate(heapq.merge(a, b)):
c[i] = v
def larsmans(a,b):
return np.array(sorted(set(a) | set(b)))
def larsmans_mod(a,b):
return np.array(set.union(set(a),b))
def sebastian(a, b, kind='mergesort'):
# took mergesort as it seemed a tiny bit faster for my sorted large array try.
c = np.concatenate((a, b)) # we still need to do this unfortunatly.
c.sort(kind=kind)
flag = np.ones(len(c), dtype=bool)
np.not_equal(c[1:], c[:-1], out=flag[1:])
return c[flag]
結果：
martijn2 25.1079499722
OP 1.44831800461
larsmans 9.91507601738
larsmans_mod 5.87612199783
sebastian 3.50475311279e-05
ここでの私の具体的な貢献はlarsmans_mod、2セットの作成を回避することです。1セットしか作成しないため、実行時間がほぼ半分に短縮されます。
martijn競争するには遅すぎたため、EDITは削除されました。わずかに大きい配列（ソート済み）入力についてもテストされています。また、出力の正確さについてもテストしていません...
の使用に関する他の回答に加えて、bisect.insortパフォーマンスに満足できない場合は、blistモジュールを使用してみてくださいbisect。パフォーマンスが向上するはずです。
従来のlist 挿入の複雑さはですがO(n)、挿入blistの複雑さはですO(log(n))。
また、配列はソートされているようです。その場合、muduleのmerge関数を使用して、両方の配列が事前にソートされているという事実を利用できます。heapqこのアプローチでは、メモリ内に新しいアレイを作成するため、オーバーヘッドが発生します。このソリューションの時間計算量はO(n+m)であるのに対し、ソート付きのソリューションはO(n*m)複雑さ（n要素* m挿入）であるため、検討するオプションになる場合があります。
import heapq
a = [1,2,4,5,6,8,9]
b = [3,4,7,10]
it = heapq.merge(a,b) #iterator consisting of merged elements of a and b
L = list(it) #list made of it
print(L)
出力：
[1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10]
繰り返し値を削除する場合は、groupbyを使用できます。
import heapq
import itertools
a = [1,2,4,5,6,8,9]
b = [3,4,7,10]
it = heapq.merge(a,b) #iterator consisting of merged elements of a and b
it = (k for k,v in itertools.groupby(it))
L = list(it) #list made of it
print(L)
出力：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
このようなマージにbisectモジュールを使用して、2番目のPythonリストを最初のPythonリストにマージすることができます。
関数はbisect*numpy配列に対して機能しますが、insort*機能しません。モジュールのソースコードを使用してアルゴリズムを適応させるのは簡単です。非常に基本的です。
from numpy import array, copy, insert
def insort(a, x, lo=0, hi=None):
if hi is None: hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if x < a[mid]: hi = mid
else: lo = mid+1
return lo, insert(a, lo, [x])
a = array([1,2,4,5,6,8,9])
b = array([3,4,7,10])
c = copy(a)
lo = 0
for i in b:
lo, c = insort(c, i, lo)
カスタムinsortが実際にここに何かを追加しているわけではありませんが、デフォルトでbisect.bisectも問題なく機能します。
import bisect
c = copy(a)
lo = 0
for i in b:
lo = bisect.bisect(c, i)
c = insert(c, i, lo)
この適応を使用insortすると、結合して並べ替えるよりもはるかに効率的です。bもソートされているためlo、各ループの配列全体を考慮する代わりに、挿入ポイントを追跡し、そこから始まる次のポイントを検索できます。
保存する必要がない場合はa、その配列を直接操作して、コピーを保存してください。
さらに効率的：両方のリストがソートされているため、次を使用できますheapq.merge：
from numpy import zeros
import heapq
c = zeros(len(a) + len(b), a.dtype)
for i, v in enumerate(heapq.merge(a, b)):
c[i] = v
これにはbisectモジュールを使用します。
import bisect
a = array([1,2,4,5,6,8,9])
b = array([3,4,7,10])
for i in b:
pos = bisect.bisect(a, i)
insert(a,[pos],i)
現在これをテストすることはできませんが、機能するはずです
sortnpパッケージは、ソートされたnumpy-arrayの効率的なマージを実装し、値を一意にするのではなく、値をソートするだけです。
import numpy as np
import sortednp
a = np.array([1,2,4,5,6,8,9])
b = np.array([3,4,7,10])
c = sortednp.merge(a, b)
私は時間を測定し、この回答でそれらをnumpyのマージソート（v1.17.4）よりも優れている同様の投稿と比較しました。
誰も言及していないようですunion1d（union1d）。現在、これはのショートカットですunique(concatenate((ar1, ar2)))が、覚えておくべき短い名前であり、ライブラリ関数であるため、numpy開発者によって最適化される可能性があります。insortこれは、大規模アレイに対するsebergの受け入れられた回答と非常によく似ています。これが私のベンチマークです：
import numpy as np
def insort(a, b, kind='mergesort'):
# took mergesort as it seemed a tiny bit faster for my sorted large array try.
c = np.concatenate((a, b)) # we still need to do this unfortunatly.
c.sort(kind=kind)
flag = np.ones(len(c), dtype=bool)
np.not_equal(c[1:], c[:-1], out=flag[1:])
return c[flag]
size = int(1e7)
a = np.random.randint(np.iinfo(np.int).min, np.iinfo(np.int).max, size)
b = np.random.randint(np.iinfo(np.int).min, np.iinfo(np.int).max, size)
np.testing.assert_array_equal(insort(a, b), np.union1d(a, b))
import timeit
repetitions = 20
print("insort: %.5fs" % (timeit.timeit("insort(a, b)", "from __main__ import a, b, insort", number=repetitions)/repetitions,))
print("union1d: %.5fs" % (timeit.timeit("np.union1d(a, b)", "from __main__ import a, b; import numpy as np", number=repetitions)/repetitions,))
私のマシンでの出力：
insort: 1.69962s
union1d: 1.66338s