Python3:近い値をもつリストを判定したい
解決済
回答 3
投稿
- 評価
- クリップ 2
- VIEW 236
リストの1つ目の要素どうしの絶対値,2つ目の要素どうしが互いに一定の閾値(例えば30)以下のリストをみつけたら削除したいです.
#例
a_list = [[802, 1593], [802, 1601], [93, 1019], [614, 1019], [1138, 1608], [1128, 1253]]
#[802, 1593]の場合は,[802, 1601]を削除
ads(802-802) < 30 and ads(1593-1601) < 30 # => 削除
総当たりで比較する方法では,計算量が大きくなりすぎるので,効率的な方法があれば教えて欲しいです.
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
checkベストアンサー
+3
Listはサイズが大きくなると変更コストも大きくなるので、一定のサイズを超えると変更ではなく再生成のほうが早いです。あとはループを上手く回してGeneratorからListを一気に再生成させれば、Listの変更コスト0かつオーダーNで近接要素を間引くことができます。ループ内の計算コストも高くないので、そんなに時間はかからないと思います。
from operator import __sub__
def filterclose(coordinates, distance):
a = coordinates[0]
yield a
for b in coordinates[1:]:
if not all(diff < distance for diff in map(abs, map(__sub__, a, b))):
yield b
a = b
a_list = [[802, 1593], [802, 1601], [93, 1019], [614, 1019], [1138, 1608], [1128, 1253]]
b_list = list(filterclose(a_list, 40))
print(b_list) # -> [[802, 1593], [93, 1019], [614, 1019], [1138, 1608], [1128, 1253]]
追記
複素数使ったりしながら色々試してたら半分以下の時間で完了するようになった。。。
def filterclose(coordinates, distance):
iterable = iter(coordinates)
threshold = float(distance)
a = next(iterable)
a_comp = complex(*a)
yield a
for b in iterable:
b_comp = complex(*b)
diff = b_comp - a_comp
if abs(diff.real) >= threshold or abs(diff.imag) >= threshold:
yield b
a, a_comp = b, b_comp
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+3
実際のプログラミングにおいて計算オーダーを気にするのは場合によりけりと思います。例えば100個程度しかないデータを処理するのに総当たりを用いて計算量がN^2のオーダーになるからといって、それほど気にする必要もないと思います。10^4程度の計算なんて一瞬で終わるのですから。しかしデータ量が1万とか10万ともなればさすがに多少複雑であっても何か効率のよい方法を考えるべきでしょう。
質問者さんは「データ量が多くても使えるような一般的なアルゴリズム」を考えようとしていますか?それともご自分のアプリケーションに使うための専用の論理を考えようとしていますか?それによりかけるべき手間は変わってくると思います。
それはさておき・・・
総当たりを避ける方法としては例えば探すべき対象は値の大きさで決まるのですからあらかじめ比較対象データをソートしておきバイナリーサーチするといった方法が思いつきます。ある一つの値に近いデータが存在するかどうかの計算量は総当たりではNのオーダーであるのに対して、バイナリーサーチならLog(N)のオーダーとなることが期待できるでしょう。1000個なら総当たりだと平均500回の比較が必要なのに対してバイナリーサーチなら10回程度の比較で近傍の値を見つけられるでしょう。
またバイナリーサーチでもまだ追いつかない場合ハッシュ法のように「あるデータを充分細かいグループに写像し、そのグループの中だけを探す」というアイデアも使えるかも知れません。本件ではある値どうしの一致ではなく「充分近いか」なので、例えば閾値が30なのであれば30程度の距離の違いでも同一のグループになるようなハッシュ関数を考えればそこそこの効率がでそうな気がします。ハッシュ関数を「絶対値を取って30で割る」という方法をベースにすれば、ハッシュ値同士の差が-1, 0, +1のエントリー群のみを比較すればよいことになります。
ハッシュ値 | 同一ハッシュ値を持つ候補の集合 |
---|---|
... | ... |
9 | 275, -280, ... |
10 | 300, -310, ... |
11 | -330, 340, ... |
... | ... |
最初に述べましたがこんな凝ったことをしても100個程度のデータ量だとアルゴリズムの複雑さゆえにかえって遅くなるかも知れません。しかしながらこれが数百万といったオーダーのデータの中から近い値があるかどうかを高速に求めなければならないという状況では有効になるかと思います。
上記はバイナリーサーチやハッシュ法といった計算機プログラミングにおいて非常にポピュラーな方法を述べたに過ぎません。こういう検討は「バイナリーサーチにするとなぜ早いのか」「ハッシュにするとなぜ早いのか」といったアルゴリズムの基本の本質を把握していれば自分でいろいろ工夫することができると思います。逆にアルゴリズムや計算量の本質の方の把握をしていないとこうした検討が難しいと思います。ぜひそういう面でも「各々のアルゴリズムの本質」について少し深く考えてみるとよいのではないでしょうか?
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+3
①2つの成分の足します。
②足し合わせたもののソートインデックスを得ます。
③合計値が±60以内のものの集合を作ります。
④それぞれの集合内で比較して条件満たすものを削除します。
削除の要件より緩くて確かめやすい前処理をすることです。
て、1個目の値でソートするだけでnlognですやん。
また無駄なことをしてしまいました。
メモリが無限にあると仮定して、O(N)。
import numpy as np
N = 10**9
M = 10000
th = 30
a = np.random.randint(M, size=(N,2))
def f(a):
mm = np.max(a, axis=0)+1
s = np.empty((mm[0], mm[1]), dtype=bool)
s.fill(1)
ans = []
for p in a:
if s[p[0], p[1]]:
ans.append(p)
s[max(0, p[0]-th+1):min(s.shape[0], p[0]+th-1), max(0, p[1]-th+1):min(s.shape[1], p[1]+th-1)] = False
return np.array(ans)
ans = f(a)
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう!
- ただいまの回答率 91.04%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
質問への追記・修正、ベストアンサー選択の依頼
teng
2018/01/12 17:20 編集
削除の条件をもう少し厳密に決めた方が良いかと。 該当する2項目のうち削除する方はどういう条件で決めるのか、近い値のリストが3つ以上あった場合はどうするのか、等。 いかがでしょうか
evanstera
2018/01/13 15:32
ご指摘ありがとうございます.イメージでは,若いインデックスのリストを削除できればと思っていました.大まかなに除去ができればと考えていたので3つ以上あった場合もこのように除去できればと思います.