Q&A
削除の条件をもう少し厳密に決めた方が良いかと。
該当する２項目のうち削除する方はどういう条件で決めるのか、近い値のリストが3つ以上あった場合はどうするのか、等。
いかがでしょうか
リストの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 # => 削除
総当たりで比較する方法では，計算量が大きくなりすぎるので，効率的な方法があれば教えて欲しいです．
ご指摘ありがとうございます．イメージでは，若いインデックスのリストを削除できればと思っていました．大まかなに除去ができればと考えていたので3つ以上あった場合もこのように除去できればと思います．
回答3件
0
ベストアンサー
Listはサイズが大きくなると変更コストも大きくなるので、一定のサイズを超えると変更ではなく再生成のほうが早いです。あとはループを上手く回してGeneratorからListを一気に再生成させれば、Listの変更コスト0かつオーダーNで近接要素を間引くことができます。ループ内の計算コストも高くないので、そんなに時間はかからないと思います。
python
1from operator import __sub__ 2 3 4def filterclose(coordinates, distance): 5 a = coordinates[0] 6 yield a 7 for b in coordinates[1:]: 8 if not all(diff < distance for diff in map(abs, map(__sub__, a, b))): 9 yield b 10 a = b 11 12 13a_list = [[802, 1593], [802, 1601], [93, 1019], [614, 1019], [1138, 1608], [1128, 1253]] 14b_list = list(filterclose(a_list, 40)) 15 16print(b_list) # -> [[802, 1593], [93, 1019], [614, 1019], [1138, 1608], [1128, 1253]]
追記
複素数使ったりしながら色々試してたら半分以下の時間で完了するようになった。。。
python
1def filterclose(coordinates, distance): 2 iterable = iter(coordinates) 3 threshold = float(distance) 4 a = next(iterable) 5 a_comp = complex(*a) 6 yield a 7 for b in iterable: 8 b_comp = complex(*b) 9 diff = b_comp - a_comp 10 if abs(diff.real) >= threshold or abs(diff.imag) >= threshold: 11 yield b 12 a, a_comp = b, b_comp
投稿2018/01/12 11:54
編集2018/01/12 12:45
総合スコア6142
「Intel(R) Core(TM) i7-2677M CPU @ 1.80GHz」「3.6.1 (v3.6.1:69c0db5, Mar 21 2017, 18:41:36) [MSC v.1900 64 bit (AMD64)]」で60000000のリストを50000000に間引くのに100秒かかった。
少し気になったのですが、
coordinates = [[5,0], [3,3], [7,9], [5,0]]
のとき二番目の方は取り除けないのでしょうか。
前処理としてソートが必要ですか？
すいませんが二番目とはどこを指していますか？
回答内の一番目のコードと二番目のコードの結果が違う(バグってる)の意図か、[[5,0], [3,3], [7,9], [5,0]]の二番目の[5,0]が取り除けないという意図でしょうか。
後者であれば「近接要素」ではないので、その通り取り除けません。
やりたい事がふわっと書いてあったので解釈がみなさんと違ってしまったみたいです。
わかりにくくてすみません。
後者の方の2番めの[5,0]が取り除けないという意味でした。
なるほど、そのようにも解釈できますね。
盲点でした。
そうでした、それで気になったのが、
coordinates = [[5,0], [5,0], [3,3], [7,9]]
とすると[5,0]が1つ取り除かれてしまうのです。
[5,0], [5,0]が隣同士になると、
abs(5-5) < 30 and abs(0-0) < 30
で、取り除く条件を満たすからです。
おっしゃる通りで、隣り合っているかどうかで重複していても、取り除かれたり弾かれたりするのが気になっていました。
とはいえこのコードものすごく早いですね。
ありがとうございます。Python的に無駄が発生しないように書いたコードなのでnumpy等のCライブラリを使用しないコードとしては、まぁまぁ限界値だと思います。bytearrayやctypesを使うと、もしかするともっと速くかけるのかもしれませんが。
びっくりするぐらい速くなりました．
せっかくなので，ゆっくり読んで理解してみたいと思いました．
わざわざありがとうございます！
0
①２つの成分の足します。
②足し合わせたもののソートインデックスを得ます。
③合計値が±60以内のものの集合を作ります。
④それぞれの集合内で比較して条件満たすものを削除します。
削除の要件より緩くて確かめやすい前処理をすることです。
て、1個目の値でソートするだけでnlognですやん。
また無駄なことをしてしまいました。
メモリが無限にあると仮定して、O(N)。
python
1import numpy as np 2N = 10**9 3M = 10000 4th = 30 5 6a = np.random.randint(M, size=(N,2)) 7def f(a): 8 mm = np.max(a, axis=0)+1 9 s = np.empty((mm[0], mm[1]), dtype=bool) 10 s.fill(1) 11 ans = [] 12 for p in a: 13 if s[p[0], p[1]]: 14 ans.append(p) 15 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 16 return np.array(ans) 17ans = f(a)
投稿2018/01/12 10:55
編集2018/01/12 13:12総合スコア8560
ソートした結果に基づき全データに何かするとしてもデータ量がおおいならN^2よりははるかによいですよね！ｗ
バイナリーサーチもあらかじめソートするのは同じですし・・・
sortしてから考えるのがこの手の問題の王道ですね。
検索の計算オーダーをどう下げるかが問題ですね。
ちなみにメモリが無限にあればO(N)にできます。
検索をO(1)にできます。
点がスパースの場合消費するメモリ量にびっくりすることでしょう。
10個しか点がなくても凄まじいサイズの配列が作られます。
たしかにｗ
データの特性に結構依存するのが難しいところですね。
削除されるのが多数なのか、残されるのが多数なのかで戦略がだいぶ変わります。
後はCPUバウンドなのか、メモリバウンドなのかで適切にアルゴリズムを選択するしかないですね。
あまりアルゴリズムについて詳しくないので，考え方から勉強になります．
ありがとうございます！
0
実際のプログラミングにおいて計算オーダーを気にするのは場合によりけりと思います。例えば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個程度のデータ量だとアルゴリズムの複雑さゆえにかえって遅くなるかも知れません。しかしながらこれが数百万といったオーダーのデータの中から近い値があるかどうかを高速に求めなければならないという状況では有効になるかと思います。
上記はバイナリーサーチやハッシュ法といった計算機プログラミングにおいて非常にポピュラーな方法を述べたに過ぎません。こういう検討は「バイナリーサーチにするとなぜ早いのか」「ハッシュにするとなぜ早いのか」といったアルゴリズムの基本の本質を把握していれば自分でいろいろ工夫することができると思います。逆にアルゴリズムや計算量の本質の方の把握をしていないとこうした検討が難しいと思います。ぜひそういう面でも「各々のアルゴリズムの本質」について少し深く考えてみるとよいのではないでしょうか？
投稿2018/01/12 08:57
編集2018/01/12 09:00総合スコア18394
目的は自作したアプリの一部で使用するためです．
せっかくなので，計算機プログラミングにおけるアルゴリズムについて勉強してみたいと思います．
アドバイスありがとうございます．
あなたの回答
tips
プレビュー
