質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

91.25%

  • Python 3.x

    2773questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python3:近い値をもつリストを判定したい

解決済

回答 3

投稿

  • 評価
  • クリップ 2
  • VIEW 128

evanstera

score 4

リストの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ページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • teng

    2018/01/12 17:20 編集

    削除の条件をもう少し厳密に決めた方が良いかと。 該当する2項目のうち削除する方はどういう条件で決めるのか、近い値のリストが3つ以上あった場合はどうするのか、等。 いかがでしょうか

    キャンセル

  • evanstera

    2018/01/13 15:32

    ご指摘ありがとうございます.イメージでは,若いインデックスのリストを削除できればと思っていました.大まかなに除去ができればと考えていたので3つ以上あった場合もこのように除去できればと思います.

    キャンセル

回答 3

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/12 21:11

    「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秒かかった。

    キャンセル

  • 2018/01/12 22:17

    少し気になったのですが、
    coordinates = [[5,0], [3,3], [7,9], [5,0]]
    のとき二番目の方は取り除けないのでしょうか。

    前処理としてソートが必要ですか?

    キャンセル

  • 2018/01/12 22:28

    すいませんが二番目とはどこを指していますか?

    回答内の一番目のコードと二番目のコードの結果が違う(バグってる)の意図か、[[5,0], [3,3], [7,9], [5,0]]の二番目の[5,0]が取り除けないという意図でしょうか。

    後者であれば「近接要素」ではないので、その通り取り除けません。

    やりたい事がふわっと書いてあったので解釈がみなさんと違ってしまったみたいです。

    キャンセル

  • 2018/01/12 22:35

    わかりにくくてすみません。
    後者の方の2番めの[5,0]が取り除けないという意味でした。

    なるほど、そのようにも解釈できますね。
    盲点でした。

    キャンセル

  • 2018/01/12 22:50

    そうでした、それで気になったのが、

    coordinates = [[5,0], [5,0], [3,3], [7,9]]

    とすると[5,0]が1つ取り除かれてしまうのです。

    キャンセル

  • 2018/01/12 23:17

    [5,0], [5,0]が隣同士になると、
    abs(5-5) < 30 and abs(0-0) < 30
    で、取り除く条件を満たすからです。

    キャンセル

  • 2018/01/13 00:20

    おっしゃる通りで、隣り合っているかどうかで重複していても、取り除かれたり弾かれたりするのが気になっていました。

    とはいえこのコードものすごく早いですね。

    キャンセル

  • 2018/01/13 16:21

    ありがとうございます。Python的に無駄が発生しないように書いたコードなのでnumpy等のCライブラリを使用しないコードとしては、まぁまぁ限界値だと思います。bytearrayやctypesを使うと、もしかするともっと速くかけるのかもしれませんが。

    キャンセル

  • 2018/01/13 20:27

    びっくりするぐらい速くなりました.
    せっかくなので,ゆっくり読んで理解してみたいと思いました.
    わざわざありがとうございます!

    キャンセル

+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個程度のデータ量だとアルゴリズムの複雑さゆえにかえって遅くなるかも知れません。しかしながらこれが数百万といったオーダーのデータの中から近い値があるかどうかを高速に求めなければならないという状況では有効になるかと思います。

上記はバイナリーサーチやハッシュ法といった計算機プログラミングにおいて非常にポピュラーな方法を述べたに過ぎません。こういう検討は「バイナリーサーチにするとなぜ早いのか」「ハッシュにするとなぜ早いのか」といったアルゴリズムの基本の本質を把握していれば自分でいろいろ工夫することができると思います。逆にアルゴリズムや計算量の本質の方の把握をしていないとこうした検討が難しいと思います。ぜひそういう面でも「各々のアルゴリズムの本質」について少し深く考えてみるとよいのではないでしょうか?

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/13 20:20

    目的は自作したアプリの一部で使用するためです.
    せっかくなので,計算機プログラミングにおけるアルゴリズムについて勉強してみたいと思います.
    アドバイスありがとうございます.

    キャンセル

+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)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/12 21:00

    ソートした結果に基づき全データに何かするとしてもデータ量がおおいならN^2よりははるかによいですよね!w
    バイナリーサーチもあらかじめソートするのは同じですし・・・

    キャンセル

  • 2018/01/12 21:46

    sortしてから考えるのがこの手の問題の王道ですね。

    検索の計算オーダーをどう下げるかが問題ですね。

    ちなみにメモリが無限にあればO(N)にできます。
    検索をO(1)にできます。

    点がスパースの場合消費するメモリ量にびっくりすることでしょう。
    10個しか点がなくても凄まじいサイズの配列が作られます。

    キャンセル

  • 2018/01/12 21:47

    たしかにw

    キャンセル

  • 2018/01/12 21:51

    データの特性に結構依存するのが難しいところですね。

    削除されるのが多数なのか、残されるのが多数なのかで戦略がだいぶ変わります。

    後はCPUバウンドなのか、メモリバウンドなのかで適切にアルゴリズムを選択するしかないですね。

    キャンセル

  • 2018/01/13 20:21

    あまりアルゴリズムについて詳しくないので,考え方から勉強になります.
    ありがとうございます!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

ただいまの回答率

91.25%

関連した質問

同じタグがついた質問を見る

  • Python 3.x

    2773questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。