2次元データから範囲内の要素を高速で抽出

Question

【Python 3.7】

2つの要素x,yが与えられたときにx,yが満たす条件を探索してそれを抽出する、ということをできるだけ高速で行いたいです。
具体的には例えばx=2.5, y=1500であれば以下の表から8を抽出、という感じです。

↓y/x→	0.5~2.0	2.0~5.0	5.0~10.0	10.0~20.0	20.0~50.0
200~500	10	9	6	2	1
500~1000	10	9	7	3	2
1000~5000	9	8	7	5	3
5000~30000	7	6	5	3	1

これはあくまで例えで実際に使用したい2次元データは100×600ほどです。
for文で回せばできるのですが、時間がかかります。プログラムの関係上、数ミリ秒も無駄にしたくないです。
2次元データの型は特に指定はないです。

こういう探索に特化した方法やライブラリ等あれば教えていただきたいです。

【追記】
2次元データの更新はプログラム中では行わないため、2次元データの作成にかかる時間は考慮しません。

Comments

[TaniguchiTakaki]

いまいちその2次元データの構造がわからないのでこの例だとPythonのコードでどういう表現になるか書いてもらえますか？

Answer 1

x, yの表を見た感じだと範囲の隙間は無いようなので、x, yそれぞれについて二分探索して
テーブル参照するのが一番簡単じゃないですかね。
100x600だと表データを作るのは大変そうですが、探索速度はそれほど悪くないはずです。

from bisect import bisect_right

def solve(x, y, val_dic, ys, xs):
    y_pos = bisect_right(ys, y)
    x_pos = bisect_right(xs, x)
    return val_dic.get((x_pos, y_pos), -1)


# 表の内容に基づいて、あらかじめ用意しておくデータ
table = [
    [10, 9, 6, 2, 1],
    [10, 9, 7, 3, 2],
    [9, 8, 7, 5, 3],
    [7, 6, 5, 3, 1]
]
# tableを(x, y)をキーにした辞書でアクセスできるように変換
val_dic = {(x, y): val for y, row in enumerate(table, start=1) for x, val in enumerate(row, start=1)}

ys = [200, 500, 1000, 5000, 30000]
xs = [0.5, 2.0, 5.0, 10.0, 20.0, 50.0]


# 動作チェック
data = [(1, 200, 10), (2.5, 1500, 8), (3.0, 29999, 6), (7, 200, 6), (20, 500, 2), (49, 25000, 1),
        (5.0, 29800, 5), (19.999, 5000, 3), (0.5, 1000, 9), (4.9999, 4999.9, 8), (0.51, 200.1, 10),
        (0.49, 1500, -1), (5, 30000, -1), (0, 0, -1), (10**100, 2**342, -1), (-1, -1, -1)]
for x, y, exp in data:
    res = solve(x, y, val_dic, ys, xs)
    assert res == exp, f'x, y = {x}, {y} -> {res} != {exp}'

Comments

[ramin]

二分探索がリストに含まれていない要素の挿入点まで調べられるとは知りませんでした。
二次元データ内で一部カーブフィッティングが使用できる部分があったので、最終的には二分探索＋カーブフィッティングで実装しました。
ありがとうございました。