Как эффективно определить интервал, в котором находится данное значение?

Рассмотрим следующие определения зоны для значения x:

  • 'A': x <1
  • 'B': 1 <= x <10
  • 'C': 10 <= x <112
  • 'D': 112 <= x

Я ищу эффективный способ определения зоны для заданных значений x. Я придумал:

borders = (1, 10, 112)

tst_values = (.2, 2, 22, 222)
for x in tst_values:
    z = next((i for b, i in zip(borders, 'ABC') if x < b), 'D')
    print(f" * Value {x:3g} is in zone '{z}'.")

# The output is:
# * Value 0.2 is in zone 'A'.
# * Value   2 is in zone 'B'.
# * Value  22 is in zone 'C'.
# * Value 222 is in zone 'D'.

Каковы лучшие практики решения такой проблемы, особенно если количество зон, т.е. len(borders), велико. borders может содержать произвольный список (возрастающих) чисел с плавающей запятой.

Обновлять Немного перефразировал вопрос, чтобы ответить на комментарии.

Это простая логарифмическая задача. Возьмите журнал числа, чтобы получить цифры ..

Mr. Polywhirl 10.08.2018 16:17

@ Mr.Polywhirl Нет шаблона для зон - границы могут быть произвольным списком возрастающих чисел. Я обновил вопрос, чтобы прояснить это.

Dietrich 10.08.2018 16:21

«особенно если количество границ большое» - Вы имеете в виду, если у вас много границ? Или вы имеете в виду, что значение не так много границ велико?

Leon 10.08.2018 16:21

@Dietrich, значения тестов всегда растут по своей природе?

Albin Paul 10.08.2018 16:22

@Leon Количество зон большое. Значение зон может быть представлено обычными числами с плавающей запятой.

Dietrich 10.08.2018 16:24

@AlbinPaul Тестовые значения могут быть предварительно отсортированы в любом желаемом порядке.

Dietrich 10.08.2018 16:25

@ Дитрих, вы проверяли, работают ли решения?

rafaelc 11.08.2018 01:37
3
7
136
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Ответ принят как подходящий

Чтобы эффективно найти диапазон, в котором вы находитесь в длинном списке отсортированных границ, я бы предложил использовать бинарный поиск. В основном вы смотрите на середину своего массива границ, проверяете, являетесь ли вы большим / маленьким. В зависимости от этого вы проверяете значение на одной / трех четвертях длины массива границ. И так далее.

Это легко реализовать с помощью рекурсии вручную. В качестве альтернативы вы можете использовать реализацию numpy numpy.digitize, на которую указал YSelf. Последний почти наверняка будет быстрее первого.

При использовании numpy.digitize ваш код будет выглядеть следующим образом:

borders = (1, 10, 112)
values = (.2, 2, 22, 222)

for x in values:
    z = 'ABCD'[numpy.digitize(x, borders)]
    print(f" * Value {x:3g} is in zone '{z}'.")
numpy.digitize реализует этот двоичный поиск.
YSelf 10.08.2018 16:30

Не знал о np.digitize() - это хорошо решает мою проблему.

Dietrich 11.08.2018 11:51

Эффективный способ сделать это - выполнить двоичный поиск через границы. У Python есть сборка в библиотеке bisect, которая сделает это за вас:

import bisect

borders = (1, 10, 112)
tst_values = (.2, 2, 22, 222)
    for x in tst_values:
    border_right = bisect.bisect_right(borders, x) # x < b
    # or
    border_left = bisect.bisect_left(borders, x)   # x > b

Это даст вам индекс в границах, в которые попадает значение x. Затем вы можете преобразовать этот индекс в букву, если хотите.

Основываясь на использовании < и <= в примере OP, нам нужен bisect_left или просто bisect, который является псевдонимом для bisect_left.

Felk 10.08.2018 16:39

Если вам нужен эффективный способ решения этой проблемы, используйте несколько векторизованных операций с использованием np.greater_than и np.less с outer, а затем принимайте значения индекса с помощью np.take

a = np.greater_equal.outer(tst_values, [-np.inf, 1,10,112]) & \
    np.less.outer(tst_values, [1, 10,112, np.inf])

np.take(list('ABCD'), np.argmax(a, axis=1))

Это работает довольно эффективно. Для 5-миллиметровых рядов он выполняется менее чем за секунду.

%timeit (...)
922 ms ± 8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Спасибо за тесты - для меня это второй выбор после np.digitize().

Dietrich 11.08.2018 11:53

Другие вопросы по теме