Python: самый быстрый способ проверить, в каком интервале находится номер
Предположим, я разбил интервал [0, 1] на серию меньших интервалов [0, 0.2), [0.2, 0.4), [0.4, 0.9), [0.9, 1.0]. Теперь я пробую значение r в [0, 1]. Каков самый быстрый способ проверить, в каком интервале это относится к использованию Python/Numpy/Pytorch?
Очевидный способ таков:
r = np.random.rand()
if 0 <= r < 0.2:
pass # do something
elif 0.2 <= r < 0.4:
pass # do something else
elif 0.4 <= r < 0.9:
pass # do yet something else again
elif 0.9 <= r <= 1.0:
pass # do some other thing
Вам не кажется, что бинарный поиск будет быстрее на большом количестве корзин @QuangHoang? numpy.digitize для этого доступен.
@MarkMeyer Это правда. О чем я только думал.
Отвечает ли это на ваш вопрос? Самый быстрый способ проверить, какому индексу интервала соответствует значение
Ответы 2
Модуль bisect содержит функцию bisect, которая использует алгоритм деления пополам для индексации в отсортированный список. Это должно быть примерно O(log n).
from bisect import bisect
Вы можете сохранить самые правые значения ваших интервалов в списке и список функций, которые делают что-то подходящее в том же порядке. Например.
def a():
print("Do something")
intervals = [0.2, 0.4, 0.9, 1]
stufftodo = [a, a, a, a]
Вы можете, конечно, иметь разные функции для каждого интервала. Затем вы можете использовать индекс, возвращаемый bisect, для индексации в stufftodo, извлечь соответствующую функцию и вызвать ее.
r = np.random.rand()
stufftodo[bisect(intervals, r)]()
Сначала вы захотите преобразовать свой список интервалов в список границ, поэтому вместо множества интервалов [0, 0.2), [0.2, 0.4), [0.4, 0.9), [0.9, 1.0] вы просто определяете:
boundaries = [0, 0.2, 0.4, 0.9, 1.0] # values must be sorted!!
Затем вы можете выполнить бинарный поиск по всем из них, чтобы увидеть, к какому сегменту принадлежит value:
index = bisect.bisect_right(boundaries, value)
index будет индексом верхней границы, поэтому, чтобы получить диапазон, вам нужно:
range_low = boundaries[index - 1] if index > 0 else None
range_high = boundaries[index] if index < len(boundaries) else None
Это также позаботится об обработке значений, которые не находятся ни в одном из интервалов. Бинарный поиск будет выполняться в log(N) сравнениях, что теоретически является лучшим, что вы можете сделать для произвольных интервалов.
если значение точное, например, 0.4, это не сработает. Он дает интервал слева от правильного. Возможно, это легко исправить, bisect вместо bisect_left ?
@ L.Grozinger Правда, сейчас я изменил его на bisect_right (то же самое, что bisect, но более явно).
Для одного числа это максимально быстро :-). В противном случае смотрите на
np.searchsorted.