Home>

[Python 3.7]

When two elements x and y are given, we want to search for conditions that x and y satisfy and extract them as fast as possible.
Specifically, for example, if x = 2.5 and y = 1500, 8 is extracted from the table below.

↓ 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

This is just an example, and the actual 2D data I want to use is about 100x600.
You can do it with a for statement, but it takes time. I don't want to waste a few milliseconds because of the program.
There is no special specification for the type of 2D data.

I would like to know if there is a method or library specialized for such search.

[Added]
Since 2D data is not updated in the program, the time required to create 2D data is not considered.

  • Answer # 1

    There seems to be no gap in the range when looking at the table of x, y, so do a binary search for each of x, y
    Isn't it the easiest to refer to the table?
    If it is 100x600, it will be difficult to create tabular data, but the search speed should not be so bad.

    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)
    # Data prepared in advance based on table contents
    table = [
        [10, 9, 6, 2, 1],
        [10, 9, 7, 3, 2],
        [9, 8, 7, 5, 3],
        [7, 6, 5, 3, 1]
    ]
    # convert table so that it can be accessed with dictionary with (x, y) as key
    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]
    # Check operation
    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} '