指定された整数がint配列の2つの要素の合計に等しいかどうか

what is optimal algorithm to check if a given integer is equal to sum of two elements of an int array? – StackOverflow

最適なアルゴリズムは分からないけど,numpyソリューションとしては,
空間効率を気にしなくて良い程度(のデータサイズ;中規模以下)なら,
何も考えずにブロードキャストでもリーズナブルだが,
一定サイズを超える場合(大規模データ),
func3の様な方法がリーズナブルチョイスになる.

numpyはopenblasを用いて並列化されているので,
その場合,Big-Oをどう考えれば良いのか分からないが,
多分,func2はO(n^2)で並列化が十分に効いている時はほぼO(n)以下,
func3はO(n)になっているかなと.

import numpy as np


def func1(S, k):
  res = np.empty_like(k, dtype=np.bool)
  for i, t in enumerate(k.tolist()):
    cond = (S + S[:, None]) == t
    np.fill_diagonal(cond, False)
    res[i] = cond.any()
  return res


def func2(S, k):
  cond = (S + S[:, None]) == k[:, None, None]
  cond[:, np.arange(len(S)), np.arange(len(S))] = False
  return cond.any((2, 1))


def func3(S, k):
  diff = k[:, None] - S
  cond1 = np.isin(diff, S)
  cond2 = diff != S
  return np.logical_and(cond1, cond2).any(-1)


S = np.array([1,2,3,4])
k = np.array([5, 6, 8, 11])
print(func1(S, k))
print(func2(S, k))
print(func3(S, k))
%timeit func1(S, k)
%timeit func2(S, k)
%timeit func3(S, k)
S = np.arange(1, 10)
k = np.random.randint(5, 20, size=10)
%timeit func1(S, k)
%timeit func2(S, k)
%timeit func3(S, k)
S = np.arange(1, 100)
k = np.random.randint(5, 200, size=100)
%timeit func1(S, k)
%timeit func2(S, k)
%timeit func3(S, k)
S = np.arange(1, 1000)
k = np.random.randint(5, 2000, size=1000)
%timeit func1(S, k)
%timeit func2(S, k)
%timeit func3(S, k)
[ True  True False False]
[ True  True False False]
[ True  True False False]

10000 loops, best of 3: 29.4 µs per loop
100000 loops, best of 3: 11.1 µs per loop
10000 loops, best of 3: 21.9 µs per loop

10000 loops, best of 3: 70.7 µs per loop
100000 loops, best of 3: 12.5 µs per loop
10000 loops, best of 3: 32.6 µs per loop

100 loops, best of 3: 2.19 ms per loop
1000 loops, best of 3: 566 µs per loop
1000 loops, best of 3: 574 µs per loop

1 loop, best of 3: 2.45 s per loop
1 loop, best of 3: 641 ms per loop
10 loops, best of 3: 87.6 ms per loop
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください