Сравнение до бесконечности при проверке если точка находится выше линии


У меня есть функция, которая вызывается в непрерывном цикле. Я профилированного мой код, и это, где моя самая большая узкое место. Эта функция довольно проста: он проверяет, если точка в (Х,г) форме выше линии (уклон, перехват) форма.

Проблема в том, она также имеет дело со случаем, когда склон является положительная бесконечность, и перехватить дает х-перехват. В этом случае функция должна возвращать значение true , если точка находится справа от линии.

Вот эта функция написана, как это было, когда я заметил узкое место:

def point_over(point, line):
    """Return true if the point is above the line.
    """
    slope, intercept = line
    if slope != float("inf"):
        return point[0] * slope + intercept < point[1]
    else:
        return point[0] > intercept

На моей машине, это как быстро он работает:

>>> timeit("point_over((2.412412,3.123213), (-1.1234,9.1234))", 
           "from __main__ import point_over", number = 1000000)
1.116534522825532

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

point[0] * line[0] + line[1] < point[1] if line[0] != float('inf') else point[0] > line[1]

И выполняет точно в раз все:

>>> timeit("point[0] * line[0] + line[1] < point[1] if line[0] != float('inf') else point[0] > line[1]", 
           "point, line = ((2.412412,3.123213), (-1.1234,9.1234))", number = 1000000)
0.9410096389594945

Тем не менее, это одна строка кода еще коробления большая часть времени выполнения в мой код, даже будучи подставлена.

Почему сравнение с плавающей точкой('инф') займет больше времени, чем ряд расчетов, а также сравнение? Есть ли способ сделать это быстрее?

Как пример того, что я утверждаю, здесь представлены скоростей двух частей моей троичной заявление разделены и по времени:

>>> timeit("line[0] != float('inf')", 
           "point, line = ((2.412412,3.123213), (-1.1234,9.1234))", number = 1000000)
0.528602410095175
>>> timeit("point[0] * line[0] + line[1] < point[1]", 
           "point, line = ((2.412412,3.123213), (-1.1234,9.1234))", number = 1000000)
0.48756339706397966

Мой основной вопрос в том, почему это занимает так долго, чтобы сделать сравнение до бесконечности. Вторичная любые советы о том, как ускорить их. В идеале существует какое-то волшебное (даже если невероятно суховато) так, чтобы половина времени выполнения этой линии, не опуская вниз и C. В противном случае, скажите мне, что я должен опуститься до с.



15691
13
задан 14 ноября 2011 в 09:11 Источник Поделиться
Комментарии
4 ответа

Было бы быстрее использовать математику.isinf() функции:

>>> from math import e, pi, isinf
>>> s = [0, float('inf'), e, pi]
>>> map(isinf, s)
[False, True, False, False]

Причина ваша текущая проверка длится так долго из-за того, сколько работы он должен делать:

>>> from dis import dis

>>> def my_isinf(f):
return f == float('Inf')

>>> dis(my_isinf)
2 0 LOAD_FAST 0 (f)
3 LOAD_GLOBAL 0 (float)
6 LOAD_CONST 1 ('Inf')
9 CALL_FUNCTION 1
12 COMPARE_OP 2 (==)
15 RETURN_VALUE

Есть глобальная нагрузки, который включает в себя поиск в словаре. Есть две аргументов вызова функции. Конструктор поплавок должен разобрать строку, а затем выделить (и счетчик) новый объект всплывать в памяти. Затем шаг сравнении отправляет свою работу на поплавок__.экв__, который возвращает логическое значение, которое затем подается на если-заявление.

16
ответ дан 14 ноября 2011 в 09:11 Источник Поделиться

Другие упомянули математику.isinf(). Но это, вероятно, будет быстрее, поскольку он уклоняется от поиск по имени и вызова функции:

def point_over(point, line, infinity=float("inf")):
slope, intercept = line
if slope == infinity:
return point[0] > intercept
return point[0] * slope + intercept < point[1]

В принципе, вместо вычисления с плавающей точкой("инф") каждый раз, когда функция вызывается, вы оцениваете его как-то на функция определения времени и хранить его в локальную переменную, объявив ее в качестве аргумента по умолчанию. (Локальные переменные быстрее получить доступ к более глобальные.)

6
ответ дан 14 ноября 2011 в 09:11 Источник Поделиться

В медленной части , если склон != поплавок("инф") нет сомнений преобразования строки в число с плавающей точкой. Было бы проще просто использовать , если не математика.isinf(уклон) вместо. Конечно, вы должны импортировать математике для того чтобы работать.

3
ответ дан 14 ноября 2011 в 09:11 Источник Поделиться

Это будет даже быстрее (избегая вызовов функций в целом) если вы кэшировать значение с плавающей точкой("инф") в переменной:

>>> def floatcall():
... return 1.0 == float("inf")
...
>>> def mathcall():
... return math.isinf(1.0)
...
>>> inf = float("inf")
>>> def nocall():
... return 1.0 == inf
...
>>> timeit.timeit("floatcall()", "from __main__ import floatcall", number=1000000)
0.37178993225097656
>>> timeit.timeit("mathcall()", "import math; from __main__ import math call", number=1000000)
0.22630906105041504
>>> timeit.timeit("nocall()", "from __main__ import inf, nocall", number=1000000)
0.17772412300109863

2
ответ дан 14 ноября 2011 в 09:11 Источник Поделиться